Homework 3 Example Solution

Homework 3 Example Solution
CSE 457/598 Fall 2014
1. Let L be the language of even-length palindromes (even-length strings which are equal to their reversal). Given
strings x & y such that x 6= y, let z = 10|x|+|y|+2 1xrev (where xrev denotes the reversal of x), so that xz =
x10|x|+|y|+2 1xrev ∈ L but yz = y10|x|+|y|+2 1xrev ∈
/ L. If |x| = |y|, then the latter is trivial; otherwise, note that the
midpoint of the string must be in the long run of 0’s, & that since |x| 6= |y|, the distance to the nearest 1 will be
different on each side of the midpoint; thus the string is not a palindrome. Therefore all strings of Σ∗ are pairwise
inequivalent, so every string lies in its own equivalence class.
2.
a. The equivalence classes are sets of strings with the same value of |x|1 − |x|0 , i.e. the same excess of 1’s over
0’s. Suppose x & y are strings from 2 different such sets. Let z = 0|x|1 1|x|0 , & then xz ∈ L, but yz ∈
/ L, so the
sets are pairwise inequivalent. On the other hand, suppose x & y are 2 strings from the same set. Then for all
strings z, |xz|1 − |xz|0 = |x|1 − |x|0 + |z|1 − |z|0 = |y|1 − |y|0 + |z|1 − |z|0 = |yz|1 − |yz|0 , so x is equivalent to y
as claimed.
b. The equivalence classes are {{ai } : i ≥ 0} ∪ {{ai bj } : i ≥ j > 0} ∪ {{aj bj cj−i : j > i} : i ≥ 0} ∪ {{w : w ∈
/
any other class}}. {ai } for i > 0 is inequivalent to any other class because z = bi ci distinguishes it (i.e. ai z ∈ L
but xz ∈
/ L for any x 6= ai ). {ε} is distinguished from everything but the penultimate class by z = ε, while it is
distinguished from that class by z = abc. {ai bj } for i ≥ j > 0 is distinguished by z = b|i−j| ci . {aj bj cj−i : j > i}
for i ≥ 0 is distinguished by z = ci , while the strings for each i are equivalent because they all require the same
unique extension to be in the languge. Finally, the remaining strings are all equivalent, because none of them
can be extended to form a string in the language.
3.
a. Lrev is regular: Construct an NFA for it as follows. Copy a DFA for L, but reverse every transition. Add a new
state (that will become the start state of the NFA) with an ε-transition to every original final state. Finally,
the accepting state is the original start state of the DFA. Then Lrev L is regular by closure of the set of regular
languages under concatenation.
b. This can be non-regular. Let Σ = {0, 1} & L = Σ∗ . Then {wrev w : w ∈ L} consists of even-length palindromes
over Σ (since (wrev w)rev = wrev w for all w ∈ Σ∗ ). But in the answer to problem 1 we showed this language has
infinitely many equivalence classes under the Myhill-Nerode equivalence relation, so it is not regular.
c. {w : wrev w ∈ L} is regular: Construct an NFA for its reverse (given a DFA D for L) as follows. The states are
pairs of states of D, plus a new state q 0 . The initial state is q 0 . There are ε-transitions from q 0 to (q0 , q) (where
q0 is the initial state of D & q is any final state of D) & transitions from (q, r) to (q 0 , r0 ) on input a whenever
there are transitions on the same input a from q to q 0 & r0 to r (note the reverse direction) in D. Finally, the
accepting states are all states of the form (q, q). For the NFA to accept a string w, the first component of the
state must reach a state of D from which D goes on to accept the reverse of the string (enforced by the second
component of the state), which is to say, wwrev ∈ L. Now we have the reverse of what we want, but we know
that reversing it preserves regularity by the argument in part A.
4.
a. Let D =< Q, Σ, δ, q0 , F > where Q = {q0 , q1 , q2 , q3 , q4 }, Σ = {0, 1}, F = {q0 , q1 , q2 , q3 }, & δ is as follows:
δ(q0 , 0) = q0 δ(q0 , 1) = q1
δ(q1 , 0) = q2 δ(q1 , 1) = q1
δ(q2 , 0) = q2 δ(q2 , 1) = q3
δ(q3 , 0) = q4 δ(q3 , 1) = q3
δ(q4 , 0) = q4 δ(q4 , 1) = q4
b. We compute the 100th & 1000th powers of the transition matrix for D (where the i, j entry is the number of
transitions from state qi to state qj ) & sum the first 4 elements (since q0 -q3 are accepting) of the first row of
each. This counts the number of ways of reaching any accepting state from the start state.
1
100 


1 100 4950 161700 ≈ 1.3 · 1030
1 1 0 0 0
0
0 1 1 0 0
1
100
4950
≈ 1.3 · 1030 





0 0 1 1 0
0
1
100
≈ 1.3 · 1030 
= 0



0
0 0 0 1 1
0
0
1
≈ 1.3 · 1030 
0 0 0 0 2
0
0
0
0
≈ 1.3 · 1030
Length 100: 166751 strings
1000 


1 1000 499500 166167000 ≈ 1.1 · 10301
1 1 0 0 0
0
 0 1 1 0 0
1
1000
499500
≈ 1.1 · 10301 





 0 0 1 1 0
0
1
1000
≈ 1.1 · 10301 
≈ 0



0
 0 0 0 1 1
0
0
1
≈ 1.1 · 10301 
0 0 0 0 2
0
0
0
0
≈ 1.1 · 10301
Length 1000: 166667501 strings
(It is possible in this case to simply remove state q4 in the specification and proceed with the NFA that results.
This removes the last row and column from the transition
matrix and makes the computations somewhat easier.
Also note that with strings of length n, there are ni strings that end in qi for i = 0, 1, 2, 3, so the answer in
P3
general is i=0 ni , a pattern which you might have noticed in the results above.)
c. Let D =< Q, Σ, δ, q0 , F > where Q = {q0 , q1 , q2 , q3 , q4 , q5 , q6 }, Σ = {0, 1}, F = {q0 , q5 }, & δ is as follows:
δ(q0 , 0) = q1 δ(q0 , 1) = q6
δ(q1 , 0) = q2 δ(q1 , 1) = q6
δ(q2 , 0) = q3 δ(q2 , 1) = q4
δ(q3 , 0) = q6 δ(q3 , 1) = q4
δ(q4 , 0) = q6 δ(q4 , 1) = q5
δ(q5 , 0) = q1 δ(q5 , 1) = q0
δ(q6 , 0) = q6 δ(q6 , 1) = q6
d. We compute the 7th , 100th , & 200th powers of the transition matrix for D & sum the
(since q0 & q5 are accepting) of the first row of each. The reasoning is the same as part

7 

0 1 2 1 1 0 123
0 1 0 0 0 0 1
0 0 1 2 3 1 121
 0 0 1 0 0 0 1




1 1 0 1 3 3 119
 0 0 0 1 1 0 0




0 0 0 0 1 0 1 = 1 1 0 0 1 2 123




2 3 1 0 0 1 121
 0 0 0 0 0 1 1




1 3 3 1 1 0 119
 1 1 0 0 0 0 0
0 0 0 0 0 0 128
0 0 0 0 0 0 2
Length 7: 0 strings
100 

1.4 · 1011 2.5 · 1011 1.9 · 1011 1.4 · 1011 2.5 · 1011
0 1 0 0 0 0 1
1.9 · 1011 3.4 · 1011 2.5 · 1011 1.9 · 1011 3.4 · 1011
0 0 1 0 0 0 1



2.5 · 1011 4.4 · 1011 3.4 · 1011 2.5 · 1011 4.4 · 1011
0 0 0 1 1 0 0



1.4 · 1011 2.5 · 1011 1.9 · 1011 1.4 · 1011 2.5 · 1011
0 0 0 0 1 0 1
≈



1.9 · 1011 3.4 · 1011 2.5 · 1011 1.9 · 1011 3.4 · 1011
0 0 0 0 0 1 1



2.5 · 1011 4.4 · 1011 3.4 · 1011 2.5 · 1011 4.4 · 1011
1 1 0 0 0 0 0
0 0 0 0 0 0 2
0
0
0
0
0
11
Length 100: 335407875432 (≈ 3.354 · 10 ) strings

200 
0 1 0 0 0 0 1
2.4 · 1023 4.1 · 1023 3.1 · 1023 2.4 · 1023 4.1 · 1023
0 0 1 0 0 0 1
3.1 · 1023 5.5 · 1023 4.1 · 1023 3.1 · 1023 5.5 · 1023



0 0 0 1 1 0 0
4.1 · 1023 7.2 · 1023 5.5 · 1023 4.1 · 1023 7.2 · 1023



23
23
23
23
23
0 0 0 0 1 0 1
≈


2.4 · 1023 4.1 · 1023 3.1 · 1023 2.4 · 1023 4.1 · 1023
0 0 0 0 0 1 1
3.1 · 10
5.5 · 10
4.1 · 10
3.1 · 10
5.5 · 10



1 1 0 0 0 0 0
4.1 · 1023 7.2 · 1023 5.5 · 1023 4.1 · 1023 7.2 · 1023
0
0
0
0
0
0 0 0 0 0 0 2
23
Length 200: 547041013731037049032809 (≈ 5.470 · 10 ) strings
5.
first & sixth elements
(b).
1.9 · 1011
2.5 · 1011
3.4 · 1011
1.9 · 1011
2.5 · 1011
3.4 · 1011
0

1.3 · 1030
1.3 · 1030 

1.3 · 1030 

1.3 · 1030 

1.3 · 1030 

1.3 · 1030 
1.3 · 1030
3.1 · 1023
4.1 · 1023
5.5 · 1023
3.1 · 1023
4.1 · 1023
5.5 · 1023
0

1.6 · 1060
1.6 · 1060 

1.6 · 1060 

1.6 · 1060 

1.6 · 1060 

1.6 · 1060 
1.6 · 1060
a. If 0 steps are taken (starting from an arbitrary state), M will remain in the state it was in before, while M 0
starts in q00 , which has a 1 in the cells on the main diagonal (corresponding to q → q for each state q) & 0’s
elsewhere. So after 0 steps, the state of M 0 corresponds to the effect of 0 steps of M .
2
Suppose k steps have been taken, & the correspondence has until now been preserved. Then the transition
function of M 0 ensures that it will, after step k + 1 (with input a), encode that q → r is possible if & only if
q → s were previously possible for some state s for which s → r is a transition of M on input a. But this is
exactly the reachability for k + 1 steps of M , so after k + 1 steps, the state of M 0 corresponds to the effect of
k + 1 steps of M .
Thus by induction, the state of M 0 encodes the reachability of M for any number of steps. Now M accepts
a string if some accepting state can be reached from q0 with that string as input, while M 0 will accept after
receiving that string as input if there is a 1 in the q0 , q cell for some accepting state q, which is equivalent by
the above argument. So M & M 0 accept the same language.
b. When ε-transitions are allowed, the only changes necessary are to replace q00 with a matrix with 1 in the q, r
cell if & only if r can be reached from q via ε-transitions alone & to allow any number of ε-transitions of M
to be taken after the input-consuming transition of M in the definition of the transition function for M 0 . This
is required so that M 0 can simulate taking any number of ε-transitions between input-consuming transitions
of the NFA while consuming input at every step of M itself. It is sufficient because by construction, there are
no other states reachable from a given state by ε-transitions. The reason after is chosen (& the start state
updated) rather than before is to ensure that M 0 correctly accepts when M could take ε-transitions ending in
an accepting state.
3

Download Report