S→aab|Abb
A→a|aA
B→b|bB
Which ONE of the languages L(G) is accepted by G?
Correct : a
Explanation:
1. Analyze the Sub-Grammars:
The start variable S has two production branches: S → aab and S → Abb. We can evaluate what languages are generated by exploring both paths independently.
2. Path 1: S → aab
• This path generates a single, fixed terminal string: aab (or a2b1).
3. Path 2: S → Abb
Let's look at the variable A. The rules for A are:
A → a | aA
• This is a classic recursive structure that generates one or more 'a's sequentially. Thus, A produces the language {an | n ≥ 1}.
• Substituting A back into the path S → Abb, the language generated by this branch becomes:
{anbb | n ≥ 1} = {anb2 | n ≥ 1}
4. Combine Both Branches:
The complete language generated by the grammar G is the union of both derivation paths:
L(G) = {a2b1} ∪ {anb2 | n ≥ 1}
5. Match with the Options:
Let's check how this matches option (a):
{a2bn | n ≥ 1} ∪ {anb2 | n ≥ 1}
• For the first set {a2bn | n ≥ 1}, when n = 1, it produces a2b1 (which exactly covers Path 1). When n = 2, it produces a2b2.
• For the second set {anb2 | n ≥ 1}, when n = 2, it also produces a2b2.
• Since the string a2b1 is perfectly accounted for by the first term when n = 1, the union simplifies exactly to the language generated by our grammar rules.
6. Note on Redundant Rules:
The variable B (defined as B → b | bB) is never reachable from the start variable S. Because it is a non-reachable variable, its rules have absolutely no effect on the final language L(G).
Similar Questions
Total Unique Visitors