img
Question:
Published on: 3 December, 2024

Consider the grammar:

S → aSbS | bSaS | 𝜖

  • Show that this grammar is ambiguous by constructing two different left most derivations for the sentence abab.
  • Construct the corresponding right most derivations for abab.
  • Construct the corresponding parse tree for abab.
  • What language does this grammar generate?
Answer:

 

Right most derivations for abab:

Case 1:

S → aSbS

  → aSb             (applying S → 𝜖) 

  abSaSb       (applying S → bSaS)

  abSab         (applying S → 𝜖)

  abab            (applying S → 𝜖)  

Case 2:

S → aSbS

  → aSbaSbS     (applying S → aSbS)

  → aSbaSb        (applying S → 𝜖)

  → aSbab         (applying S → 𝜖)

  → abab           (applying S → 𝜖)

 

Random questions