GATE2025_CS1_Q19

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?

✅ Final Answer:

The correct answer is option (A) L(G) = {a²bⁿ | n ≥ 1} ∪ {aⁿb² | n ≥ 1}.

🔹 Short Answer:

The language generated by non-terminal A is a⁺ (one or more 'a's). The language for B is b⁺ (one or more 'b's). The start symbol S has two productions:
1. S → aaB generates strings with 'aa' followed by b⁺, i.e., {a²bⁿ | n ≥ 1}.
2. S → Abb generates strings with a⁺ followed by 'bb', i.e., {aⁿb² | n ≥ 1}.
The total language L(G) is the union of these two possibilities.

🔸 Long Answer:

To determine the language generated by the grammar G, we need to analyze the set of strings that can be derived from each non-terminal, starting from the smallest components and building up to the start symbol S.

Step 1: Analyze the language for non-terminal A

The rules for A are: A → a | aA

• The base case is A → a. This produces the string "a".
• The recursive case is A → aA. This means an 'A' can be replaced by an 'a' followed by another 'A'.
• Let's derive a few strings:
  • A ⇒ a
  • A ⇒ aA ⇒ aa
  • A ⇒ aA ⇒ aaA ⇒ aaa

This pattern shows that A generates one or more 'a's. In formal language notation, this is represented as a⁺. So, L(A) = {aⁿ | n ≥ 1}.

Step 2: Analyze the language for non-terminal B

The rules for B are: B → b | bB

• The base case is B → b. This produces the string "b".
• The recursive case is B → bB.
• Derivations:
  • B ⇒ b
  • B ⇒ bB ⇒ bb
  • B ⇒ bB ⇒ bbB ⇒ bbb

Similarly, B generates one or more 'b's. This is represented as b⁺. So, L(B) = {bⁿ | n ≥ 1}.

Step 3: Analyze the language for the start symbol S

The rules for S are: S → aaB | Abb. The pipe symbol `|` represents a choice, so the final language L(G) is the union of the languages generated by each production.

• Case 1: S → aaB
  This rule means the string must start with "aa" followed by any string that can be generated by B. Since L(B) is b⁺, this production generates the language of "aa" followed by one or more 'b's.
  Language Part 1: {a²bⁿ | n ≥ 1}.
  Examples: aab, aabb, aabbb, ...
• Case 2: S → Abb
  This rule means the string must start with any string from A, followed by "bb". Since L(A) is a⁺, this production generates the language of one or more 'a's followed by "bb".
  Language Part 2: {aⁿb² | n ≥ 1}.
  Examples: abb, aabb, aaabb, ...

Step 4: Combine the languages

The total language L(G) is the union of the languages from the two production rules for S.

L(G) = L(aaB) ∪ L(Abb)
L(G) = {a²bⁿ | n ≥ 1} ∪ {aⁿb² | n ≥ 1}

Comparing this with the given options, we find that it exactly matches option (A).

Bibliography:
- Hopcroft, J. E., Motwani, R., & Ullman, J. D. (2006). Introduction to Automata Theory, Languages, and Computation. Addison-Wesley. (Chapter 5: Context-Free Grammars and Languages).
- Sipser, M. (2012). Introduction to the Theory of Computation. Cengage Learning. (Chapter 2: Context-Free Languages).

Ask your doubts in comment form our GURUJEE will reply ASAP, click notify me button so that you get notified on reply.