NIELIT 2016 MAR Scientist B - Section C: 29

Question

The CFG $S \to aS\mid bS\mid a\mid b$ is equivalent to 

• A. $(a+b)$
• B. $(a+b)(a+b)^*$
• C. $(a+b)(a+b)$
• D. all of these

Comments

B is the correct answer

---

S->(a+b)*S/a/b

(a+b)*(a+b)

B is correct

---

option B is the answer

Answer 1

(A)-does not generate strings  $babb,abb$ etc.  but CFG generates it.(This option generates only 1-length strings)

(B)- is the answer

(C)-it only generates 2-length strings and other strings generated by the CFG are not generated by this regular expression.

So, B is correct.