Re: PDAs and regular expressions

<glenn.langemeier@gmx.net>
24 Oct 1998 01:45:30 -0400

          From comp.compilers
Related articles
PDAs and regular expressions pseale@ix.netcom.com (pseale) (1998-10-22)
Re: PDAs and regular expressions glenn.langemeier@gmx.net (1998-10-24)
Re: PDAs and regular expressions bromage@cs.mu.OZ.AU (1998-10-24)
| List of all articles for this month |
From: <glenn.langemeier@gmx.net>
Newsgroups: comp.compilers
Date: 24 Oct 1998 01:45:30 -0400
Organization: BLAUPUNKT Werke GmbH
References: 98-10-141 <01bdfd85$e4708920$10200285@HI232016.hi.bosch.de>
Keywords: parse

> > .....Given a pushdown automaton, I wonder:
> > - what the weakest grammatical model is that can describe the
possible
> > contents of the pushdown tape in any given state (for instance, a
regular
> > 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
  automata.


  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,


  Glenn.


  please email to :
  glenn.langemeier@gmx.net
  glenn.langemeier@pcm.bosch.de

Post a followup to this message

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