Re: Ambuguity of CFG

jason_box wrote:
Dear Jan,

I believe I remembering hearing something about all s-grammars can be
proven to be unambigoius. It is true that not all CFG's are regular but
I thought there was a thrm or lemma that stated this fact?

Indeed,

Hopcroft and Ullman (Introduction to Automata Theory, Languages
and Computation) say on page 233: We know that the deterministic
PDA's accept a family of languages , the set of deterministic
contexfree languages, lying properly between teh regular
languages and the contextfree languages.

Moreover they say on the same page that the LR grammars generate
exactly the DCFL's.

Regards,

Jan Jongejan.
.

Relevant Pages

  • Re: Regualar Expression Theory
    ... Alan Turing 1950 ... > Model of Computation and Formal Languages, Oxford University Press, ... Are these references related to regular expressions? ...
    (comp.unix.shell)
  • Re: homo(phones/graphs/nyms)
    ... >> think the Dutch and German list of cognates are more or less complete, ... All of these regular. ... in the other languages. ...
    (sci.lang)
  • Re: Regualar Expression Theory
    ... >> Model of Computation and Formal Languages, Oxford University Press, ... > Are these references related to regular expressions? ... equivalences of regular expressions and finite automata ... Tour Of Advanced Topics In Finite Automata ...
    (comp.unix.shell)
  • Re: Intersection of regular expression languages
    ... constructed as a regular expression language? ... There are regular languages and there are ... wondered if there was a more direct construction. ...
    (comp.compilers)
  • Re: A question about two formal languages
    ... You have the right to thinks so, but in fact it is not a homework, ... > What properties distinguish regular languages from context-free ... I tried to use the pumping lemma but didn't get a contradiction, ...
    (comp.theory)