UGC NET Computer Science December 2019 | Question 95

Question 95

---

Consider the following grammar:
S→0A|0BB
A→00A|λ
B→1B|11C
C→B
Which language does this grammar generate?

1. 1. L((00)* 0+(11)*1)
2. 2. L(0(11)*+1(00)*)
3. 3. L((00)* 0)
4. 4. L(0(11)*1)

Answer :

Explanation

Strings generated by given grammers are like 0, 000, 00000, 0000000,....., strings with odd number of 0's.

Option 1 is incorrect because strings generated by given option (1) language contains string containing 1's also, like 1, 111, 11111,... whereas given grammer generated string with only 0's.

Option 2 is incorrect because strings generated by given option (2) language contains string containing 1's and it can't generate "000", whereas given grammer generated string with only 0's like 0, 000, 00000....

Option 3 is correct because every string generated by given grammar will contain only 0's and given option is generating string containing 0's also. Option 3 language generates string same as given grammar. i.e strings generated by given grammers and option (3) language are like 0, 000, 00000, 0000000,....., strings with odd number of 0's.

Option 4 is incorrect because strings generated by given option (4) language contains string containing 1's also, like 01, 0111, 011111,... whereas given grammer generated string with only 0's.

So, option 3 is correct answer

Previous	Next
UGC NET CS December 2019 - Question 94	UGC NET CS December 2019 - Question 96