UGC NET CSE | December 2019 | Part 2 | Question: 44

Question

Consider the language $L = \{ a^n b^{n-3} \mid n > 2 \}$ on $\Sigma = \{ a, b\}$. Which one of the following grammars generates the language $L$?

• A. $S \rightarrow aA \mid a, A  \rightarrow aAb \mid b$
• B. $S \rightarrow aaA \mid \lambda, A  \rightarrow aAb \mid \lambda$
• C. $S \rightarrow aaaA \mid a, A \rightarrow aAb \mid \lambda$
• D. $S \rightarrow aaaA, A \rightarrow aAb \mid \lambda$

Answer 1

Language $L=\{aaa,aaaab,aaaaabb,aaaaaabbb……..\}$

option 1 and 3 are not correct because  they generate the string ‘a’ which doesn’t belong to L.

Option 2 is not correct because the grammar generates the string lambda which doesn’t belong to L.

Hence option 4 is the correct answer.

The language generated by the grammar of option 4 is $L=\{a^{3}.a^nb^{n}|where\ n>=0\}=\{a^{n+3}b^{n}|where\ n>=0\}$

where $\{a^nb^n|n>=0\}$ is generated by the variable A.

So the language generated by grammar is equal to given grammar.