Question No.1 Give CFG for the following languages, a. a^n.b^m where m = n-1 and

Question

Question No.1
Give CFG for the following languages,
a. a^n.b^m where m = n-1 and n = 1,2,3…
Some words belonging to this language are, a , aab , aaabb , aaaabbb , ….
b. a^n.b^2n where n = 1,2,3…
Some words belonging to this language are, abb , aabbbb , aaabbbbbb , ….

Question No.2
Consider the CFG given below and find Null and Null-able transitions (if any) also remove these transitions to give new CFG
S ---- > ABB | CC | ABC | AC
A --- > a | ?
B --- > b | C
C --- > ab | ?
[Here ? means null string, as in CFG’s we use ? for indicating null string instead of ^ sign]

Question No.3
Convert the CFG (Context Free Grammar) given below to CNF (Chomsky Normal Form)
S ---- > YYY | ZZ | aa | bb
Y --- > a | Z
Z --- > b | Y

Question No.4
Design PDA (Push Down Automata) for the language given below,
(ba)^n(a)^n n = 1,2,3…

Explanation / Answer

1)a)set = {a,b} S --> aX X --> aXb | ab | e 1)b)SET = {a,b} S --> aSbb S --> abb S --> e 2)a) S --> ABB | BB | CC | C | ABC | AB | BC | AC | A | C A --> a B --> b | C C --> ab 3)a S --> RY | ZZ | YZ | ZY R --> YY Y --> a | Z Z --> b | Y

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.