Consider the language \(L = \left\{ {{a^n}{b^{n - 3}}\ | n > 2} \right\}\) on ∑ = {a, b}. Which one of the following grammars generates the language L?

Given language:

\(L = \left\{ {{a^n}{b^{n - 3}} |n > 2} \right\}\)

It is generating strings of type = {aaa, a⁴b, a⁵b², a⁶b³, ………………….}

Now, consider all the options one by one :

Option 1: S → aA|a, A → aAb|b

This grammar is generating strings of type = {a, ab, aabb…………}. But in given language, we are not getting {a}. So, it is not generating given language.

Option 2: S → aaA|λ, A → aAb|λ 

Smallest string that is generated by this grammar is λ. But for given language it is not true, because strings are starting with aaa.

Option 3: S → aaaA|a, A → aAb|λ

In this grammar also, smallest string possible is {a} which is not required here. So, it is not generating given language.

Option 4: S → aaaA, A → aAb|λ

This grammar generates string of type = {aaa, a⁴b, a⁵b²,…….} which is same as in the given language. It generates the given language.