Is this unambiguous grammar equivalent?

Question

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:

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?

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$$