1)Convert the following context free grammar to Chomsky Normal
Form
S → a X | Yb
X → S | λ
Y → b Y | λ
2)Some languages distinguish between uppercase and lowercase in identifiers. What are the pros and cons of this design decision?
3)Use the pumping lemma to prove that the following languages
are not regular. (The alphabet is Σ = {a,
b}.)
a) L = {an b1 ak: k >= n+
l}
b) L = {ww: w ∈ Σ *}
c) L= {ak2} // this is k square
d) L ={uwwrv :u,v,w ∈ Σ+, |u| >= |v|}
1)Convert the following context free grammar to Chomsky Normal Form
S → a X | Yb
X → S | λ
Y → b Y | λ
-> Remove λ productions
S → a X | Yb | a | b
X → S
Y → b Y | b
-> Remove unit productions
S → a S | Yb | a | b
Y → b Y | b
-> Replace all productions with non-terminals except
for unit productions
Below is the final CNF grammar
| S → AS | YB | a | b Y → BY | b A → a B → b |
Note: One
question at a time please -- HOMEWORKLIB RULES
1)Convert the following context free grammar to Chomsky Normal Form S → a X | Yb...
TRUE OR FALSE? (Note: E = belongs to) 1. A context-free grammar G is in Chomsky normal form. Then G is not recursive. 2. Let G be an arbitrary context-free grammar. uAv =>* u'A'v' , where u, v, u' and v' E V* and A E (V - Eps), then L(G) is infinite. 3. {ww : w E {a, b}*} is accepted by some NDPDA with exactly two states