439 views
0 votes
0 votes

Which of the following language generated by given grammar?

1) L = {w : na(w) and nb(w) both are even}

2) L = {w : na(w) and nb(w) both are odd}

3) L = {w : na(w) or nb(w) are even}

4) L = {w : na(w) or nb(w) are odd}

1 Answer

Best answer
3 votes
3 votes

Starting from S, picking a production generates 'a' or 'b' or $\epsilon $. At the next step Non-Terminal A or B has to be chosen. A string can only be generated after returning back to S and then using $\epsilon$. Now, to generate an odd number of a's, we have to return back to S in odd number of steps and similar is the case for generating 'b'. This is because at each step of the derivation a terminal is generated. 

The dependency graph shows that odd a's and odd b's cannot be generated.

selected by

Related questions

2 votes
2 votes
2 answers
1
Rajesh R asked Oct 24, 2017
413 views
$S - AB$$A - aA / epsilon$$B ->aBb / epsilon$What is the class of language generated by the above grammar ?
0 votes
0 votes
1 answer
2
Ashwani Kumar 2 asked May 7, 2016
575 views
S- +SS | -SS | aGive explanation?
1 votes
1 votes
2 answers
3
sh!va asked Jul 12, 2016
1,040 views
S→ A 0BA→ BB|0B →AA|1What is the number of terminal strings of length 5 generated by the context-free grammar shown above?4567
0 votes
0 votes
1 answer
4