o theorem 2.4.1 on p.88. i don't get it. i think i get the o first half of it, but i don't get the part about y!=e (what is e?)First, for terminology's sake, "e" is actually a lower case epsilon, indicating an empty string. It's similar to the way naught (a zero with a line through it) represents an empty set.
o and i'm a little unsure of x(y^i)z is an element of L.So, here's the theorem in english...
The Cast:
L A regular language
i,n Dummy variables used to make a point
w Any string longer than "n" characters long
x,y,z Substrings of "w" such that if you string them all together, they
make w
The Plot:
1) For any language, L, that you can come up with, there is a particular
number, n.
2) Any string w that is
a) In the langauge L
b) At least n characters
Can be broken down into three strings, x, y, and z, such that
a) x, y, and z strung together in that order make up w
b) y is not an empty string
c) the length of xy (x and y concatenated) is less than or equal to n
d) Any string of the form x(y^i)z, i>=0 (that is, x, followed by any
number of y's, zero or greater, followed by z) is also in the
langauge.
The Point: We show that any regular language has the neat feature stated in 2d (the rest is just setup). Therefore, we can easily say that any language without this property is *not* a regular language.
Page maintained by Salvatore Domenick Desiano (sal@ri.cmu.edu).
smile.