Re: PDAs and regular expressions

24 Oct 1998 01:45:30 -0400

          From comp.compilers

Related articles
PDAs and regular expressions (pseale) (1998-10-22)
Re: PDAs and regular expressions (1998-10-24)
Re: PDAs and regular expressions (1998-10-24)
| List of all articles for this month |

From: <>
Newsgroups: comp.compilers
Date: 24 Oct 1998 01:45:30 -0400
Organization: BLAUPUNKT Werke GmbH
References: 98-10-141 <01bdfd85$e4708920$>
Keywords: parse

> > .....Given a pushdown automaton, I wonder:
> > - what the weakest grammatical model is that can describe the
> > contents of the pushdown tape in any given state (for instance, a
> > expression) and
> > - if so, has anyone developed an algorithm to compute this.
> > Any references would be appreciated.
> > ....

  Hi, Paul,

  the weakest grammatical model for a PDA is a context free grammar (CFG),
  using regular expressions you can only describe (non-)deterministic finite

  I know that there is an algorithm to transform a PDA into CFG and vice
  versa, but for details I'll have to consult some of my computer science
  scripts. If you can wait till tomorrow, please let me know.

  For a quick reference please have a look into the dragon book and its
  literature list.

  Greetings from Hildesheim,


  please email to :

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.