|PDAs and regular expressions email@example.com (pseale) (1998-10-22)|
|Re: PDAs and regular expressions firstname.lastname@example.org (1998-10-24)|
|Re: PDAs and regular expressions email@example.com.OZ.AU (1998-10-24)|
|Date:||24 Oct 1998 01:45:30 -0400|
|Organization:||BLAUPUNKT Werke GmbH|
> > .....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.
> > ....
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
Greetings from Hildesheim,
please email to :
Return to the
Search the comp.compilers archives again.