Problem Solving in Automata, Languages, and Complexity

12 REGULAR LANGUAGES

a3 = 3). Also, for k = 0, 1,... , 9, let Lk be the set of all nonempty strings
over {ao,... , ak} having no repeated adjacent symbols. Then, we have

Lo = ao,

Lk+l = Lk + (E + Lk)(ak+dk)*ak+l(& + Lk).

(Note that if a string in Lk+r does not contain ak+l, then it is in LI,.) Cl

• Example 1.20 Find a regular expression for the set of all strings over al-
  phabet

{(i)(i)(%).(p),(a);(e);(n)(i)}

that represent correct additions over binary expansions of integers, with lead-
ing O’s added when necessary. For example, the relation

0 1 1 0

+ 0 1 0 1

1 0 1 1

implies that the string

(H)(i)(l)(Y)

is in the set.

SoZution. First, we note that the language is closed under string concatena-
tion; that is, the concatenation of two strings in the language is still in the
language. Thus, it suffices to study the minimal strings in the language.
Next, we consider the leftmost symbol. It has four choices:

In the first three cases, this digit by itself is a minimal string in the language.
Now, we consider the fourth case. Here, the rightmost symbol has only one
choice:

1

( 1

1 9

0

and the second rightmost symbol must exist and has four choices: