CODEWITHSUNDEEP
grammarcontext-free-grammar
DimensionalLensing
DimensionalLensing

Reputation: 31

How to Prove a Grammar is ambiguous? S -> (S)|SS|()

I am rather new to grammars, and was wondering if someone could help me determine using a parse tree how this grammar below is ambiguous? I know that it needs to have two different strings that can be created.

S -> (S)|SS|()

I can def convert it to chomsky normal form and greibach, but ambiguity is perplexing to me with these.

Upvotes: 0

Views: 9290

Answers (1)

rici
rici

Reputation: 241671

The easiest way to prove a grammar ambiguous is to find a sentence with two different parse trees. (Or two different rightmost derivations, which is exactly the same thing. Or, if you prefer, two different leftmost derivations.)

S → S S | X is always ambiguous (for any X), because the sentence X X X has two different parse trees:

         S            S
        / \          / \
       S   S        S   S
      /   / \      / \   \
     X   S   S    S   S   X
         |   |    |   |
         X   X    X   X

Upvotes: 5

Related Questions