Search code examples
context-free-grammarambiguous-grammar

ContextFreeGrammar ambiguity

given a CFG: S--> aS | Sa | b I can not find any string that can be made from two different pars trees.

the middle state has left recursion but without eliminating that is there any string that shows the CFG ambiguity ? can anyone help plz.

Solution

  • If you apply rules 1, 2 and 3, you get:

    S -> aS -> aSa -> aba

    And if you apply rules 2, 3 and 1, you get the same string:

    S -> Sa -> aSa -> aba

    There's the ambiguity.

    Found a tool that checks ambiguity: http://services.brics.dk/java/grammar/demo.html

    Enter the grammar and check analyze the grammar for potential ambiguity:

    S : "a" S
  | S "a"
  | "b"

    Results:

    *** vertical ambiguity: S[#1] <--> S[#2]
    ambiguous string: "aba"
the grammar is ambiguous!