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?
Added 2 years ago
Active
Viewed 1370
Ans

 

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 → πœ–)

 



Related Questions