Consider the following grammar where S is the start symbol, and a and b are terminal symbols.
S →aSbS |bS |ϵ
Which of the following statements is/are true?
Solution :
The correct options/answers are:
1. The grammar is ambiguous
2. The string abb has two distinct derivations in this grammar
Let us analyze the given grammar and why these statements are correct.
The grammar is defined as:
S → aSbS | bS | ϵ
where S is the start variable (non-terminal), and a and b are terminal symbols, and ϵ represents the empty string.
1. Ambiguity of the Grammar:
A grammar is ambiguous if there exists at least one string in the language generated by the grammar that has more than one leftmost derivation, more than one rightmost derivation, or more than one distinct parse tree.
Let us verify this by finding derivations for the string "abb".
Derivation 1 (Leftmost Derivation):
We start with the production rule S → aSbS:
S ⇒ aSbS (using S → aSbS)
⇒ abS (using S → ϵ for the first S)
⇒ abbS (using S → bS for the remaining S)
⇒ abb (using S → ϵ for the final S)
Derivation 2 (Leftmost Derivation):
We can also derive the same string starting with S → aSbS, but applying different rules:
S ⇒ aSbS (using S → aSbS)
⇒ asbS (we keep the first S for now)
Let's substitute the first S using the rule S → bS:
S ⇒ abSbS (using S → bS for the first S)
⇒ abbS (using S → ϵ for the first S in the middle)
⇒ abb (using S → ϵ for the final S)
Since we have found two distinct derivations (and thus two distinct parse trees) for the string "abb", the string "abb" has two distinct derivations in this grammar, which directly proves that the grammar is ambiguous.
2. Decidability of Context-Free Languages:
The grammar is context-free, and context-free languages are decidable. Therefore, the statement "The language generated by the grammar is undecidable" is false. Additionally, the string "abab" has multiple derivations, making the statement about "abab" having only one rightmost derivation false as well.
Completely free for students. Educators & coaching institutes get 2 months free Pro trial to create tests.
Access unlimited practice questions, detailed step-by-step solutions, and exam study materials — completely free for students.
Create and conduct professional online assessments with AI question generation, tab proctoring, and comprehensive batch management.
Prepare for GATE 2026 Civil Engineering with the latest question papers, previous year papers, detailed solutions, syllabus, exam pattern, preparation tips, mock tests, and subject-wise study material. Download GATE 2026 CE question papers with solutions in PDF format and boost your preparation for top engineering institutes and PSU recruitment.
Prepare effectively for GATE 2026 Electronics & Communication Engineering (EC) with this comprehensive Question Paper with Solutions. This resource includes detailed explanations, concept-wise solutions, previous year paper analysis, and exam-oriented practice to help aspirants strengthen core subjects like Electronic Devices, Analog Circuits, Digital Circuits, Signals & Systems, Network Theory, Control Systems, Electromagnetics, Communications, and more. Perfect for revision, self-assessment, and boosting your GATE 2026 EC preparation strategy.
Copyright © 2026 Combe Labs Private Limited. All Rights Reserved.