1.1 Strings and Languages
Example 1.3 Solve the word equation
X011 = 011X
over the alphabet (0, 1); that is, find the set of strings x over (0, 1) which
satisfy the equation.
Solution. For the equation to hold, either x is the empty string or the string
011 is both a prefix and a suffix of x:
(^0111) I
= &Jo
(It is obvious that x cannot be of length 1 or 2.) Let x = 011~. Now, remove
the first occurrence of 011 from both 011x and x011, we get x = ~011. It
follows that Olly = ~011. This gives us a recursive solution for x: x is either
E or x = 011~ for some other solution y of the equation. It is not hard to see
now that (O1l)n is a solution to the equation for each n > - 0, and they are the
only solutions. Cl
A language is a set of strings. For example, (0, l}, {O’, 01, 02,. ..}. and the
set of all English words are languages. Let C be an alphabet. We write C*
to denote the set of all strings over C. Thus, a language L over C is just a
subset of C. For any finite language A C C, we write IAl to denote the size
(i.e., the number of strings) in A. -
The following are some basic operations on languages. (The first four are
just set operations. See Figure 1.1.)
Union: If A and B are two languages, then A U B = {x 1 x E A or x E B}.
Intersection: If A and B are two languages, then A n B = {x 1 x E A and
It: E B).
Subtraction: If A and B are two languages, then A \ B = {x I x E A and
x 4 B}. (A \ B is also denoted by A - B when B C - A.)
Complementution: If A is a language over the alphabet C, then A = C* -A.
Concutenution: If A and B are two languages, then their concatenation is
A - B = {ub I a E A, b E B}. We also write AB for A l B.
It is clear that concatenation satisfies the associativity law, and so we
do not need parentheses when we write the concatenation of more than two
languages: A1 A2. l. A,,.
Example 1.4 (a) If A = {O,l} und B = {1,2}, then AB = {01,02,11,12}.
(b) Is it true that if A is of size n > - 0 and B is of size m > 0 then AB