The Equational Approach: (2) Infinite Automata and Index Grammars
Mark
Following up on the previous article, suppose you attempt to derive a
finite automaton for the expression given by the recursive system:
S = 1 + a S b S + c S d S (E1)
For instance, evaluating on \A and dA operators on some of the expressions,
you get:
\S = 1, dS = a (S b S) + c (S d S)
\(S b S) = 0, d(S b S) = dS b S + \S db S + \S \b dS
= a (S b S b S) + c (S d S b S) + b S
\(S d S) = 0, d(S d S) = a (S d S b S) + c (S d S d S) + d S
The pattern becomes clear, very quickly, that every expression generated will
have the form:
S yn S ... y2 S y1 S, where y1, y2, ..., yn are all b or d.
So make the following definition:
S() = S
S(x1 x2 ... xn) = S yn S ... y2 S y1 S
where xi = 1 or 2,
and yi = b if xi = 1,
yi = d if xi = 2
Then the following can be derived, where w is an arbitrary word in the
set (1 + 2)*:
\S() = 1
\S(w 1) = 0
\S(w 2) = 0
and
dS() = a S(1) + c S(2)
dS(w 1) = a S(w 1 1) + c S(w 1 2) + b S(w)
dS(w 2) = a S(w 2 1) + c S(w 2 2) + d S(w)
Therefore, the following infinite system of equations results:
S() = 1 + a S(1) + c S(2) (S1)
S(w 1) = b S(w) + a S(w 1 1) + c S(w 1 2)
S(w 2) = d S(w) + a S(w 2 1) + c S(w 2 2)
This is an infinite "finite automaton" -- an infinite set of equations between
in infinite number of expressions. These expressions are more general than
regular expressions (since they do not satisfy any finite system of equations).
They're Context Free Expressions. As with the previous example, it's not too
hard to prove that it's in minimal form, either. As an exercise: plot this
(it's topology is that of an infinite binary tree).
Since this system can also be viewed as a grammar, I'll also use the term
"Index Grammar" interchangeably.
(2.2) Push Down Automaton = Indexed Infinite Automata
There is a direct correspondence between expressions in an index grammar and
states in a push down automaton, along the following lines:
Q(x) <----> state Q, stack contents 0 x
for x in the set (1, 2, ..., m}*, and m the number of stack symbols in the
given PDA (not including the "bottom" symbol, 0).
A precise definition for Index Grammars based on this relation can be
given:
Definition: CS[m] Index Grammar
A CS[m] Index Grammar is a system of equations in q variables,
Q0, Q1, ..., Q{q-1} indexed by the set { 1, ..., m }*, over an input
alphabet X of the forms:
Qi(x c) = a1 Qi1(x x1) + a2 Qi2(x x2) + ...
Qi() = \Qi + a1 Qi1'(x1) + a2 Qi2'(x2) + ...
where
the x's are in the set { 1, ..., m }*.
the a's are in the set X
c = 1, ..., m.
\Qi may be 0 or 1.
The grammar is Deterministic if none of the a's in the right hand side of any
equation is identical to any of the other a's in that equation.
The correspondence between Index Grammars and Push Down Automata is readily
apparent. Let (Q, X, S, d, s, F) be a PDA with:
Q = { 0, 1, ..., q-1 } the state set, q > 0
X: the input alphabet
S = { 0, 1, ..., m } the stack alphabet, m >= 0
s = 0, the start state.
d is a one-many map between (S, Q, X) and (S*, Q)
F, a subset of Q, consisting of all the final states.
Using index notation, this PDA is treated as a system of q equations in the
variables Qi(x), i = 0, ..., q-1, x in the set S*, generated by the d-relation.
For each state, m + 1 equations are generated as follows:
Qi(x c) = sum (a Qi'(x x')) c = 1, ..., m
Qi() = \Qi + sum (a Qi'(x'))
where \Qi = 1 if q is in the set F, \Qi = 0 otherwise. The first sum is of
all the a, i' and x' such that (c, i, a) and (x', i') are in relation d. The
second sum is over all the a, i' and x' such that (0, i, a) and (x', i') are
in relation d.
Because of the transparent nature of this correspondence, I'll use the
term Push Down Automaton and Index Grammar interchangeably -- all an Index
Grammar really is is just a PDA listed in equational form. I'll also use
the terms State and Expression interchangeably for the same reason. The
following property is also clear:
CS[0] = The regular languages
(union m >= 0: CS[m]) = The context free languages
so I'll use the terms CS[m] and context free language (CFL) interchangeably.
The notion of inequalities, discussed in the previous article applies here
equally well. Consequently, you can also talk about derivation sequences as
systems of inequalities. For example, a derivation for the sequence a c d b
using the automaton S1 would proceed like so:
S() >= a S(1)
>= a c S(1 2)
>= a c d S(1)
>= a c d b S()
>= a c d b
Also, as discussed in the previous article, a fundamental property that
comes from this relation is the following:
E = { w in X*: E >= w }
The same properties hold here, as well. In particular, the set corresponding
to (i.e. equal to) the start state is:
Q0() = { w in X*: Q0() >= w }
which is also defined as the LANGUAGE ACCEPTED BY THE PDA.
There is also a fundamental property that characterizes in what sense
these expressions represent solutions to the system of equations:
Least Fixed Point Property:
If the system of equations,
Si(x c) = a1 Si1(x x1) + a2 Si2(x x2) + ...
Si() = d(q) + a1 Si1(x1) + a2 Si2(x2) + ...
is viewed as a system of fixed-point equations between sets Si(x),
then Si(x) >= Qi(x) = { w in X*: Si(x) >= w }. Thus, the Qi(x)'s
are called the Least Fixed Points to the system above.
(2.3) Special Cases
There are 2 special cases worthy of note:
CS[0] -- Finite Automata
The system of equations has the form:
Qi() = \Qi + a1 Qi1'() + a2 Qi2'() + ...
since there are no index symbols.
CS[1] -- Counter Automata
Here, the system has the form:
Qi(x 1) = a1 Qi1(x x1) + a2 Qi2(x x2) + ...
Qi() = \Qi + a1 Qi1'(x1) + a2 Qi2'(x2) + ...
where
the x's are in the set { 1 }*.
the a's are in the set X
c = 1, ..., m.
\Qi may be 0 or 1.
Defining Ci(0) = Qi(), Ci(1) = Qi(1), Ci(2) = Qi(1 1), etc.
this system can also be written as:
Ci(n + 1) = a1 Ci1(n + n1) + a2 Ci2(n + n2) + ...
Ci(0) = \Ci + a1 Ci1'(n1) + a2 Ci2'(n2) + ...
where the n's numbers >= 0.
(2.4) Topological Properties
A CS[m] infinite automaton will look like an infinite m-ary tree of
distinct finite automata, except now that state transitions may pass between
levels. In particular, at the root of the tree will be all the Q()'s. Under
the set of states represented by the Q(x)'s will be the m sets:
{ Qi(x 1): i = 0 ... q-1 } ... { Qi(x m): i = 0 ... q-1 }
corresponding to the m branches of this part of the tree. This number, m,
will be called the DEGREE of the automaton. As you might guess, it is in
general impossible to come up with an algorithm that will find the optimal
degree automaton for a CS[m] language, so that optimization here is a
permanently open field (no matter how good your optimization method is,
there's a better one "out there"). If you don't think this is trivial,
try proving that the language given by the equation
S = x + S S S a
has degree 1 (it does).
If you're up to it, try proving that the language given by the
automaton S1 has degree 2.
(2.5) Deterministic CS[m] < Non-deterministic CS[m].
An inherently ambiguous CFL is one given by the system of equations:
S = U c* + a* V
U = 1 + a U b
V = 1 + b V c
or the set: { a^i b^j c^k: i = j or j = k }. Trying to construct its
minimal automaton, you will find something interesting. Define the
following expressions:
A(n) = U b b^n c* + a* V
B(n) = V c^n
C = c*
D(n, p) = b^n c* + V c^p
E(n) = c^n
then the following can be derived:
S = U c* + a* V
= c* + a U b c* + a a* V + V
= 1 + a (U b c* + a* V) + b (V c) + c (c*)
= 1 + a A(0) + b B(1) + c C
and:
A(n) = 1 + a A(n+1) + b D(n, 1)
B(n) = E(n) + b B(n+1)
C = 1 + c C
D(0, p) = 1 + b B(p+1) + c C
D(n+1,p) = E(p) + b D(n, p+1)
E(0) = 1
E(n+1) = c E(n)
This leads to a very elegant looking infinite automaton for the ambiguous
language (I've kept the lambda transitions in, though they can easily be
removed):
c c c c
[[E(0)]] <- E(1) <--- E(2) <--- E(3) <--- ...
c b b b
+--+ B(1) ---> B(2) ---> B(3) ---> ...
v | ^ ^ ^
[[C]] <---+-----/-+------/--+-----/---+--- ...
| /b | / b | / b |
| / | / | / |
S D(0,1) D(0,2) D(0,3) ...
| ^ ^ ^
a | / b / b / b / b
v / / / /
A(0) D(1,1) D(1,2) D(1,3) ...
| ^ ^ ^
a | / b / b / b / b
v / / / /
A(1) D(2,1) D(2,2) D(2,3) ...
| ^ ^ ^
a | / b / b / b / b
v / / / /
A(2) D(3,1) D(3,2) D(3,3) ...
|
...
Not shown: each of the states in a given column has a lambda transition to the
state, E(n), in the same column.
This system of equations:
S = 1 + a A(0) + b B(1) + c C
A(n) = 1 + a A(n+1) + b D(n, 1)
B(n) = E(n) + b B(n+1)
C = 1 + c C
D(0, p) = 1 + b B(p+1) + c C
D(n+1,p) = E(p) + b D(n, p+1)
E(0) = 1
E(n+1) = c E(n)
is what I call a CS[1, 1] Index Grammar. It differs from the Index Grammars
listed above in that it's not just a m-ary tree, but actually an infinite
2-dimensional grid (a cross product of two 1-ary trees).
(2.6) Concurrent Context Free Languages
The relevant property that distinguishes this automaton from all the
CS[m] automata is therefore its DIMENSION. For this reason, I'll use the
term CS[] in place of CS[0] and the terminology:
C_0 = CS[] = Regular languages: 0-dimensional
C_1 = {union m >= 0: CS[m]} = Context Free Languages: 1-dimensional
It follows from these basic obervations that not all non-deterministic
CS[m] automata can be transformed into one-dimensional determinstic CS[m]
automata.
It's possible to expand on this scheme by making the following definitions:
Definition: CS[m1, m2, ..., mk] Index Language
A CS[m1, m2, ..., mk] language is the intersection of a
CS[m1], CS[m2], ..., CS[mk] language. Its Dimension is k,
and its degree is (m1, m2, ..., mk).
Definition: C_k = (union mi >= 0: CS[m1, ..., mk])
Definition: C*: Concurrent Context Free Language
= union k >= 0: C_k
It trivially follows then that:
Intersection properties:
(1) C_k is the class of all languages derived from
intersecting k context free languages
(2) CS[m1 .... mk n1 ... nl] is the class of languages
derived from intersecting CS[m1...mk] and CS[n1...nl]
languages.
(3) CS[m1 ... mk] is a subset of CS[n1 ... nk]
if and only if mi <= ni.
(4) CS[0 m1 ... mk] = CS[m1 ... mk].
This includes CS[0] = CS[] as a special case.
The only substantial item to prove is that intersecting a CS[] and CS[m]
language results in a CS[m] language. This can be directly shown by
applying the same method used to intersect 2 finite automata here to
intersecting a finite automata with the CS[m] automaton (the Product
Construction). Try the proof as an exercise.