CS 181 Homework Week 7 solution

$24.99

Original Work ?
Category: You will Instantly receive a download link for .ZIP solution file upon Payment

Description

5/5 - (8 votes)

0. Consider the following language over ∑ = { a, b, c }:
L0 = { ai
b
j
c
k | i=j or j=k }
Determine whether L0 is: i) finite state or ii) context free & not finite state. If i, show it by any means we
have covered in class. If ii, give a context free grammar for it and use the Pumping Lemma for Finite
State Languages to show that it is not finite state.
1. Consider the following language over ∑ = { a, b, # }:
L1 = { an b
m # | n > m }
Determine whether L1 is: i) finite state or ii) context free & not finite state. If i, show it by any means we
have covered in class. If ii, show a PDA for L1 as a transition diagram and prove that it is not finite state
by any means discussed in class.
2. Consider the following language over ∑ = { 0, 1, # }:
L2 = { t # tR # t | t in { 0, 1 }* }
Prove that it is not context free using the Pumping Lemma for context free languages.
eof