Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
The Untold Story of Formal Languages, part 8
7 views
Skip to first unread message
Mark Hopkins
Aug 9, 1995, 3:00:00 AM8/9/95
to
Solving Context Free Equations
This article is a continuation of the series now titled "The Untold
Story of Formal Languages". The previous 7 parts (revised with minor errors
in the originals corrected):
1. The Spinor Representation of Formal Languages
2. The Formal Language Representation of Algebras
3. The Equational Representation of Formal Languages
4. Context Free Expressions
5. The Algebraic Representation of Formal Languages
6. The Hardest Context Free Language
7. Turing Expressions
are all available by e-mail. If anyone is willing to donate some
FTP space, I can put them there. In the future, this will probably be
compiled into a monograph or even a text.
(1) History
Earlier attempts to construct a representation for Context Free
Languages gave up on trying to find a notation as transparent and elegant
as that used for regular expressions, in one case even stating that such a
representation was probably not to be found at all. In light of what we've
presented here, though, that assessment has proven entirely wrong.
Still, it helps to see what was done before now. What all these
approaches have in common is that they all effectively concentrated on
finding a way to represent the:
Least Fixed Point Operator s:E(s)
Defined as the Least Fixed Point to the equation
s = E(s)
where E(s) is a regular expression involving s. For example, the language
L = { a^n b^n: n >= 0 }
which is represented by the equation:
S = 1 + a S b
has as its solution: s:(1 + a s b). Note that the variable s is therefore
a bound variable. The expression can also be written as t:(1 + a t b).
Note also that the star operator can be represented as:
A* = x:(1 + A x)
Ironically, none of the authors directly used this approach, though
their efforts all amounted to fancy ways to obtain this operator. An
advantage in all three of the approaches is that the form of the expression
directly reflects the grammar it derives from -- which is also its
disadvantage: it does not really eliminate the variables and come up with
a truly variable-free representation. There seems to be an extra step
missing that would for instance allow one to go from
s:(1 + a s b)
to something like:
<0| (a<1|)* (|1>b)* |0>
That's the step that I've presented here with the notation for Context Free
expressions.
(2) The Gruska/McWhirter/Yntema Approach
Two of the first three approaches (Gruska and McWhirter) were published
in the same journal and were essentially the same. The cites are:
Journal of Computer and System Sciences 5, (1971):
J. Gruska, "A Characterization of Context-Free Languages", 353-364
I.P. McWhirter, "Substitution Expressions", 629-637
Both defined the same substitution operator (I'm using a different notation
here than in the references):
L [x = E] = { w1 e1 w2 e2 ... e(n-1) wn:
w1 x w2 x ... x wn is in L,
e1, e2, ..., e(n-1) all in E,
none of the w's contain the symbol x }
Assuming L is represented by the expression L(x), the effect of this
operator is to substitute each x in the expression L(x) by the expression
E. I will also use the following notation:
L(E) = L(x) [x = E]
Example:
(a b + a s b) [s = (a b)*] = a b + a (a b)* b
Amazingly, the fixed point operator can be directly defined in terms of
this operator. Given a language L(x), involving the symbol x, define the
following sequence
L0(x) = L(x)
L_(n+1)(x) = L_n(L_n(x))
Then
x:L(x) = L0(0) + L1(0) + L2(0) + L3(0) + ...
What this does is actually mimic the construction sequence of the least
fixed point solution itself. Neither author, however, directly made this
connection but ended up using essentially this constructions anyhow. As
an exercise, work out the various terms, Ln(x) and Ln(0) for
L(x) = 1 + a x b.
The third approach (Yntema) was published at the same time, in a
different journal:
M.K. Yntema, "Cap Expressions for Context-Free Languages",
Information and Control 8 (1971), 311-318
but actually mimicked all the essential features noted above. This is the
one I will discuss in more detail below.
(3) The Current Approaches
(3.1) The Context-Free Algebra
The approach I took I developed in the late 1988 and 1989 and first
wrote about here in '92. It basically amounts to a two-pronged attack on
the problem. On the one hand, you can capture the automaton behavior of
context free languages by generalizing finite state automata to special cases
of infinite state automata. Both kinds of automata are formally identified
with systems of equations. What characterizes automata corresponding to
Context Free Languages is that they essentially have the topology of an
infinite n-ary tree. One can also consider more general topologies, such as
the Cartesian product of infinite trees, and this leads quite naturally to
2-dimensional infinite automata, 3-dimensional infinite automata, etc.
For instance, the class of languages generated by the closure of the
Context Free Languages under intersection (for which the name Concurrent
Context Free Language has been used often) can be modelled by a finite number
of push down automata running concurrently and so will have infinite
automata characterized as n-dimensional.
The second prong is to directly represent the stack operations of an
automaton by operators. Amazingly, there is a such high degree of formal
similarity to the Bra-Ket notation of Quantum Theory, that the notation
almost screams out at you, demanding to be used. Thus, we arrive at the
notation and formalism for the Context Free Algebra, characterized by the
relations:
Commutativity: <n| x = x <n|, |n> x = x |n>
Orthogonality: <m| |n> = 1 if m = n, 0 else
Completeness: |0> <0| + |1> <1| + ... + |s> <s| = 1
(3.2) The Chomsky-Schuetzenberger Theorem
... provides the ultimate link for the Context-Free expression notation. The
irony is that this is one of the very first theorems stated in Formal
Language Theory and done so at a time when people were actually looking
ways to represent languages by language expressions. Yet the notation I
developed seemed to elude everyone. The theorem states that:
Every context-free language over an alphabet X can be represented in
the form:
L = f(R & D)
where
D is the Dyck language generated by
D0 = { v1, v2, ..., vs, u1, u2, ... us }
for some s >= 0 (if s = 0 then D is empty).
R is a regular subset of (X + D0)
& denotes the intersection operator in ASCII
f is a morphism which erases all the operator symbols.
The language D may be given by the grammar (listed in equational form):
D = 1 + v1 D u1 D + v2 D u2 D + ... vs D us D
The effect of intersecting the regular subset, R, with D is to filter
out all those word in R whose operators do not occur in balanced
pairs. This has the effect of implementing the relations
vm un = 0 if m, n distinct.
The effect of the function f(...) is to cancel out the matching pairs
of operators that remain. This has the effect of implementing the
relations:
vm um = 1
and
Commutativity: vn x = x vn, un x = x un
The link to the Context Free expression notation is achieved by way
of the correspondences:
vn <--> <n| and un <--> |n>
We can then achieve the same effect with respect to the Context-Free
Algebra by introducing two new operators, <0| and |0> and writing
L = <0| R |0>
where R is now a regular expression over the Context-Free algebra. Any
unpaired operator of any word in R will bump into one of the 0-operators
and the word will end up being filtered out. The result is now that
L is not just represented by the corresponding expression, it is EQUAL
to it!
(3.3) Extended Notation
An extended notation that I developed late in 1993 involved the use
of the Interleave Product, defined as follows:
A ^ B = { w0 x1 w1 ... xn wn: w0 w1 ... wn in A, x1 ... xn in B }
which is the set of all interleavings of words from A with words from B.
With respect to this operator, the left-quotient operator (also known
in the literature as the derivative operator) actually behaves like a
derivative. It is defined as follows:
x\A = { w: x w is a word in A }
and satisfies the property:
x\(A ^ B) = (x\A) ^ B + A ^ (x\B) (*)
There is an even nicer relation between the automaton for A ^ B and
those for A and for B -- essentially the former is the Cartesian
Product of the latter two. This actually follows from the property (*)
above. For instance, consider the two Dyck languages given by the
respective equations:
D(p, q) = 1 + p D q D
D(b, d) = 1 + b D d D
their corresponding infinite state automata will be:
-- p --> -- p --> -- p --> ...
--> [[0]] [1] [2] [3]
<-- q -- <-- q -- <-- q -- ...
and
-- b --> -- b --> -- b --> ...
--> [[0]] [1] [2] [3]
<-- d -- <-- d -- <-- d -- ...
The automaton for the language D(p, q) x D(b, d) will be:
p p p
----> ----> ---->
--> [[0,0]] [0,1] [0,2] ...
| ^ <---- | ^ <---- | ^ <----
| | q | | q | | q
b | | d b | | d b | | d
| | p | | p | | p
v | ----> v | ----> v | ---->
[1,0] [1,1] [1,2] ...
| ^ <---- | ^ <---- | ^ <----
| | q | | q | | q
b | | d b | | d b | | d
| | p | | p | | p
v | ----> v | ----> v | ---->
[2,0] [2,1] [2,2] ...
| ^ <---- | ^ <---- | ^ <----
| | q | | q | | q
...
In the second article of the series, I mistakenly stated that this
was the automaton for the intersection of D(p, q) and D(b, d).
Actually D(p, q) ^ D(b, d) is the intersection:
(D(p, q) ^ (b + d)*) & ((p + q)* ^ D(b, d))
You can define an operator that is somewhat analogous to the
Kleene Star operator:
A! = 1 + A + A^A + A^A^A + ...
Then the Dyck language can actually be expressed in closed form as:
D(p, q) = (pq)!
and the Dyck language D, of the Chomsky-Schuetzenberger Theorem as:
D = (v1 u1 + v2 u2 + ... + vs us)!
The language represented in the automaton above is then:
(pq)! ^ (bd)!
If one introduces the notation
x~A = { w: w is derived from a word w' in A by removing all its x's }
for x in the alphabet X
then one arrives at a second notation with the ability to express any
Context-Free language via the Chomsky-Schuetzenberger Theorem and more.
For instance, the language given by the equation
S = 1 + a S b
will have the following representations and solutions:
S = f((v1 a)* (b u1)* & D(v1, u1))
S = u1~v1~( (v1 a)* (b u1)* & (v1 u1)! )
or
S = (0| (<1| a)* (b |1>)* |0>
(4) The Fixed Point Operator
The Yntema approach can the closest to directly recognizing the
fundamental role the Fixed Point Operator plays. This is the one that
will be discussed in detail here.
Yntema's approach to solving systems of equations representing context
free grammars was analogous to the logical sequence:
3x = 4, therefore x = 4/3
My approach, on the other hand, is analogous to the sequence:
3x = 4, therefore x = 4/3 = 1.333...
What Yntema basically did was define the fix-point operator --
a:P(a) = least fixed point solution to (a = P(a))
(calling it a Cap Expression) by using the same substitution idea--
a:P(a) is defined as the language obtained as the
limit of the process:
* L_0 = P(a)
* L_{n+1} is the set of words of the form
w0 p1 w1 ... pn wn
such that none of the w's contain any instances
of the symbol a, each of the p's is an element of
P(a), and the word w0 a w1 ... a wn is in L_n.
The article tended to obfuscate this one simple detail that the notation
basically amounted to a fancy way of writing a context free grammar (till
the very end when this feature was acknowledged), but in fact that's all that
was accomplished. But the step might considered to be a crucial first step,
somewhat analogous to deriving the intermediate form 4/3 before the decimal
1.333...
To show how the notation applies, consider the grammar stated in equational
form:
S = N V + S P
V = v N
P = p N
N = n + N P
Yntema's solution method would proceed like so:
N = n + N P
--> N = x:(n + x P)
P = p N
= p x:(n + x P)
--> P = y:(p x:(n + x y))
V = v x:(n + x P)
where P is as given above
S = N V + S P
= x:(n + x P) v x:(n + x P) + S P
--> S = z:(N v N + S P)
where P = y:(p x:(n + x y))
and N = x:(n + x P)
= x:(n + x y:(p x:(n + x y)))
Yntema's main theorem states that all context free languages can be
generated from the fixed point operation, concatenation and union. All
that this is really saying is that CFL's can be specified by systems
of equations whose right hand sides are finite unions of concatenations:
in other words, Context Free Grammars.
(5) Some Basic Properties of the Least Fixed Point Operator
This is as unsatisfactory as saying that "4/3 is the solution to 3x = 4"
when what you really wanted to say is that the solution is the repeating
decimal 1.333... It may suprise you, in fact, to realise that the language
given above is just the regular language:
S = n (p n)* v n (p n)*
What was not properly understood back then (and to a large extent not even
now) is that the operators { union, concatenation, Kleene star } ARE
sufficient to represent all languages. The limitation is not on the operator
set but on the algebra it is used with!
So let's start out with that premise. In fact, let's derive a couple
short-cuts that will save the day.
Lemma 1: N:a = a if a contains no instances of N
Proof:
Trivial.
Lemma 2: N:(a + N b + c N + N d N) = N:(c* a b* (d c* a b*)*)
where a, b, c, d may contain instances of N, but a, c do not
begin in N, and a, b do not end in N
Proof:
Exercise :)
This lemma is stated so that we can eliminate all the left and right
recursions in an equation. The only recursive appearances of a variable
will then be embedded somewhere in the middle of a term. Note some
special cases of this lemma:
Corollaries:
N:(a + N d N) = N:(a (d a)*)
N:(a + N b) = N:(a b*)
N:(a + c N) = N:(c* a)
N:(a + N) = N:a
N:(a + N N) = N:(a a*)
Proof:
Substitute appropriate values (0 or 1) for the appropriate variables
a, b, c and d in Lemma 2.
Exercise: Derive all the interesting corollaries of Lemma 2.
Now let's solve the system posed before. From
S = N V + S P
V = v N
P = p N
N = n + N P
we get:
N = x:(n + x P) = n P*
P = p n P* = x:(p n x*)
V = v N = v n P*
S = z:(N V + z P) = N V P*
= n P* v n P* P* = n P* v n P*
Now the second equation is tricky, but one can write:
x = p n x* = p n (1 + x* x)
= p n + p n x* x = p n + x x
So lo and behold, by one of our Corollaries, we get:
x = x:(p n + x x) = x:(p n (p n)*)
= p n (p n)*, by Lemma 1
Thus:
P = p n (p n)*
and P* = (p n (p n)*)* = (p n)*
so
S = n (p n)* v n (p n)*
Now that was too easy. What if the analogous equation were like:
4x^3 + 3x = 1
Well, as you probably already know:
sinh(3A) = 4 sinh^3(A) + 3 sinh(A)
so that
sinh(3A) = 1
cosh(3A) = sqrt(1 + sinh(3A)^2) = sqrt(2)
so
exp(3A) = cosh(3A) + sinh(3A) = sqrt(2) + 1
exp(-3A) = cosh(3A) - sinh(3A) = sqrt(2) - 1
so
exp(A) = (sqrt(2) + 1)^(1/3) * Omega
exp(A) = (sqrt(2) - 1)^(1/3) / Omega
sinh(A) = (exp(A) - exp(-A))/2
where Omega is one of the cube roots of 1. So this is also the solution
for x. You could probably solve any polynomial equation using trig
functions, hyperbolic functions and their inverses.
But the solution is not a repeating decimal. So things aren't so easy
anymore. Analogously, the solution to a fixed-point equation doesn't have to
be a regular expression. This apparent limitation would have been the end of
the story if we had been living in the 20th Century. But ... um... slippage
in the time stream. Oops.
(6) Some Basic Properties of the Context Free Algebra
For what follows let's state a definition and a couple lemmas:
Definition: Let E be a regular expression over X union D, where
D = { |0>, |1>, ..., |s>, <0|, <1|, ..., <s| }
subject to the relations
<m| |n> = 1 if m = n
= 0 else (R)
|0><0| + |1><1| + ... + |s><s| = 1
Then E is called operator-free if every word in E can be
reduced to a word in X* using the relations E.
Lemma 3: If E is operator-free then
<n| E = E <n| and |n> E = E |n>
Proof:
Let <n| w be a word in <n| E, where w is a word in E. Then w = w' for
some word w' in X*. Thus <n| w = <n| w' = w' <n| = w <n|, since <n|
commutes with all the symbols in X. A similar proof follows for all the
other cases.
Lemma 4: E is operator-free if and only if
E = <n| E' |n>, where neither <n| nor |n> occur in E'.
Proof:
The forward implication is trivial, let E' = E. So for the backward
implication let E' be given as above, let n be any number from 0 to s and
let <n| w |n> be a word in E = <n| E' |n> where w is a word in E' containing
no occurrences of |n> or <n|.
If the operators in w do not occur in balanced pairs, there will either
be a spare |m> which can be brought out to the left end of E', or a spare
<m| which can be brought out to the right end of E', where m is distinct
from n. In either case, you'll get a cancellation with one of the
bounding n-operators in <n| E' |n>.
On the other hand if the operators in w do occur in balanced pairs,
then they will cancel and w will reduce to some w' in X*.
Keep in mind that since we're working in a partially ordered semi-ring
which is an extension of the semi-ring of regular expressions over X, 0 is not
a word, but merely the additive identity of the semi-ring. A word w is
considered to be "in E" iff E = E + w. A further discussion of the algebraic
preliminaries can be found in the 5th part of this series ("The Algebraic
Representation of Formal Languages").
(7) Solving the Least Fixed Point Equation
So, back to the original issue, what if the grammar looked like this:
S = N V a + S P b
V = v N c
P = p N d
N = n e + N P f
where the extra symbols might even be construed as tree-building operations.
This system can still be solved, but now using Context Free expressions.
First, the equation for N still yields the same type of solution:
N = <x: n e + x P f> = n e (P f)*
But for P, the result is no longer regular. In fact, you now have the
following equation:
P = p N d
= p n e (P f)* d
For each occurrence of P on the right hand side, note the set of terms which
may follow it. After P will come f, an undetermined number of more (P f)'s
and then d. The context following P is thus: f (P f)* d.
Assign each distinct context a pair of operators <n| and |n> where the
corresponding number, n, is numbered starting at 1. Define the term:
PF = sum (|n> C_n PF) + |0>
where C_n is the nth follow context. Here, this definition amounts to
saying: let
PF = |1> C_1 PF + |0>
where
C_1 = f (P f)* d
So now define the term PS = P PF. Then we may write:
<0| PS = <0| P (|1> C_1 PF + |0>)
= <0| P |1> C_1 PF + <0| P |0>
= 0 C_1 PF + P by Lemma 3
= P
<1| PS = <1| P |1> C_1 PF + <1| P |0>
= P C_1 PF + 0 by Lemma 3
= P f (P f)* d PF
and
PS = p n e (P f)* d PF
= p n e Q
where Q = (P f)* d PF
and
Q = P f (P f)* d PF + d PF
= <1| PS + d PF
= <1| p n e Q + d |1> C_1 PF + d |0>
= <1| p n e Q + d |1> f Q + d |0>
Thus we arrive at a right-linear system of equations for P:
P = <0| PS
PS = p n e Q
Q = <1| p n e Q + d |1> f Q + d |0>
whose solution is derived by substitution:
P = <0| p n e (<1| p n e + |1> d f)* d |0>
noting the commutation relation |1> d = d |1>. With a little
algebra this could be reduced further to:
P = <0| (<1| p n e + |1> d f)* d |1> |0>
but it doesn't really matter. The point is that a closed form solution
has been found and it is of the form:
P = <0| R |0>
where R is a regular expression over the alphabet X = {a,b,c,d,e,f,n,p,v}
and operator set {|1>,<1|}.
So now everything else is routine:
V = v N c
S = N V a + S P b
--> S = <z: N V a + z P b>
= N V a (P b)*
which after substitution for N and V yields:
S = n e (P f)* v n e (P f)* c a (P b)*
Now (P f)* can be reduced to the for <0| ... |0> by noting that:
(P f)* = (<0| R |0> f)*
= 1 + <0| R |0> f (<0| R |0> f)*
= 1 + <0| R f |0> (<0| R f |0>)*
= 1 + <0| R f (|0> <0| R f)* |0>
= <0| |0> + <0| (|0> <0| R f) (|0> <0| R f)* |0>
= <0| (|0> <0| R f)* |0>
Or
(P f)* = <0| (p0 R f)* |0>, where p0 = |0><0|
Thus
S = n e <0| (p0 R f)* |0> v n e <0| (p0 R f)* |0> c a <0| (p0 R b)* |0>
= <0| n e (p0 R f)* p0 v n e (p0 R f)* p0 c a (p0 R b)* |0>
Or with a little further manipulation this can be reduced to:
S = <0| n e (p0 R f)* v n e (p0 R f)* c a (p0 R b)* |0>
where
p0 = |0><0|
R = (<1| p n e + |1> d f)* d |1>
which is only one pair of context symbols away from being a regular language.
This then provides the archetypical example of how to solve Context
Free Equations in closed form. Given an equation
x = P = P(x, y1, ..., yn)
where P(x) is a regular expression of y1, ..., yn and where each of the
y's is operator-free. First, to be consistent, we may eliminate all the
uccorrences of <0| and |0> by rewriting each of the y's that have the form
<0| y' |0> as <m| y' |m> where m is the smallest number larger than 0 for
which no m-operators occur amongst the y's. This is actually an application
of Lemma 4.
We may apply Lemma 1 if P does not actually involve any occurrences of x.
Otherwise we can apply Lemma 2 to make sure there are no left or right
recursions in x. Distinguish and number all the contexts associated each
occurrence of x in P and call them C_1, C_2, ..., C_s where there are s
contexts. There may be new contexts that appear in each of the C's that
do not occur in P. Add these to the enumeration and whatever new contexts
are spawned as a result and so on. The process will eventually terminate
since the terms get successively smaller.
Define
x_F = |0> + |1> C_1 x_F + ... + |s> C_s x_F
and
x_S = x x_F.
Then
<0| x_S = <0| x x_F
= <0| x |0> + sum (<0| x C_2 x_F |i>)
= x + 0
= x
and
<i| x_S = <i| x x_F
= <i| x |0> + sum (<i| x C_2 x_F |i>)
= 0 + <i| x C_i x_F |i>
= x C_i x_F
But we may also write
x_S = x x_F = P(x, y1, ..., yn) x_F
Since C_i was derived from the term P, every occurrence of x in C_i will
have a context associated with it. We may thus write
C_i = ai + ai1 x C_1 + ... + ais x C_s
where none of the a's contain any occurrences of x. Thus
C_i x_F = ai x_F + ai1 x C_1 x_F + ... + ais x C_n x_F
= ai x_F + ai1 <1| x_S + ... + ais <s| x_S
where the a's are regular expressions in (y1, ..., yn) containing no
occurrences of x. The term P x_F may be written in a similar fashion. Thus
the system of equations
x = <0| x_S
x_S = P x_F
x_F = |0> + |1> C_1 x_F + ... + |n> C_n x_F
will ultimately reduce to a series of right-linear equations of the
form:
x = <0| x_S
x_S = p x_F + p1 <1| x_S + ... + ps <s| x_S
x_F = |0> + (|1> a1 + |2> a2 + ... + |s> as) x_F
+ sum |i> aij <j| x_S
whose solutions must therefore be of the form:
x = <0| x_S
x_S = A* p x_F
x_F = B* |0> + B* C x_S
= B* |0> + B* C A* p x_F
Thus
x_F = (B* C A* p)* B* |0>
x_S = A* p (B* C A* p)* B* |0>
A* p B* (C* A* p B*)* |0>
and
x = <0| A* p B* (C* A* p B*)* |0>
which has the form:
x = <0| R |0>
for some regular expression in the y's and over the operator set
{ <1|, <2|, ..., <s|, |1>, |2>, ..., |s> }.
Given a system of equations, we may solve one equation this way
and then substitute the solution in the remaining equations to arrive
at a smaller system. Applying the process iteratively will lead to
a closed form solution.
(8) A Couple More Examples
(8.1) A simple expression grammar
Consider the grammar given by the system:
S = E q E a + o S c
E = u E + E b E + l E r + x
where S is the main variable. Solving the equation for E first, we
get:
E = (u E + l E r + x) (b (u E + l E r + x))*
by Lemma 2. There are only two distinct contexts:
C_1 = Q = (b (u E + l E r + x))*
and C_2 = r Q
associated respectively with the occurrences of E in u E, and with the
occurrences of l E r. Neither of the contexts C_1 nor C_2 will spawn
new contexts so our process is complete. We may thus write:
E = <0| E_S
E_S = (u E + l E r + x) Q E_F
E_F = |0> + |1> Q E_F + |2> r Q E_F
and carry out the following reductions:
Q E_F = (b (u E + l E r + x))* E_F
= E_F + b (u E + l E r + x) Q E_F
= E_F + b E_S
= |0> + |1> Q E_F + |2> r Q E_F + b E_S
E_S = u E Q E_F + l E r Q E_F + x Q E_F
= u <1| E_S + l <2| E_S + x Q E_F
= U x Q E_F
where
U = (u <1| + l <2|)*
Thus
Q E_F = (|1> + |2> r + b U x)* |0>
and
E = <0| U x Q E_F
= <0| U x V |0>
where
V = (|1> + |2> r + b U x)*
U = (u <1| + l <2|)*
The second equation may then be solved in closed form:
S = E q E a + o S c
which leads to:
S = <0| S_S
S_F = |0> + |1> c S_F
S_S = S S_F
which leads to the reductions:
S_F = (|1> c)* |0>
S_S = E q E a S_F + o S c S_F
= E q E a S_F + o <1| S_S
S_S = (o <1|)* E q E a S_F
= (o <1|)* E q E a (|1> c)* |0>
Thus
S = <0| (o <1|)* E q E a (|1> c)* |0>
If we change to 0-operators in E to <3| and |3>, we may then write:
S = <0| (o <1|)* E q E a (|1> c)* |0>
where
V = (|1> + |2> r + b U x)*
U = (u <1| + l <2|)*
E = <3| U x V |3>
Making the indicated substitutions for U, V and E will yield the
closed-form solution, though it will be a bit unwieldy. In actual
practice it's more useful to stop the process once a right-linear system of
equations is derived and then call THAT the solution. The system will bear a
direct connection to a push down automaton and therefore have more immediate
application. The regular expression, itself, is really only for purposes of
exhibition.
(8.2) A tricky grammar
Consider the language given by the equation
S = a + S S S b
Applying Lemma 2 results in the equation:
S = a (S S b)*
whose two contexts are:
C_1 = S b Q
and C_2 = b Q
where Q = (S S b)*
Thus
S = <0| S_S
S_F = |0> + |1> S b Q S_F + |2> b Q S_F
S_S = S S_F = a Q S_F
This reduces to:
Q S_F = S_F + S S b Q S_F
= S_F + <1| S_S
S_F = |0> + |1><2| S_S + |2> b Q S_F
S_S = a Q S_F
Thus
Q S_F = |0> + |1><2| S_S + |2> b Q S_F + <1| S_S
= |0> + (|1><2| + <1|) a Q S_F + |2> b Q S_F
= ( (|1><2| + <1|) a + |2> b )* |0>
and
S = <0| a Q S_F
= <0| a (v a + u b)* |0>
where
v = |1><2| + <1|
u = |2>
As it turns out, the subalgebra generated by { <0|, |0>, u, v } is
isomorphic to that generated by { <0|, |0>, <1|, |1> } by the
correspondence:
<0| <--> <0|
|0> <--> |0>
v <--> <1|
u <--> |1>|1>
In fact, v u = |1> and v |1> = 1. Thus, we may write
S = <0| a (<1| a + |1>|1> b)* |0>
In effect, v behaves like the square root of u's adjoint, <2|.
This article is a continuation of the series now titled "The Untold
Story of Formal Languages". The previous 7 parts (revised with minor errors
in the originals corrected):
1. The Spinor Representation of Formal Languages
2. The Formal Language Representation of Algebras
3. The Equational Representation of Formal Languages
4. Context Free Expressions
5. The Algebraic Representation of Formal Languages
6. The Hardest Context Free Language
7. Turing Expressions
are all available by e-mail. If anyone is willing to donate some
FTP space, I can put them there. In the future, this will probably be
compiled into a monograph or even a text.
(1) History
Earlier attempts to construct a representation for Context Free
Languages gave up on trying to find a notation as transparent and elegant
as that used for regular expressions, in one case even stating that such a
representation was probably not to be found at all. In light of what we've
presented here, though, that assessment has proven entirely wrong.
Still, it helps to see what was done before now. What all these
approaches have in common is that they all effectively concentrated on
finding a way to represent the:
Least Fixed Point Operator s:E(s)
Defined as the Least Fixed Point to the equation
s = E(s)
where E(s) is a regular expression involving s. For example, the language
L = { a^n b^n: n >= 0 }
which is represented by the equation:
S = 1 + a S b
has as its solution: s:(1 + a s b). Note that the variable s is therefore
a bound variable. The expression can also be written as t:(1 + a t b).
Note also that the star operator can be represented as:
A* = x:(1 + A x)
Ironically, none of the authors directly used this approach, though
their efforts all amounted to fancy ways to obtain this operator. An
advantage in all three of the approaches is that the form of the expression
directly reflects the grammar it derives from -- which is also its
disadvantage: it does not really eliminate the variables and come up with
a truly variable-free representation. There seems to be an extra step
missing that would for instance allow one to go from
s:(1 + a s b)
to something like:
<0| (a<1|)* (|1>b)* |0>
That's the step that I've presented here with the notation for Context Free
expressions.
(2) The Gruska/McWhirter/Yntema Approach
Two of the first three approaches (Gruska and McWhirter) were published
in the same journal and were essentially the same. The cites are:
Journal of Computer and System Sciences 5, (1971):
J. Gruska, "A Characterization of Context-Free Languages", 353-364
I.P. McWhirter, "Substitution Expressions", 629-637
Both defined the same substitution operator (I'm using a different notation
here than in the references):
L [x = E] = { w1 e1 w2 e2 ... e(n-1) wn:
w1 x w2 x ... x wn is in L,
e1, e2, ..., e(n-1) all in E,
none of the w's contain the symbol x }
Assuming L is represented by the expression L(x), the effect of this
operator is to substitute each x in the expression L(x) by the expression
E. I will also use the following notation:
L(E) = L(x) [x = E]
Example:
(a b + a s b) [s = (a b)*] = a b + a (a b)* b
Amazingly, the fixed point operator can be directly defined in terms of
this operator. Given a language L(x), involving the symbol x, define the
following sequence
L0(x) = L(x)
L_(n+1)(x) = L_n(L_n(x))
Then
x:L(x) = L0(0) + L1(0) + L2(0) + L3(0) + ...
What this does is actually mimic the construction sequence of the least
fixed point solution itself. Neither author, however, directly made this
connection but ended up using essentially this constructions anyhow. As
an exercise, work out the various terms, Ln(x) and Ln(0) for
L(x) = 1 + a x b.
The third approach (Yntema) was published at the same time, in a
different journal:
M.K. Yntema, "Cap Expressions for Context-Free Languages",
Information and Control 8 (1971), 311-318
but actually mimicked all the essential features noted above. This is the
one I will discuss in more detail below.
(3) The Current Approaches
(3.1) The Context-Free Algebra
The approach I took I developed in the late 1988 and 1989 and first
wrote about here in '92. It basically amounts to a two-pronged attack on
the problem. On the one hand, you can capture the automaton behavior of
context free languages by generalizing finite state automata to special cases
of infinite state automata. Both kinds of automata are formally identified
with systems of equations. What characterizes automata corresponding to
Context Free Languages is that they essentially have the topology of an
infinite n-ary tree. One can also consider more general topologies, such as
the Cartesian product of infinite trees, and this leads quite naturally to
2-dimensional infinite automata, 3-dimensional infinite automata, etc.
For instance, the class of languages generated by the closure of the
Context Free Languages under intersection (for which the name Concurrent
Context Free Language has been used often) can be modelled by a finite number
of push down automata running concurrently and so will have infinite
automata characterized as n-dimensional.
The second prong is to directly represent the stack operations of an
automaton by operators. Amazingly, there is a such high degree of formal
similarity to the Bra-Ket notation of Quantum Theory, that the notation
almost screams out at you, demanding to be used. Thus, we arrive at the
notation and formalism for the Context Free Algebra, characterized by the
relations:
Commutativity: <n| x = x <n|, |n> x = x |n>
Orthogonality: <m| |n> = 1 if m = n, 0 else
Completeness: |0> <0| + |1> <1| + ... + |s> <s| = 1
(3.2) The Chomsky-Schuetzenberger Theorem
... provides the ultimate link for the Context-Free expression notation. The
irony is that this is one of the very first theorems stated in Formal
Language Theory and done so at a time when people were actually looking
ways to represent languages by language expressions. Yet the notation I
developed seemed to elude everyone. The theorem states that:
Every context-free language over an alphabet X can be represented in
the form:
L = f(R & D)
where
D is the Dyck language generated by
D0 = { v1, v2, ..., vs, u1, u2, ... us }
for some s >= 0 (if s = 0 then D is empty).
R is a regular subset of (X + D0)
& denotes the intersection operator in ASCII
f is a morphism which erases all the operator symbols.
The language D may be given by the grammar (listed in equational form):
D = 1 + v1 D u1 D + v2 D u2 D + ... vs D us D
The effect of intersecting the regular subset, R, with D is to filter
out all those word in R whose operators do not occur in balanced
pairs. This has the effect of implementing the relations
vm un = 0 if m, n distinct.
The effect of the function f(...) is to cancel out the matching pairs
of operators that remain. This has the effect of implementing the
relations:
vm um = 1
and
Commutativity: vn x = x vn, un x = x un
The link to the Context Free expression notation is achieved by way
of the correspondences:
vn <--> <n| and un <--> |n>
We can then achieve the same effect with respect to the Context-Free
Algebra by introducing two new operators, <0| and |0> and writing
L = <0| R |0>
where R is now a regular expression over the Context-Free algebra. Any
unpaired operator of any word in R will bump into one of the 0-operators
and the word will end up being filtered out. The result is now that
L is not just represented by the corresponding expression, it is EQUAL
to it!
(3.3) Extended Notation
An extended notation that I developed late in 1993 involved the use
of the Interleave Product, defined as follows:
A ^ B = { w0 x1 w1 ... xn wn: w0 w1 ... wn in A, x1 ... xn in B }
which is the set of all interleavings of words from A with words from B.
With respect to this operator, the left-quotient operator (also known
in the literature as the derivative operator) actually behaves like a
derivative. It is defined as follows:
x\A = { w: x w is a word in A }
and satisfies the property:
x\(A ^ B) = (x\A) ^ B + A ^ (x\B) (*)
There is an even nicer relation between the automaton for A ^ B and
those for A and for B -- essentially the former is the Cartesian
Product of the latter two. This actually follows from the property (*)
above. For instance, consider the two Dyck languages given by the
respective equations:
D(p, q) = 1 + p D q D
D(b, d) = 1 + b D d D
their corresponding infinite state automata will be:
-- p --> -- p --> -- p --> ...
--> [[0]] [1] [2] [3]
<-- q -- <-- q -- <-- q -- ...
and
-- b --> -- b --> -- b --> ...
--> [[0]] [1] [2] [3]
<-- d -- <-- d -- <-- d -- ...
The automaton for the language D(p, q) x D(b, d) will be:
p p p
----> ----> ---->
--> [[0,0]] [0,1] [0,2] ...
| ^ <---- | ^ <---- | ^ <----
| | q | | q | | q
b | | d b | | d b | | d
| | p | | p | | p
v | ----> v | ----> v | ---->
[1,0] [1,1] [1,2] ...
| ^ <---- | ^ <---- | ^ <----
| | q | | q | | q
b | | d b | | d b | | d
| | p | | p | | p
v | ----> v | ----> v | ---->
[2,0] [2,1] [2,2] ...
| ^ <---- | ^ <---- | ^ <----
| | q | | q | | q
...
In the second article of the series, I mistakenly stated that this
was the automaton for the intersection of D(p, q) and D(b, d).
Actually D(p, q) ^ D(b, d) is the intersection:
(D(p, q) ^ (b + d)*) & ((p + q)* ^ D(b, d))
You can define an operator that is somewhat analogous to the
Kleene Star operator:
A! = 1 + A + A^A + A^A^A + ...
Then the Dyck language can actually be expressed in closed form as:
D(p, q) = (pq)!
and the Dyck language D, of the Chomsky-Schuetzenberger Theorem as:
D = (v1 u1 + v2 u2 + ... + vs us)!
The language represented in the automaton above is then:
(pq)! ^ (bd)!
If one introduces the notation
x~A = { w: w is derived from a word w' in A by removing all its x's }
for x in the alphabet X
then one arrives at a second notation with the ability to express any
Context-Free language via the Chomsky-Schuetzenberger Theorem and more.
For instance, the language given by the equation
S = 1 + a S b
will have the following representations and solutions:
S = f((v1 a)* (b u1)* & D(v1, u1))
S = u1~v1~( (v1 a)* (b u1)* & (v1 u1)! )
or
S = (0| (<1| a)* (b |1>)* |0>
(4) The Fixed Point Operator
The Yntema approach can the closest to directly recognizing the
fundamental role the Fixed Point Operator plays. This is the one that
will be discussed in detail here.
Yntema's approach to solving systems of equations representing context
free grammars was analogous to the logical sequence:
3x = 4, therefore x = 4/3
My approach, on the other hand, is analogous to the sequence:
3x = 4, therefore x = 4/3 = 1.333...
What Yntema basically did was define the fix-point operator --
a:P(a) = least fixed point solution to (a = P(a))
(calling it a Cap Expression) by using the same substitution idea--
a:P(a) is defined as the language obtained as the
limit of the process:
* L_0 = P(a)
* L_{n+1} is the set of words of the form
w0 p1 w1 ... pn wn
such that none of the w's contain any instances
of the symbol a, each of the p's is an element of
P(a), and the word w0 a w1 ... a wn is in L_n.
The article tended to obfuscate this one simple detail that the notation
basically amounted to a fancy way of writing a context free grammar (till
the very end when this feature was acknowledged), but in fact that's all that
was accomplished. But the step might considered to be a crucial first step,
somewhat analogous to deriving the intermediate form 4/3 before the decimal
1.333...
To show how the notation applies, consider the grammar stated in equational
form:
S = N V + S P
V = v N
P = p N
N = n + N P
Yntema's solution method would proceed like so:
N = n + N P
--> N = x:(n + x P)
P = p N
= p x:(n + x P)
--> P = y:(p x:(n + x y))
V = v x:(n + x P)
where P is as given above
S = N V + S P
= x:(n + x P) v x:(n + x P) + S P
--> S = z:(N v N + S P)
where P = y:(p x:(n + x y))
and N = x:(n + x P)
= x:(n + x y:(p x:(n + x y)))
Yntema's main theorem states that all context free languages can be
generated from the fixed point operation, concatenation and union. All
that this is really saying is that CFL's can be specified by systems
of equations whose right hand sides are finite unions of concatenations:
in other words, Context Free Grammars.
(5) Some Basic Properties of the Least Fixed Point Operator
This is as unsatisfactory as saying that "4/3 is the solution to 3x = 4"
when what you really wanted to say is that the solution is the repeating
decimal 1.333... It may suprise you, in fact, to realise that the language
given above is just the regular language:
S = n (p n)* v n (p n)*
What was not properly understood back then (and to a large extent not even
now) is that the operators { union, concatenation, Kleene star } ARE
sufficient to represent all languages. The limitation is not on the operator
set but on the algebra it is used with!
So let's start out with that premise. In fact, let's derive a couple
short-cuts that will save the day.
Lemma 1: N:a = a if a contains no instances of N
Proof:
Trivial.
Lemma 2: N:(a + N b + c N + N d N) = N:(c* a b* (d c* a b*)*)
where a, b, c, d may contain instances of N, but a, c do not
begin in N, and a, b do not end in N
Proof:
Exercise :)
This lemma is stated so that we can eliminate all the left and right
recursions in an equation. The only recursive appearances of a variable
will then be embedded somewhere in the middle of a term. Note some
special cases of this lemma:
Corollaries:
N:(a + N d N) = N:(a (d a)*)
N:(a + N b) = N:(a b*)
N:(a + c N) = N:(c* a)
N:(a + N) = N:a
N:(a + N N) = N:(a a*)
Proof:
Substitute appropriate values (0 or 1) for the appropriate variables
a, b, c and d in Lemma 2.
Exercise: Derive all the interesting corollaries of Lemma 2.
Now let's solve the system posed before. From
S = N V + S P
V = v N
P = p N
N = n + N P
we get:
N = x:(n + x P) = n P*
P = p n P* = x:(p n x*)
V = v N = v n P*
S = z:(N V + z P) = N V P*
= n P* v n P* P* = n P* v n P*
Now the second equation is tricky, but one can write:
x = p n x* = p n (1 + x* x)
= p n + p n x* x = p n + x x
So lo and behold, by one of our Corollaries, we get:
x = x:(p n + x x) = x:(p n (p n)*)
= p n (p n)*, by Lemma 1
Thus:
P = p n (p n)*
and P* = (p n (p n)*)* = (p n)*
so
S = n (p n)* v n (p n)*
Now that was too easy. What if the analogous equation were like:
4x^3 + 3x = 1
Well, as you probably already know:
sinh(3A) = 4 sinh^3(A) + 3 sinh(A)
so that
sinh(3A) = 1
cosh(3A) = sqrt(1 + sinh(3A)^2) = sqrt(2)
so
exp(3A) = cosh(3A) + sinh(3A) = sqrt(2) + 1
exp(-3A) = cosh(3A) - sinh(3A) = sqrt(2) - 1
so
exp(A) = (sqrt(2) + 1)^(1/3) * Omega
exp(A) = (sqrt(2) - 1)^(1/3) / Omega
sinh(A) = (exp(A) - exp(-A))/2
where Omega is one of the cube roots of 1. So this is also the solution
for x. You could probably solve any polynomial equation using trig
functions, hyperbolic functions and their inverses.
But the solution is not a repeating decimal. So things aren't so easy
anymore. Analogously, the solution to a fixed-point equation doesn't have to
be a regular expression. This apparent limitation would have been the end of
the story if we had been living in the 20th Century. But ... um... slippage
in the time stream. Oops.
(6) Some Basic Properties of the Context Free Algebra
For what follows let's state a definition and a couple lemmas:
Definition: Let E be a regular expression over X union D, where
D = { |0>, |1>, ..., |s>, <0|, <1|, ..., <s| }
subject to the relations
<m| |n> = 1 if m = n
= 0 else (R)
|0><0| + |1><1| + ... + |s><s| = 1
Then E is called operator-free if every word in E can be
reduced to a word in X* using the relations E.
Lemma 3: If E is operator-free then
<n| E = E <n| and |n> E = E |n>
Proof:
Let <n| w be a word in <n| E, where w is a word in E. Then w = w' for
some word w' in X*. Thus <n| w = <n| w' = w' <n| = w <n|, since <n|
commutes with all the symbols in X. A similar proof follows for all the
other cases.
Lemma 4: E is operator-free if and only if
E = <n| E' |n>, where neither <n| nor |n> occur in E'.
Proof:
The forward implication is trivial, let E' = E. So for the backward
implication let E' be given as above, let n be any number from 0 to s and
let <n| w |n> be a word in E = <n| E' |n> where w is a word in E' containing
no occurrences of |n> or <n|.
If the operators in w do not occur in balanced pairs, there will either
be a spare |m> which can be brought out to the left end of E', or a spare
<m| which can be brought out to the right end of E', where m is distinct
from n. In either case, you'll get a cancellation with one of the
bounding n-operators in <n| E' |n>.
On the other hand if the operators in w do occur in balanced pairs,
then they will cancel and w will reduce to some w' in X*.
Keep in mind that since we're working in a partially ordered semi-ring
which is an extension of the semi-ring of regular expressions over X, 0 is not
a word, but merely the additive identity of the semi-ring. A word w is
considered to be "in E" iff E = E + w. A further discussion of the algebraic
preliminaries can be found in the 5th part of this series ("The Algebraic
Representation of Formal Languages").
(7) Solving the Least Fixed Point Equation
So, back to the original issue, what if the grammar looked like this:
S = N V a + S P b
V = v N c
P = p N d
N = n e + N P f
where the extra symbols might even be construed as tree-building operations.
This system can still be solved, but now using Context Free expressions.
First, the equation for N still yields the same type of solution:
N = <x: n e + x P f> = n e (P f)*
But for P, the result is no longer regular. In fact, you now have the
following equation:
P = p N d
= p n e (P f)* d
For each occurrence of P on the right hand side, note the set of terms which
may follow it. After P will come f, an undetermined number of more (P f)'s
and then d. The context following P is thus: f (P f)* d.
Assign each distinct context a pair of operators <n| and |n> where the
corresponding number, n, is numbered starting at 1. Define the term:
PF = sum (|n> C_n PF) + |0>
where C_n is the nth follow context. Here, this definition amounts to
saying: let
PF = |1> C_1 PF + |0>
where
C_1 = f (P f)* d
So now define the term PS = P PF. Then we may write:
<0| PS = <0| P (|1> C_1 PF + |0>)
= <0| P |1> C_1 PF + <0| P |0>
= 0 C_1 PF + P by Lemma 3
= P
<1| PS = <1| P |1> C_1 PF + <1| P |0>
= P C_1 PF + 0 by Lemma 3
= P f (P f)* d PF
and
PS = p n e (P f)* d PF
= p n e Q
where Q = (P f)* d PF
and
Q = P f (P f)* d PF + d PF
= <1| PS + d PF
= <1| p n e Q + d |1> C_1 PF + d |0>
= <1| p n e Q + d |1> f Q + d |0>
Thus we arrive at a right-linear system of equations for P:
P = <0| PS
PS = p n e Q
Q = <1| p n e Q + d |1> f Q + d |0>
whose solution is derived by substitution:
P = <0| p n e (<1| p n e + |1> d f)* d |0>
noting the commutation relation |1> d = d |1>. With a little
algebra this could be reduced further to:
P = <0| (<1| p n e + |1> d f)* d |1> |0>
but it doesn't really matter. The point is that a closed form solution
has been found and it is of the form:
P = <0| R |0>
where R is a regular expression over the alphabet X = {a,b,c,d,e,f,n,p,v}
and operator set {|1>,<1|}.
So now everything else is routine:
V = v N c
S = N V a + S P b
--> S = <z: N V a + z P b>
= N V a (P b)*
which after substitution for N and V yields:
S = n e (P f)* v n e (P f)* c a (P b)*
Now (P f)* can be reduced to the for <0| ... |0> by noting that:
(P f)* = (<0| R |0> f)*
= 1 + <0| R |0> f (<0| R |0> f)*
= 1 + <0| R f |0> (<0| R f |0>)*
= 1 + <0| R f (|0> <0| R f)* |0>
= <0| |0> + <0| (|0> <0| R f) (|0> <0| R f)* |0>
= <0| (|0> <0| R f)* |0>
Or
(P f)* = <0| (p0 R f)* |0>, where p0 = |0><0|
Thus
S = n e <0| (p0 R f)* |0> v n e <0| (p0 R f)* |0> c a <0| (p0 R b)* |0>
= <0| n e (p0 R f)* p0 v n e (p0 R f)* p0 c a (p0 R b)* |0>
Or with a little further manipulation this can be reduced to:
S = <0| n e (p0 R f)* v n e (p0 R f)* c a (p0 R b)* |0>
where
p0 = |0><0|
R = (<1| p n e + |1> d f)* d |1>
which is only one pair of context symbols away from being a regular language.
This then provides the archetypical example of how to solve Context
Free Equations in closed form. Given an equation
x = P = P(x, y1, ..., yn)
where P(x) is a regular expression of y1, ..., yn and where each of the
y's is operator-free. First, to be consistent, we may eliminate all the
uccorrences of <0| and |0> by rewriting each of the y's that have the form
<0| y' |0> as <m| y' |m> where m is the smallest number larger than 0 for
which no m-operators occur amongst the y's. This is actually an application
of Lemma 4.
We may apply Lemma 1 if P does not actually involve any occurrences of x.
Otherwise we can apply Lemma 2 to make sure there are no left or right
recursions in x. Distinguish and number all the contexts associated each
occurrence of x in P and call them C_1, C_2, ..., C_s where there are s
contexts. There may be new contexts that appear in each of the C's that
do not occur in P. Add these to the enumeration and whatever new contexts
are spawned as a result and so on. The process will eventually terminate
since the terms get successively smaller.
Define
x_F = |0> + |1> C_1 x_F + ... + |s> C_s x_F
and
x_S = x x_F.
Then
<0| x_S = <0| x x_F
= <0| x |0> + sum (<0| x C_2 x_F |i>)
= x + 0
= x
and
<i| x_S = <i| x x_F
= <i| x |0> + sum (<i| x C_2 x_F |i>)
= 0 + <i| x C_i x_F |i>
= x C_i x_F
But we may also write
x_S = x x_F = P(x, y1, ..., yn) x_F
Since C_i was derived from the term P, every occurrence of x in C_i will
have a context associated with it. We may thus write
C_i = ai + ai1 x C_1 + ... + ais x C_s
where none of the a's contain any occurrences of x. Thus
C_i x_F = ai x_F + ai1 x C_1 x_F + ... + ais x C_n x_F
= ai x_F + ai1 <1| x_S + ... + ais <s| x_S
where the a's are regular expressions in (y1, ..., yn) containing no
occurrences of x. The term P x_F may be written in a similar fashion. Thus
the system of equations
x = <0| x_S
x_S = P x_F
x_F = |0> + |1> C_1 x_F + ... + |n> C_n x_F
will ultimately reduce to a series of right-linear equations of the
form:
x = <0| x_S
x_S = p x_F + p1 <1| x_S + ... + ps <s| x_S
x_F = |0> + (|1> a1 + |2> a2 + ... + |s> as) x_F
+ sum |i> aij <j| x_S
whose solutions must therefore be of the form:
x = <0| x_S
x_S = A* p x_F
x_F = B* |0> + B* C x_S
= B* |0> + B* C A* p x_F
Thus
x_F = (B* C A* p)* B* |0>
x_S = A* p (B* C A* p)* B* |0>
A* p B* (C* A* p B*)* |0>
and
x = <0| A* p B* (C* A* p B*)* |0>
which has the form:
x = <0| R |0>
for some regular expression in the y's and over the operator set
{ <1|, <2|, ..., <s|, |1>, |2>, ..., |s> }.
Given a system of equations, we may solve one equation this way
and then substitute the solution in the remaining equations to arrive
at a smaller system. Applying the process iteratively will lead to
a closed form solution.
(8) A Couple More Examples
(8.1) A simple expression grammar
Consider the grammar given by the system:
S = E q E a + o S c
E = u E + E b E + l E r + x
where S is the main variable. Solving the equation for E first, we
get:
E = (u E + l E r + x) (b (u E + l E r + x))*
by Lemma 2. There are only two distinct contexts:
C_1 = Q = (b (u E + l E r + x))*
and C_2 = r Q
associated respectively with the occurrences of E in u E, and with the
occurrences of l E r. Neither of the contexts C_1 nor C_2 will spawn
new contexts so our process is complete. We may thus write:
E = <0| E_S
E_S = (u E + l E r + x) Q E_F
E_F = |0> + |1> Q E_F + |2> r Q E_F
and carry out the following reductions:
Q E_F = (b (u E + l E r + x))* E_F
= E_F + b (u E + l E r + x) Q E_F
= E_F + b E_S
= |0> + |1> Q E_F + |2> r Q E_F + b E_S
E_S = u E Q E_F + l E r Q E_F + x Q E_F
= u <1| E_S + l <2| E_S + x Q E_F
= U x Q E_F
where
U = (u <1| + l <2|)*
Thus
Q E_F = (|1> + |2> r + b U x)* |0>
and
E = <0| U x Q E_F
= <0| U x V |0>
where
V = (|1> + |2> r + b U x)*
U = (u <1| + l <2|)*
The second equation may then be solved in closed form:
S = E q E a + o S c
which leads to:
S = <0| S_S
S_F = |0> + |1> c S_F
S_S = S S_F
which leads to the reductions:
S_F = (|1> c)* |0>
S_S = E q E a S_F + o S c S_F
= E q E a S_F + o <1| S_S
S_S = (o <1|)* E q E a S_F
= (o <1|)* E q E a (|1> c)* |0>
Thus
S = <0| (o <1|)* E q E a (|1> c)* |0>
If we change to 0-operators in E to <3| and |3>, we may then write:
S = <0| (o <1|)* E q E a (|1> c)* |0>
where
V = (|1> + |2> r + b U x)*
U = (u <1| + l <2|)*
E = <3| U x V |3>
Making the indicated substitutions for U, V and E will yield the
closed-form solution, though it will be a bit unwieldy. In actual
practice it's more useful to stop the process once a right-linear system of
equations is derived and then call THAT the solution. The system will bear a
direct connection to a push down automaton and therefore have more immediate
application. The regular expression, itself, is really only for purposes of
exhibition.
(8.2) A tricky grammar
Consider the language given by the equation
S = a + S S S b
Applying Lemma 2 results in the equation:
S = a (S S b)*
whose two contexts are:
C_1 = S b Q
and C_2 = b Q
where Q = (S S b)*
Thus
S = <0| S_S
S_F = |0> + |1> S b Q S_F + |2> b Q S_F
S_S = S S_F = a Q S_F
This reduces to:
Q S_F = S_F + S S b Q S_F
= S_F + <1| S_S
S_F = |0> + |1><2| S_S + |2> b Q S_F
S_S = a Q S_F
Thus
Q S_F = |0> + |1><2| S_S + |2> b Q S_F + <1| S_S
= |0> + (|1><2| + <1|) a Q S_F + |2> b Q S_F
= ( (|1><2| + <1|) a + |2> b )* |0>
and
S = <0| a Q S_F
= <0| a (v a + u b)* |0>
where
v = |1><2| + <1|
u = |2>
As it turns out, the subalgebra generated by { <0|, |0>, u, v } is
isomorphic to that generated by { <0|, |0>, <1|, |1> } by the
correspondence:
<0| <--> <0|
|0> <--> |0>
v <--> <1|
u <--> |1>|1>
In fact, v u = |1> and v |1> = 1. Thus, we may write
S = <0| a (<1| a + |1>|1> b)* |0>
In effect, v behaves like the square root of u's adjoint, <2|.
(8.3) An impossibly difficult grammar
Consider the language given by the grammar expressed in equational form:
S = 1 + (a b)^(b S a)
One might wonder if and how this can be solved in closed form. Does it
yield a context free language? (No). Can it be expressed as the intersection
of n CFL's for some n? (Yes, 3). Can it be expressed as the intersection of
n unambiguous CFL's for some n? (No). Is there an easy way to characterise
it other than this? (I don't know).
0 new messages