Re: Ambuguity of CFG

stylez wrote:
Hello,

I know that all simple grammars have the special property that they're
unambigous grammars. I was trying to prove by using the fact that all
DFA/NFA and R.E.s are equiv. to CFG and that they hold a single
solution and therefore create an unambigous grammar. The problem with
this statement is that not all CFG are regular, so I was wondering if
anyone had another insight on how to prove this statement so that I can
say it holds. Thank you in advance.

Dear stylez,

RE's are indeed equivalent to DFA. However, they are not equivalent
to CFG's, since the latter are equivalent to pushdown automata (PDA).
Besides that, there exist ambiguous grammars and grammars that can only be parsed nondeterministically A simple example is the following:

S -> a S a and S -> a

The automaton has to guess when the middle of the inputstring is
reached.

Regards,

Jan Jongejan.
.