I have a simple context free grammar $(\{A\}, \{(,)\}, R, A)$, which consists of this one production rule:

$A \rightarrow AA\, \vert\, (A)\, \vert\, \epsilon$

I believe this is ambiguous! For example, I can represent "()" like this:

tree1 tree2

I'm sure there are an infinite number of these. I've attempted to make the grammar unambiguous whilst ensuring that the same language is accepted:

  • $A \rightarrow AA\, \vert\, B$

  • $B \rightarrow (C)$

  • $C \rightarrow \epsilon$

How can I be sure that this captures the same language and is no longer ambiguous?


1 Answer 1

  1. Although determining whether grammars are ambiguous is undecidable, in the case where the grammar has a rule of the form

    $$T\to T\;T$$

    then either the grammar is ambiguous or the rule is useless. (Because $T\;T\;T$ can be reduced in two ways.)

  2. Determining the equivalence of two CFGs is also undecidable so there is no general solution to the equivalence question. But you could try to prove that both grammars generate the Dyck language.

  3. A simple deterministic grammar for that language is

    $$S\to \epsilon\mid(\;S\;)\;S$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.