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.

If I understand you correctly, you can say whatever you want, but
there are context-free grammars that are ambiguous, no matter what
you say. Even worse, there are context-free languages that
are inherently ambiguous, in that it is impossible to find
nonambiguous grammars for them.


Regards,

Rick

.

Relevant Pages

  • Re: Ambuguity of CFG
    ... I know that all simple grammars have the special property that they're ... unambigous grammars. ... Dear stylez, ... since the latter are equivalent to pushdown automata. ...
    (comp.theory)
  • Re: Extended context-free grammar
    ... including e.g. the empty set for both U and T. ... of the operators commonly used to write grammars), ... In context-free grammars, the language is defined by a derivation ...
    (comp.theory)
  • Re: Why context-free?
    ... >> reasons to abandon context-free grammars completely. ... > Recursive descent parsers have a 1-1 correspondence with LL grammars. ... VWG can be viewed as a finite specification of an infinite CFG. ...
    (comp.compilers)
  • Re: example for a real world non context free language
    ... limited to constructing parse trees based on context-free grammars, ... considered part of "semantics". ...
    (comp.theory)
  • Re: Misplaced parenthesis
    ... Context-free grammars define ... that I doubted the equivalence of a RD parser to a grammar. ... Also if you read the Wikipedia definition of type-0 grammars, ... that the Turing machine is only allowed to have a set of finite states as ...
    (comp.lang.pascal.delphi.misc)