Re: PDAs and regular expressions

G'day all.


"pseale" <pseale@ix.netcom.com> writes:


> 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


It intuitively seems regular, since the contents of an LR(k) parser's
stack is at the most regular. However the weakest grammatical model
that I can think of is the regular language over stack _operations_ (as
opposed to stack _symbols_).


Notation:


0 means "empty set"
1 means "null string"
+ means "union"
<i| means "push symbol i"
|i> means "pop symbol i"


The algebra of stack operations is a spinor algebra:


a <i| = <i| a
a |i> = |i> a


<i| |j> = 1, if i = j
= 0, otherwise


\Sum_{i is a stack symbol} |i> <i| = 1


For example, a^n b^n is equivalent to the regular expression:


<0| (a <1|)* (a |1>)* |0>


(The stack symbol 0 corresponds to the bottom of the stack.)


Tha language of stack symbols for this stack is the set of finite-
length prefixes of this expression:


<0| <1|* |1>* |0>


(i.e. the above expression with the terminal symbols removed.)


This set of prefixes is certainly regular in the algebra of stack
operations.


> - if so, has anyone developed an algorithm to compute this.


Working with the language of stack operations may give you a start.
You may like to try finding a way to convert a regular expression
over stack operations into a regular expression over stack symbols.


Cheers,
Andrew Bromage

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