To see why, assume none of (1) through (4) hold. Then (1) tells us w must begin with 6, and (2) tells us w ends with a. Statements (3) and (4) tell us that s and bs must alternate in w. Thus, the logical OR of (1) through (4) is equivalent to the statement к is not of the form baba ЬаУ We have proved that the OR of (1) through (4) implies h{w) is not in L. That statement is the contrapositive of the statement we wanted: if h{;w) is in L, then w is of the form baba---ba. □

We shall next prove that the inverse homomorphism of a regular language is also regular, and then show how the theorem can be used.

Theorem 4.16: If /i is a homomorphism from alphabet 2 to alphabet T, and L is a regular language over T, then hrlL) is also a regular language.

PROOF: The proof .starts with a DFA A for L. We construct firom A and h a DFA for h~{L) using the plan suggested by Fig. 4.6. This DFA uses the states of A but translates the input symbol according to h before deciding on the next state.

Input a

Start

Accept/reject

Figure 4.6: The DFA for h {L) applies h to its input, and then simulates the DFA for L

Formally, let L be L(A), where DFA A = {Q,T,S,qo,F}. Define a DFA

S-(Q,S,7,7o,F)

where transition function 7 is constructed by the rule 7(, a) - 5(g, /г{о)). That is, the transition В makes on Input a is the result of the sequence of transitions that A makes on the string of symbols h{a). Remember that h{a) could be f, it could be one .symbol, or it could be many symbols, but S is properly defined to take care of all these cases.

It is an easy induction on to show that jiqow) - 6{до,к{ю)). Since the accepting states of A and В are the same, Б accepts w if and only if A accepts h{w). Put another way, В accepts exactly those strings w that are in h~{L). a

Example 4,17: In this example we shall use inverse homomorphism and several other closure properties of regular sets to prove an odd fact about finite automata. Suppose we required that a DFA visit every state at least once when accepting its input. More precisely, suppose A - {Q,I!,.6,qo,F) is a DFA, and we axe interested in the language L of all strings w in S* such that 6{qo,w) is in F, and also for every state q in Q there is some prefix Xq of w such that (9o, Xq) = q. Is L regular? We can show it is, but the construction is complex.

First, start with the language M that is L[A). i.e., the set of strings that A accepts in the usual way, without regard to what states it visits during the processing of its input. Note that L С M, since the definition of L puts an additional condition on the strings of L{A). Our proof that L is regular begins by using an inverse homomorphism to, m effect, place the states of A into the input symbols. More precisely, let us define a new alphabet T consisting of symbols that we may think of as triples \paq], where:

1. p and q are states in Q,

2. о is a symbol m £, and

3. 6{j),a) =q.

That is, we may think of the symbols in T as representing transitions of the automaton A. It is important to see that the notation \paq] is our way of expressing a single symbol, not the concatenation of three symbols. We could have given it a single letter as a name, but then its relationship to p, q, and a would be hard to describe.

Now, define the homomorphism h{\paq]) - a for all p, a, and q. That is, h removes the state components from each of the symbols of T and leaves (зп1у the symbol from S. Our first step in showing L is regular is to construct the language Li = h~{M). Since M is regulai, so is Li by Theorem 4.16. The strings of ii are just the strings of Л/ with a pair of states, representuig a transition, attached to eacli symbol.

As a very simple illustration, consider the two-state automaton of Fig. 4.4(a). The alphabet E is {0,1}, and the alphabet T consists of the four symbols [pOg], [pip], and [qlq]. For instance, there is a transition from state p to g on input 0, so [pOg] is one of the symbols of Г. Since 101 is a string accepted by the automaton, applied to this string will give us 2 = 8 strings, of which [р1р][рОд][(/1(/] and [glq] [Og] [pip] are two examples.

We shall now construct L from L\ by using a series of further operations that preserve regular languages. Our first goal is to eliminate all those strings of Li that deal incorrectly with states. That is, we can think of a symbol like

\paq] as saying the automaton was in state p, r<>ad input a, and thus entered state q. The sequence of symbols must satisfy- three conditions if it is to be deemed an accepting computation of Л г

1. The first state in the first sjTubol must be t/o, the start state of .4,

2. Each transition must pick up where the previous one left off. That is, the first state in one symbol must equal tht; second state of the previous sjmbol.

3. The second state of the last symbol must be in F. This condition in fact will be guaranteed once we enforce (1) and (2), since we know that every string in Li came from a string accepted by A.

The plan of the construction of L is shown in Fig. 4.7.

The language of automaton A

Inverse homomorphism Strings of M with state transitions embedded

Intersection with a regular language Add condition that first state is the start state

Difference with a regular language Add condition that adjacent states are equal

Difference with regular languages Add condition that all states appear on the path

Homomoфhism Delete state components, leaving the symbols

Figure 4.7: Constructing language L from language M by applying operations that preserve regularity of languages

We enforce (1) by intersecting L] with the set of strings that begin with a symbol of the form [qaq] for some sjonbol a and state q. That is, let Ei be the