Log In
1 vote

So , 1 is mandatory in Regular expression ; and both of above grammar allows strings without 1 to be genearated.

So ,  I expected None of above to be answer. What Am I missing here ?

Consider for (A)

Production = A0 -> A1

A1-> 0

in Theory of Computation
retagged by
I think you are right @vishal. it should be None of these as   0 or 00 or 0* is not in lang unless it conatins one 1 and both grammer are producing it. so it should be none of these.

2 Answers

0 votes
i think the grammar whould be

S -> 0S | A

A -> 1B

B -> 0B | 1B

B  -> epsiloon
0 votes
Create NFA for the given expression and from that grammer is as follows:
replace A0 with S and A1 with A
S->0S | 1A
A -> 0A | 1A | epsilon
 the above grammer doesn't match with option A and B

In the options A and B they have production rule A0 -> A1 (As mentioned by @vishal8492) which will produce string "0" which is not accepted by the regular expression.

So the answer would D.

edited by
Smallest string 1 cannot be generate by both so answer option d

Related questions

1 vote
1 answer
0 votes
3 answers
S->AbaC A->BC B->b/epsilon C->D/epsilon D->d I want to know that will A contain epsilon as B and C both are null variables???(In Elimination of epsilon-production)
asked Nov 30, 2016 in Theory of Computation Anmol Verma 307 views
1 vote
1 answer
Consider the context free grammar below. What language does it generates? S -> 0B|1A A ->0|0S|1AA B ->1|1S|0BB
asked Oct 5, 2016 in Theory of Computation Shweta Singh Lodhi 111 views