CS 154 Introduction to Automata and Complexity Theory Handout 13

Winter 1996  R. van Glabbeek  February 14

Solution Set 5

1. 5.1-1 page 321.

(a) L is accepted by the DCA (deterministic counter acceptor) in figure 1, and is hence a DCA language.

Figure 1: DCA for L

(b) L is not a regular language. Suppose to the contrary that a FA with N states accepts L, then it accepts the string

\underbrace{“ ‘ “ ‘ “ ‘ “ ‘ “ ‘ …}_{w,where |w|=N} \underbrace{… ’ ” ’ ” ’ ” ’ ” ’ ”}_{u}

By the Pumpling Theorems, for every i ≥ 0 xv^{i}yu is accepted by the FA for xvy = w and |v| > 0, which is evidently not in L for i ≠ 1.

(c) Suppose for a contradiction that the set of english sentences E were regular. We construct a finite transducer that for every string w generates a string τ(w), such that w ∈ L iff τ(v) ∈ E. Thus we could contrary to part b construct a finite acceptor for L by composing the hypothetical finite acceptor for E with τ as in Theorem 4.38. As τ we could take the transducer given by the follwing table:

(SCAN “, WRITE “Hi) (SCAN ‘, WRITE ‘Ho) (SCAN ”, WRITE ”) (SCAN ’, WRITE ’)

Alternatively, since regular languages are closed under intersection (boolean operations in general), assuming E is a regular language would imply that

F = E ∩ ((“ ‘)^{∗} Hi (’ ”)^{∗})

is a regular language. But by the same argument as in (b) F is not regular.

(d) L′ is accepted by the DCA in figure 2, and is hence a DCA language.

Figure 2: DCA for L

(e) Assume for a contradiction that L′ was regular, then it would be accepted by a DFA. Let τ be the deterministic transducer defined by:

(SCAN “, WRITE ”) (SCAN ‘, WRITE ’) (SCAN ”, WRITE ”) (SCAN ’, WRITE ’)

By theorem 4.38 L′τ^{−1} is accepted by a DFA. However L′τ^{−1} = L, and L was shown nonregular, thus, we have arrived to a contradiction.

(f) Similar (c) we construct a deterministic transducer τ, such that for every word w, τ(w) ∈ E′ (is an english sentence under the present representation) iff w ∈ L′. The transducer could for instance be of the form:

(q_{0} → q_{1}, SCAN ”, WRITE ”)
(q_{0} → q_{2}, SCAN ’, WRITE ’)
(q_{1} → q_{0}, SCAN ”, WRITE Hi ”)
(q_{1} → q_{2}, SCAN ’, WRITE ’)
(q_{2} → q_{0}, SCAN ’, WRITE Ho ’)
(q_{2} → q_{1}, SCAN ”, WRITE ”)

which only writes a word when it is inside an innermost nesting of either ′’s or ”’s.

2.

3.

4.

5. 5.9-4 page 374. Let G be a CFG for L, and N > 1 the pumping number for G, and let M = 3N.

For z_{1} = a^{M}b^{M}c^{M+M!} mark the first N a’s and use lemma 5.25 to conclude that there are derivations of the form

\begin{matrix}S & ⇒^{∗} & uAy \\ A & ⇒^{∗} & v^{i}wx^{i} & for each i ≥ 0 \end{matrix}

where z_{1} = uvwzy and v = a^{k} and x = b^{k}, 1 ≤ k ≤ N by the same reasons as on page 373. Furthermore v must have a non-empty overlap with the first N a’s in z by the second condition in lemma 5.25 (weight(v) ≥ 1 or weight(x) ≥ 1). Since k divides M the derivation of uAy extends to a derivation of a^{M+M!}b^{M+M!}c^{M+M!} by

S ⇒^{∗} uAy
⇒^{∗} ua^{k}wb^{k}y
⇒^{∗} ua^{M!+k}wb^{M!+k}y = a^{M!+M}b^{M!+M}c^{M!+M}

For z_{2} = a^{M}b^{M+M!}c^{M} mark the last third of the a’s and again use lemma 5.25 to conclude that there are derivations of the form

\begin{matrix}S & ⇒^{∗} & u′By′ \\ B & ⇒^{∗} & v^{′i}w′x^{′i} & for each i ≥ 0 \end{matrix}

where z_{2} = u′v′w′z′y′ and v′ = a^{k′} and x′ = c^{k′}, 1 ≤ k′ ≤ N. Here v′ must have a non-empty overlap with the last third of the a’s, and the derivation of u′By′ extends to a derivation of a^{M+M!}b^{M+M!}c^{M+M!} by

\begin{aligned}S & ⇒^{∗} & u′By′ \\ & ⇒^{∗} & u′a^{M!+k′}w′c^{M!+k′}y′ = a^{M!+M}b^{M!+M}c^{M!+M} \end{aligned}

Thus, in one derivation the phrase a^{M!+k}wb^{M!+k} is generated and in the other a^{M!+k′}w′c^{M!+k′} is generated. These phrases trivially overlap, since the second must contain all b’s and the first at least one b. We argue that they are not substrings of eachother (the problem could be if the first phrase is a substring of the second). This follows as |u| < N, since we marked the first third of the a’s in z_{1}, and |u′| > N, since we marked the last third of the a’s in z_{2}. Thus, a^{M!+k}wb^{M!+k} contains more a’s than a^{M!+k′}w′c^{M!+k′}.

Extra credit problem First realize that L_{X} ⊆ L_{A}(L_{B}) and L_{Y} ⊆ L_{B}. This follows as

f(L_{A}(L_{B}), L_{B}) ⊆ L_{A}(L_{B})

and

g(L_{A}(L_{B}), L_{B}) ⊆ L_{B}

thus (L_{X}, L_{Y}) = (L_{X}, L_{Y}) ∩ (L_{A}(L_{B}), L_{B}).

To establish the reverse containments we recall properties of L_{X}, L_{Y}, L_{A} and L_{B} given by their fixpoint characterizations:

1. f(L_{X}, L_{Y}) ⊆ L_{X}.

2. g(L_{X}, L_{Y}) ⊆ L_{Y}.

3. f(X, Y) ⊆ X implies L_{A}(Y) ⊆ X for every X and Y.

4. g(L_{A}(Y), Y) ⊆ L_{B} implies L_{B} ⊆ Y for every Y.

We now show L_{B} ⊆ L_{Y}:

• From 1 and 3 conclude L_{A}(L_{Y}) ⊆ L_{X}.

Thus, by monotonicity and 2 g(L_{A}(L_{Y}), L_{Y}) ⊆ g(L_{X}, L_{Y}) ⊆ L_{Y}. So, 4 implies L_{B} ⊆ L_{Y}.

Finally we establish L_{A}(L_{B}) ⊆ L_{X}:

• From the previous result, monotonicity and 1 we conclude that f(L_{X}, L_{B}) ⊆ f(L_{X}, L_{Y}) ⊆ L_{X}. Hence from 3 L_{A}(L_{B}) ⊆ L_{X}.