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} Theory of Computation theory-of-computation + – set2018 asked Dec 10, 2017 set2018 439 views answer comment Share Follow See all 2 Comments See all 2 2 Comments reply krish__ commented Dec 10, 2017 i reshown by krish__ Dec 10, 2017 reply Follow Share Is it 1)? 0 votes 0 votes set2018 commented Dec 10, 2017 reply Follow Share yes pls explain why 0 votes 0 votes Please log in or register to add a comment.
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. krish__ answered Dec 10, 2017 selected Dec 10, 2017 by set2018 krish__ comment Share Follow See all 0 reply Please log in or register to add a comment.