Re: PDAs and regular expressions

bromage@cs.mu.OZ.AU (Andrew Bromage)24 Oct 1998 01:47:10 -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: bromage@cs.mu.OZ.AU (Andrew Bromage) Newsgroups: comp.compilers Date: 24 Oct 1998 01:47:10 -0400 Organization: Computer Science, The University of Melbourne References: 98-10-141 Keywords: parse, theory

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

Post a followup to this message