Question Details

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?

Options

A

The grammar is ambiguous

B

The string abb has two distinct derivations in this grammar

C

The string abab has only one rightmost derivation

D

The language generated by the grammar is undecidable

Show Answer
Correct Answer
A The grammar is ambiguous
B The string abb has two distinct derivations in this grammar
B The string abb has two distinct derivations in this grammar
D The language generated by the grammar is undecidable

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.

Transparent Access on Mindyard

Built for Learners & Educators Alike

Completely free for students. Educators & coaching institutes get 2 months free Pro trial to create tests.

FREE FOR STUDENTS

Practice & Learn Free for Students

Access unlimited practice questions, detailed step-by-step solutions, and exam study materials — completely free for students.

  • Unlimited mock tests & question bank practice
  • Full access to curated study library & formula notes
  • 100% free for students • No credit card required
2 MONTHS FREE TRIAL

Educators & Coaching Institutes

Create and conduct professional online assessments with AI question generation, tab proctoring, and comprehensive batch management.

  • AI question uploader & rapid test generator
  • Anti-cheating tab proctoring & performance reports
  • Full Pro access free for 60 days • No upfront commitment
Discover more resources

You may also like

Mock Tests

View All
  • GATE
  • beginner
  • 3 hours
  • civil engineering

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.

  • GATE
  • beginner
  • 3 hours
  • electronics and communication engineering

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.

Ask AI Tutor
5 left
Q1 View Question & Options
AI Tutor is solving this question...
Reading question context & options...
Ask your own doubt or choose a quick prompt: