made easy test series

Question

Comments

Only 3rd?

---

Yes. How did you approach this question (keeping in mind the time)?

---

Try to derive some strings after that you will get idea about the pattern.

i) epsilon, a, b, after that by seeing grammar first anyone can think aBb means comparison of a amd b, but A->aA/bA/epsilon it derives everything. Hence just by putting B as epsilon you can get all (a+b)*

Try this way in second also.

iii) But in third you can only iterate a, but for b you need at least one a.

Hence this language is comparing a and b.

Answer 1

1. S-->AB

          A-->aA|bA|e

          B-->abB|e

this grammar is generating

(a+b)* {a^n b^n | n>=0}

---

S-->AaB

A-->aC|e

B-->aB|bB|e

C-->aCb|e

this grammar is generating

[a.{a^n b^n | n>=0}]*.a.(a+b)*

---

S-->AB

A-->aA|e

B-->aBb|e

this grammar is generating

a*. {a^n b^n | n>=0}

only 3rd is generating CFL not Regular.

Comments

If this is not regular a*. {a^n b^n | n>=0}  then why is this (a+b)* {a^n b^n | n>=0} ?

---

(a+b)* {a^n b^n | n>=0} 

because (a+b)* will generate all strings