Computer Sciences > GATE 2025 SET-1 > Context-Free Grammars
Consider the following context-free grammar G, where S, A, and B are the variables (non-terminals), a and b are the terminal symbols, S is the start variable, and the rules of G are described as:
S→aab|Abb
A→a|aA
B→b|bB
Which ONE of the languages L(G) is accepted by G?
A
L(G)={a2bn|n≥1}∪{anb2|n≥1}
B
L(G)={anb2n|n≥1}∪{a2nbn|n≥1}
C
L(G)={anbn|n≥1}
D
L(G)={a2nb2n|n≥1}

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

A palindrome is a word that reads the same forwards and backwards. In a game of words, a player has the following two plates painted with letters. From...
#1 MCQ
Which number does not belong in the series below? 2, 5, 10, 17, 26, 37, 50, 64
#4 MCQ
Choose the word that is opposite in meaning to the word “coherent”.
#5 MCQ

Related Topics

No tags found

Unique Visitor Count

Total Unique Visitors

Loading......