Re: Computer language and category theory
From: Alfred Einstead (whopkins_at_csd.uwm.edu)
Date: 11/30/04
- Next message: Jon Haugsand: "Re: Computer language and category theory"
- Previous message: Paul Bramscher: "Re: Turing Machines and Physical Computation"
- Next in thread: Jon Haugsand: "Re: Computer language and category theory"
- Reply: Jon Haugsand: "Re: Computer language and category theory"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Date: 30 Nov 2004 14:09:05 -0800
Jon Haugsand <jonhaug@ifi.uio.no> wrote:
> Given the language
>
> S ::= A | B
> A ::= aa | ba | A-aa | B-ba
> B ::= ab | bb | A-ab | B-bb
This is the regular language given by the regular expression
S = (a | b) (a-a | b-b)* (a | b).
If you consider a language to be a subset of X*, with X = {a,b,-}
then the grammar above corresponds to a system of inequalities:
S > A | B
A > aa | ba | A-aa | B-ba
B > ab | bb | A-ab | B-bb
and you are seeking out the least solution in the sense of the
inequality > which stands for ([improper] superset).
which is equivalent to:
S > Xa | Xb
A = Xa
B = Xb
X > a | b | Xa-a | Xb-b
or, by factoring
X > (a|b) | X (a-a | b-b).
The least solution in x to (x >= a | xc) is x = a c*. Thus
X > (a|b) (a-a | b-b)*.
Factoring S you arrive at the least solution
S > Xa | Xb = X(a|b) > (a|b) (a-a | b-b)* (a|b).
> However, I don't have such a simple language, but rather a slightly
> more complicated one:
>
> T ::= A | B
> A ::= aa | ba | A-aa | B-ba
> B ::= ab | bb | A-ab | B-bb | A-K
> K ::= ( A )-B | ( B )-B
A similar process yields the system
T > X(a|b|a-K)
X > (a|b) (a-a | (b|a-K)-b)*
K > ( X(a|b|a-K) )-X(b|a-K)
So, then, the root of the problem is how to solve fixed point systems
that are not one-sided linear and do not merely have regular expressions
as solutions.
The answer is to extend the algebra by adding in new elements
u1, u2, ..., un, v1, v2, ..., vn
for some n > 1; subject to the relations
ui vi = 1; ui vj = 0 if i, j are different;
and
ui x = x ui; vj x = x vj, if x is any of the original symbols.
An inequality such as x > a x b | c then has as a least solution
x = u1 (a u2)* c (b v2)* v1.
If one adopts the axiom:
x* = least upper bound of (1,x,xx,xxx,xxxx,...)
and that
(l.u.b. U) (l.u.b V) = l.u.b. (UV)
for regular subsets U, V then one can expand the above expression
into a formal infinite sum which contains as its terms all the
elements of the language recognized:
x = c | acb | aacbb | aaacbbb | ...
since everything else cancels out, by suitably manipulating the
u's and v's.
A solution for the system above can, likewise, be worked out; but is
a bit more complex.
- Next message: Jon Haugsand: "Re: Computer language and category theory"
- Previous message: Paul Bramscher: "Re: Turing Machines and Physical Computation"
- Next in thread: Jon Haugsand: "Re: Computer language and category theory"
- Reply: Jon Haugsand: "Re: Computer language and category theory"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Relevant Pages
|
