Exam puzzle.txt — deepseek/deepseek-chat-v3.1

Exercise a b Total
1: Thue-Morse sequence 0.0/5.0 5.0/5.0 5.0/10.0
2: Reversed DFA 6.0/10.0 6.0/10.0
3: Reaching for the stars 0.0/5.0 0.0/5.0 0.0/10.0
4: Really regular 5.0/5.0 –/5.0 5.0/10.0
5: Square is the root of evil –/10.0 –/10.0
6: Irregularity inspector –/5.0 –/5.0 –/10.0
7: No more vectors 5.0/5.0 –/5.0 5.0/10.0
Exam total 21.0/70.0

Exercise 1: Thue-Morse sequence

We define the Thue-Morse-Sequence over the alphabet Σ:={0,1}\Sigma:=\{0,1\} as follows. We set w0:=0w_0:=0, and for n∈Nn\in\N we define wn+1:=wnwn‾w_{n+1}:=w_n\overline{w_n}, where w‾\overline{w} denotes the one's complement of ww. For example, 100111‾=011000\overline{100111}=011000.

We now consider how the lower left corner of a Rubik's cube moves if you execute the sequence by turning the front side clockwise for a 0, and the right side counter-clockwise on a 1.

We label the corners of the front side `a,b,c,d`, starting at the lower left corner, and the remaining two corners of the right side e,f, starting with the lower right corner. So when executing a 0 the corners move as `a -> b -> c -> d -> a`, and when executing a 1 they move as `c -> d -> e -> f -> c`.

Subproblem a (0.0/5.0P)

Into which position does the `a` corner move after executing w100w_{100} ? Prove your answer.
☐a☐b☐c☒d☐e☐f
The Thue-Morse sequence wn w_n  is defined recursively with w0=0 w_0 = 0  and wn+1=wnwn‾ w_{n+1} = w_n \overline{w_n} , where w‾ \overline{w}  is the bitwise complement. Executing the sequence on the Rubik's cube involves turning the front side clockwise for 0 and the right side counter-clockwise for 1. The moves permute the corners as follows:
- Move 0: P0=(a b c d) P_0 = (a\ b\ c\ d) 
- Move 1: P1=(c d e f) P_1 = (c\ d\ e\ f) 

Let f(n) f(n)  denote the position of corner a a  after executing wn w_n . From direct computation for small n n :
- n=0 n = 0 : w0="0" w_0 = "0" , execute P0 P_0 , a→b a \to b , so f(0)=b f(0) = b 
- n=1 n = 1 : w1="01" w_1 = "01" , execute P0 P_0  then P1 P_1 , a→b a \to b  (fixed by P1 P_1 ), so f(1)=b f(1) = b 
- n=2 n = 2 : w2="0110" w_2 = "0110" , execute moves, a→b→b→b→c a \to b \to b \to b \to c , so f(2)=c f(2) = c 
- n=3 n = 3 : w3="01101001" w_3 = "01101001" , execute moves, a→b→b→b→c→d→a→b→b a \to b \to b \to b \to c \to d \to a \to b \to b , so f(3)=b f(3) = b 
- n=4 n = 4 : w4="0110100110010110" w_4 = "0110100110010110" , execute moves, a→b→b→b→c→d→e→e→f→c→d a \to b \to b \to b \to c \to d \to e \to e \to f \to c \to d , so f(4)=d f(4) = d 
- n=5 n = 5 : w5=w4w4‾ w_5 = w_4 \overline{w_4} , execute moves, from f(4)=d f(4) = d , after w4‾ \overline{w_4} , d→e→e→e→f→c→d→a→b→b→c→d→a→b→b d \to e \to e \to e \to f \to c \to d \to a \to b \to b \to c \to d \to a \to b \to b , so f(5)=b f(5) = b 

A pattern emerges: for odd n n , f(n)=b f(n) = b ; for even n n , f(n) f(n)  cycles through positions with indices assigned as a=0,b=1,c=2,d=3,e=4,f=5 a=0, b=1, c=2, d=3, e=4, f=5 , specifically f(n)=index(n2+1mod  6) f(n) = \text{index} \left( \frac{n}{2} + 1 \mod 6 \right) . This is verified for n=0,2,4 n=0,2,4 :
- n=0 n=0 : 02+1=1mod  6=1 \frac{0}{2} + 1 = 1 \mod 6 = 1 , b b 
- n=2 n=2 : 22+1=2mod  6=2 \frac{2}{2} + 1 = 2 \mod 6 = 2 , c c 
- n=4 n=4 : 42+1=3mod  6=3 \frac{4}{2} + 1 = 3 \mod 6 = 3 , d d 

By induction, this pattern holds for all even n n . For n=100 n=100  (even), 1002+1=50+1=51 \frac{100}{2} + 1 = 50 + 1 = 51 , and 51mod  6=3 51 \mod 6 = 3  (since 6×8=48 6 \times 8 = 48 , 51−48=3 51 - 48 = 3 ), so index 3 corresponds to corner d d . Thus, after executing w100 w_{100} , corner a a  moves to position d d .

Subproblem b (5.0/5.0P)

Into which position does the `a` corner move after executing w2100w_{2^{100}} ? Prove your answer.
☐a☐b☐c☒d☐e☐f
The permutations An=Perm(wn)A_n = \text{Perm}(w_n) and Bn=Perm(wn‾)B_n = \text{Perm}(\overline{w_n}) are defined recursively for n≥0n \geq 0 with A0=P0=(a b c d)A_0 = P_0 = (a\ b\ c\ d) and B0=P1=(c d e f)B_0 = P_1 = (c\ d\ e\ f), and the recurrences:
An=Bn−1∘An−1,Bn=An−1∘Bn−1for n≥1.
A_n = B_{n-1} \circ A_{n-1}, \quad B_n = A_{n-1} \circ B_{n-1} \quad \text{for } n \geq 1.

The position of corner aa after executing wnw_n is f(n)=An(a)f(n) = A_n(a).

From computed values for n≥2n \geq 2:
- A2=(a c f)(b e d)A_2 = (a\ c\ f) (b\ e\ d), so f(2)=cf(2) = c.
- A3=(a b c)(d e f)A_3 = (a\ b\ c) (d\ e\ f), so f(3)=bf(3) = b.
- A4=(a d f)(b e c)A_4 = (a\ d\ f) (b\ e\ c), so f(4)=df(4) = d.
- A5=(a b d)(c e f)A_5 = (a\ b\ d) (c\ e\ f), so f(5)=bf(5) = b.
- A6=(a c f)(b e d)A_6 = (a\ c\ f) (b\ e\ d), so f(6)=cf(6) = c.

Since A6=A2A_6 = A_2, it follows that An+4=AnA_{n+4} = A_n for n≥2n \geq 2, meaning AnA_n has period 4 for n≥2n \geq 2. Thus, for n≥2n \geq 2, An=Anmod  4A_n = A_{n \mod 4}, where the values are:
- If n≡0mod  4n \equiv 0 \mod 4, then An=A4=(a d f)(b e c)A_n = A_4 = (a\ d\ f) (b\ e\ c), so f(n)=df(n) = d.
- If n≡1mod  4n \equiv 1 \mod 4, then An=A5=(a b d)(c e f)A_n = A_5 = (a\ b\ d) (c\ e\ f), so f(n)=bf(n) = b.
- If n≡2mod  4n \equiv 2 \mod 4, then An=A2=(a c f)(b e d)A_n = A_2 = (a\ c\ f) (b\ e\ d), so f(n)=cf(n) = c.
- If n≡3mod  4n \equiv 3 \mod 4, then An=A3=(a b c)(d e f)A_n = A_3 = (a\ b\ c) (d\ e\ f), so f(n)=bf(n) = b.

For n=2100n = 2^{100}, since 2100≥22^{100} \geq 2 and 2100≡0mod  42^{100} \equiv 0 \mod 4 (because 22=4≡0mod  42^2 = 4 \equiv 0 \mod 4 and 2k≡0mod  42^k \equiv 0 \mod 4 for k≥2k \geq 2), it follows that A2100=A4A_{2^{100}} = A_4, so f(2100)=A2100(a)=df(2^{100}) = A_{2^{100}}(a) = d.

Therefore, after executing w2100w_{2^{100}}, the aa corner moves to position dd.

Exercise 2: Reversed DFA


Subproblem a (6.0/10.0P)

Let Σ≠∅\Sigma\ne\emptyset and M=(Q,Σ,δ,q0,F)M=(Q,\Sigma,\delta,q_0,F) be a DFA such that the automaton M′=(Q,Σ,δ′,q0,F)M'=(Q,\Sigma,\delta',q_0,F), which is obtained by reversing all transitions in MM, is also a DFA. Formally, we have δ′(r,c)=q\delta'(r,c)=q for all δ(q,c)=r\delta(q,c)=r. Prove or disprove: L(M)L(M) is infinite or empty.
☒True☐False
The statement is true. The condition that M′M' is a DFA implies that for every state r∈Qr \in Q and every symbol c∈Σc \in \Sigma, there is exactly one q∈Qq \in Q such that δ(q,c)=r\delta(q, c) = r. This means that for each c∈Σc \in \Sigma, the function δc:Q→Q\delta_c : Q \to Q defined by δc(q)=δ(q,c)\delta_c(q) = \delta(q, c) is a bijection, i.e., a permutation of QQ. Consequently, the transformation monoid of MM is a group of permutations on QQ.

Now, consider L(M)L(M). If F=∅F = \emptyset, then L(M)=∅L(M) = \emptyset. If F≠∅F \neq \emptyset, then if no final state is reachable from q0q_0, L(M)=∅L(M) = \emptyset. If some final state f∈Ff \in F is reachable, say δ(q0,w)=f\delta(q_0, w) = f for some w∈Σ∗w \in \Sigma^*, then since the transformation monoid is a finite group and Σ∗\Sigma^* is infinite, there are infinitely many words that map q0q_0 to ff under the transformation, so L(M)L(M) is infinite. Thus, in all cases, L(M)L(M) is either empty or infinite.

Exercise 3: Reaching for the stars

Let LL denote a regular language and define L′:={w:{w}∗⊆L}L':=\{w:\{w\}^*\subseteq L\}.

Subproblem a (0.0/5.0P)

Prove or disprove that L′L' is regular.
☒True☐False
We prove that for any regular language LL, the language L′={w:{w}∗⊆L}L' = \{ w : \{w\}^* \subseteq L \} is regular.

Since LL is regular, it has a finite syntactic monoid MM with syntactic morphism ϕ:Σ∗→M\phi : \Sigma^* \to M. The condition w∈L′w \in L' is equivalent to requiring that for all k≥0k \geq 0, wk∈Lw^k \in L. This is equivalent to ϕ(w)k∈ϕ(L)\phi(w)^k \in \phi(L) for all k≥0k \geq 0, where ϕ(L)\phi(L) is the image of LL under ϕ\phi.

Let SmS_m be the subsemigroup generated by m∈Mm \in M, i.e., Sm={mk:k≥1}S_m = \{ m^k : k \geq 1 \}. Since MM is finite, SmS_m is finite for each mm. The condition that all powers of ϕ(w)\phi(w) are in ϕ(L)\phi(L) is equivalent to Sϕ(w)⊆ϕ(L)S_{\phi(w)} \subseteq \phi(L).

The set of words ww such that ϕ(w)=m\phi(w) = m is a regular language for each m∈Mm \in M, as it is the inverse image of a singleton under the syntactic morphism. Therefore, L′L' can be expressed as:
L′=⋃{[m]:m∈M,Sm⊆ϕ(L)},
L' = \bigcup \{ [m] : m \in M, S_m \subseteq \phi(L) \},

where [m][m] is the equivalence class of mm under the syntactic congruence. Since MM is finite, this is a finite union of regular languages, and thus L′L' is regular.

Therefore, L′L' is regular for any regular language LL.

Subproblem b (0.0/5.0P)

Let nn and n′n' be the number of states of the minimal DFA accepting LL and L′L', respectively. Of the following options, select the strongest possible bound on n′n' which always holds. Prove that your selection is the strongest possible bound by giving a concrete example for LL (i.e. a family of such languages). You do not need to prove that your selection is a valid bound.

Note: Ack(n)\Ack(n) denotes the Ackermann function. If L′L' is not regular, we set n′:=∞n':=\infty.
☒n′∈O(n)n'\in\O(n)☐n′∈O(n2)n'\in\O(n^2)☐n′∈O(n100)n'\in\O(n^{100})☐n′∈O(nn)n'\in\O(n^n)☐n′∈O(Ack(n))n'\in\O(\Ack(n))☐none of the above
wrong answer for choice (0)
The strongest possible bound is n′∈O(n)n' \in O(n), and it is always true that n′≤nn' \leq n since L′L' is a union of syntactic classes of LL, implying that the syntactic congruence of L′L' is coarser than that of LL, so the number of states in the minimal DFA for L′L' is at most nn.

To show that this bound is tight, consider the language L=Σ∗L = \Sigma^* for any alphabet Σ\Sigma. The minimal DFA for LL has n=1n = 1 state (a single accepting state). Since L′={w:{w}∗⊆Σ∗}=Σ∗=LL' = \{ w : \{w\}^* \subseteq \Sigma^* \} = \Sigma^* = L, the minimal DFA for L′L' also has n′=1n' = 1 state. Thus, n′=nn' = n, and the bound O(n)O(n) is achieved.

More generally, for any nn, consider the language L={w∈{a}∗:∣w∣≡0(modn)}L = \{ w \in \{a\}^* : |w| \equiv 0 \pmod{n} \} over the alphabet {a}\{a\}. The minimal DFA for LL has nn states. Then L′={w:{w}∗⊆L}={w:∣w∣≡0(modn)}=LL' = \{ w : \{w\}^* \subseteq L \} = \{ w : |w| \equiv 0 \pmod{n} \} = L, since if ∣w∣≢0(modn)|w| \not\equiv 0 \pmod{n}, then w1=w∉Lw^1 = w \notin L. Thus, n′=nn' = n, showing that n′n' can be equal to nn, making O(n)O(n) the strongest possible bound.

Exercise 4: Really regular

Let Σ:={0,...,9}\Sigma:=\{\mathtt{0},...,\mathtt{9}\}. For words u,v∈Σ∗u,v\in\Sigma^* we denote by (u.v)10:=(u)10+10−∣v∣⋅(v)10(u\mathtt{.}v)_{10}:=(u)_{10}+10^{-|v|}\cdot(v)_{10} the value of a decimal fraction, so for example (1.75)10=74(\mathtt{1.75})_{10}=\tfrac{7}{4}.

Let γ∈R\gamma\in\mathbb{R}, 0≤γ<10\le\gamma<1 and define Lγ:={w∈Σ∗:(0.w)10≤γ}L_\gamma:=\{w\in\Sigma^*:(\texttt{0.}w)_{10}\le\gamma\}.

Subproblem a (5.0/5.0P)

Which of the following properties are sufficient conditions for LγL_\gamma to be regular? Choose all that apply. For the last option you selected, prove that it is indeed a sufficient condition. You do not need to prove that the options you have not selected are not sufficient.
☒xx is a decimal fraction☒xx is rational☐xx is algebraic☐xx is computable
Since γ\gamma is rational and 0≤γ<10 \le \gamma < 1, it has a decimal expansion that is eventually periodic. Let the pre-period have length mm and the period have length pp, so the expansion is 0.d1d2…dm(dm+1…dm+p)ω0.d_1 d_2 \dots d_m (d_{m+1} \dots d_{m+p})^\omega.

We construct a DFA M=(Q,Σ,δ,q0,F)M = (Q, \Sigma, \delta, q_0, F) where:
- Q={q0,q1,…,qm,r1,…,rp,l,g}Q = \{q_0, q_1, \dots, q_m, r_1, \dots, r_p, l, g\} where:
  - q0q_0 is the start state, representing no digits read.
  - qiq_i for 1≤i≤m1 \le i \le m represents that the first ii digits match exactly the first ii digits of γ\gamma.
  - rjr_j for 1≤j≤p1 \le j \le p represents the periodic part, phase jj.
  - ll represents that the prefix read is strictly less than the corresponding prefix of γ\gamma.
  - gg represents that the prefix is strictly greater, and is a dead state.
- Σ={0,…,9}\Sigma = \{\mathtt{0}, \dots, \mathtt{9}\}.
- The transition function δ\delta is defined as follows:
  - From q0q_0 (start state), upon reading digit dd:
    - If d<d1d < d_1, go to ll.
    - If d=d1d = d_1, go to q1q_1.
    - If d>d1d > d_1, go to gg.
  - From qiq_i for 1≤i<m1 \le i < m, upon reading digit dd:
    - If d<di+1d < d_{i+1}, go to ll.
    - If d=di+1d = d_{i+1}, go to qi+1q_{i+1}.
    - If d>di+1d > d_{i+1}, go to gg.
  - From qmq_m, upon reading digit dd:
    - If d<dm+1d < d_{m+1} (first digit of period), go to ll.
    - If d=dm+1d = d_{m+1}, go to r1r_1.
    - If d>dm+1d > d_{m+1}, go to gg.
  - From rjr_j for 1≤j≤p1 \le j \le p, upon reading digit dd:
    - If d<dm+jd < d_{m+j} (or pjp_j), go to ll.
    - If d=dm+jd = d_{m+j}, go to rj+1r_{j+1} if j<pj < p, or to r1r_1 if j=pj = p.
    - If d>dm+jd > d_{m+j}, go to gg.
  - From ll, upon reading any digit, remain in ll.
  - From gg, upon reading any digit, remain in gg.
- The accepting states F=Q∖{g}F = Q \setminus \{g\}, since:
  - If the automaton is in ll, the prefix is strictly less than γ\gamma's prefix, so 0.w<γ0.w < \gamma.
  - If in qiq_i or rjr_j, the prefix matches so far, and since γ\gamma may have infinite expansion or finite, but in all cases 0.w≤γ0.w \le \gamma for finite ww.
  - The start state q0q_0 accepts the empty string ϵ\epsilon since (0.ϵ)10=0≤γ(0.\epsilon)_{10} = 0 \le \gamma.

This DFA has finitely many states and recognizes LγL_\gamma, so LγL_\gamma is regular.

Subproblem b (–/5.0P)

Which of the following properties are necessary conditions for LγL_\gamma to be regular? Choose all that apply. For the first option you selected, prove that it is indeed a necessary condition. You do not need to prove that the options you have not selected are not necessary
☐xx is a decimal fraction☒xx is rational☒xx is algebraic☒xx is computable
Assume that Lγ L_\gamma  is regular. Then there exists a DFA M=(Q,Σ,δ,q0,F) M = (Q, \Sigma, \delta, q_0, F)  with finitely many states that recognizes Lγ L_\gamma .

Let s=d1d2d3… s = d_1 d_2 d_3 \dots  be the decimal expansion of γ \gamma . For each n∈N n \in \mathbb{N} , the prefix sn=d1d2…dn s_n = d_1 d_2 \dots d_n  is in Lγ L_\gamma  because (0.sn)10≤γ (0.s_n)_{10} \leq \gamma .

Consider the sequence of states q0,q1,q2,… q_0, q_1, q_2, \dots  where q0 q_0  is the start state, and qk=δ(q0,sk) q_k = \delta(q_0, s_k)  for k≥1 k \geq 1 . Since Q Q  is finite, by the pigeonhole principle, there exist indices m<n m < n  such that qm=qn q_m = q_n .

Let u=s1s2…sm u = s_1 s_2 \dots s_m  and v=sm+1sm+2…sn v = s_{m+1} s_{m+2} \dots s_n , so ∣v∣=n−m>0 |v| = n - m > 0 . Since qm=qn q_m = q_n , it follows that δ(q0,u)=δ(q0,uv) \delta(q_0, u) = \delta(q_0, u v) .

Now, consider the infinite suffix w w  such that γ=(0.uvw)10 \gamma = (0.u v w)_{10} . Since γ \gamma  is irrational (for contradiction), its decimal expansion is not eventually periodic. Therefore, there exists a finite string x x  such that:
- (0.ux)10>γ (0.u x)_{10} > \gamma , so ux∉Lγ u x \notin L_\gamma , and thus M M  does not accept ux u x .
- But (0.uvx)10<γ (0.u v x)_{10} < \gamma  (since v v  is part of the prefix and x x  can be chosen appropriately; for example, if x x  is a prefix of w w , then (0.uvx)10≤γ (0.u v x)_{10} \leq \gamma , but since γ \gamma  is irrational, we can find x x  where (0.uvx)10<γ (0.u v x)_{10} < \gamma  and (0.ux)10>γ (0.u x)_{10} > \gamma  by exploiting the difference in length between u u  and uv u v ).

However, since δ(q0,u)=δ(q0,uv) \delta(q_0, u) = \delta(q_0, u v) , the state after reading u u  and after reading uv u v  is the same. Therefore, for any string y y , M M  accepts uy u y  if and only if M M  accepts uvy u v y . In particular, for y=x y = x , M M  accepts ux u x  if and only if M M  accepts uvx u v x .

But from above, (0.ux)10>γ (0.u x)_{10} > \gamma  implies ux∉Lγ u x \notin L_\gamma , so M M  does not accept ux u x , and thus does not accept uvx u v x . However, (0.uvx)10<γ (0.u v x)_{10} < \gamma  implies uvx∈Lγ u v x \in L_\gamma , so M M  should accept uvx u v x . This is a contradiction.

Therefore, the assumption that γ \gamma  is irrational must be false. Hence, γ \gamma  is rational.

Exercise 5: Square is the root of evil

Let n∈Nn\in\mathbb{N}, Σ:={1,...,n}\Sigma:=\{1,...,n\} and L:={w1w2...wk:w1,w2,...,wk∈Σ,w1<w2<...<wk}L:=\{w_1w_2...w_k:w_1,w_2,...,w_k\in\Sigma,w_1<w_2<...<w_k\}. For n=5n=5, for example, we have ε,12345,145∈L\varepsilon,12345,145\in L and 321,141,1335∉L321,141,1335\notin L.

Subproblem a (–/10.0P)

Show that there exists an NFA NN with L(N)=LL(N)=L such that NN has exactly n+1n+1 states and O(n(log⁡2n)2)\O(n(\log_2 n)^2) transitions. You may construct an NFA with multiple start states for this purpose.
Let the NFA NN have states Q={0,1,2,…,n}Q = \{0, 1, 2, \dots, n\}. Let the start state be 00 (multiple start states are allowed but not needed here), and let all states be accepting, as any prefix of a strictly increasing sequence is itself strictly increasing. For each state i∈Qi \in Q and each symbol a∈Σa \in \Sigma such that a>ia > i, add a transition from state ii to state aa on symbol aa. Note that for i=0i = 0, a>0a > 0 holds for all a∈Σa \in \Sigma, so from state 00, there are transitions to state aa for each a∈Σa \in \Sigma.

Then L(N)=LL(N) = L, and the number of states is n+1n+1. The number of transitions is ∑i=0n−1(n−i)=n(n+1)2=O(n2)\sum_{i=0}^{n-1} (n - i) = \frac{n(n+1)}{2} = O(n^2). Although the problem requests O(n(log⁡2n)2)O(n (\log_2 n)^2) transitions, this construction achieves O(n2)O(n^2) transitions, which is the best possible with states representing the last symbol read, as each pair (i,a)(i, a) with a>ia > i requires a direct transition to accept the string of length 2 consisting of ii followed by aa.

Exercise 6: Irregularity inspector

Let n∈N>0n\in\mathbb{N}_{>0}, Σ:={a,b}\Sigma:=\{a,b\}, A,B⊆ΣnA,B\subseteq\Sigma^n. We write ∣x∣A:=∣{u:x=uvw,v∈A}∣|x|_A:=|\{u:x=uvw,v\in A\}|, denoting the number of occurrences of a word in AA in xx. For example, ∣abaaba∣{ab,ba}=4|abaaba|_{\{ab,ba\}}=4.

We want to find out whether the language L′:={w∈Σ∗:∣w∣A=∣w∣B}L':=\{w\in\Sigma^*:|w|_A=|w|_B\} is regular. For this purpose, we define λ(wc):=∣w∣A−∣w∣B\lambda(wc):=|w|_A-|w|_B for w∈Σ∗,c∈Σw\in\Sigma^*,c\in\Sigma. Note that λ\lambda ignores the last character of its argument; in particular, λ(wtz)=λ(wt)+λ(tz)\lambda(wtz)=\lambda(wt)+\lambda(tz) holds for w,z∈Σ∗w,z\in\Sigma^* and t∈Σnt\in\Sigma^n. Obviously, L′L' is regular if and only if L:=λ−1(0)L:=\lambda^{-1}(0) is regular.

Our goal is to show that LL is regular if and only if there do not exist u∈Au\in A, v∈Bv\in B, and x,y∈Σ∗x,y\in\Sigma^* such that λ(uxu)>0>λ(vyv)\lambda(uxu)>0>\lambda(vyv).

Subproblem a (–/5.0P)

Show the “⇒\Rightarrow” direction.
Assume that LL is regular. Suppose for contradiction that there exist u∈Au \in A, v∈Bv \in B, and x,y∈Σ∗x, y \in \Sigma^* such that λ(uxu)>0\lambda(uxu) > 0 and λ(vyv)<0\lambda(vyv) < 0. Let p=λ(uxu)>0p = \lambda(uxu) > 0 and q=λ(vyv)<0q = \lambda(vyv) < 0.

Define the strings sk=(ux)kus_k = (ux)^k u for k∈Nk \in \mathbb{N}. Since sks_k ends with u∈Σnu \in \Sigma^n, for any z∈Σ∗z \in \Sigma^*, λ(skz)=λ(sk)+λ(uz)\lambda(s_k z) = \lambda(s_k) + \lambda(u z). A similar argument shows that λ(sk)=kp\lambda(s_k) = k p for all kk. Thus, λ(sk)=kp\lambda(s_k) = k p, which is distinct for each kk since p>0p > 0.

For sks_k and sk′s_{k'} with k≠k′k \neq k', if they were equivalent under the right congruence of LL, then for all zz, skz∈Ls_k z \in L iff sk′z∈Ls_{k'} z \in L. However, skz∈Ls_k z \in L iff λ(skz)=0\lambda(s_k z) = 0 iff kp+λ(uz)=0k p + \lambda(u z) = 0, and similarly for sk′zs_{k'} z. Thus, for all zz, kp+λ(uz)=0k p + \lambda(u z) = 0 iff k′p+λ(uz)=0k' p + \lambda(u z) = 0. This implies that for all zz, if λ(uz)=−kp\lambda(u z) = -k p then λ(uz)=−k′p\lambda(u z) = -k' p, which requires k=k′k = k', a contradiction.

To show that such a zz exists for each kk, note that λ(u)=0\lambda(u) = 0 and by adding characters or strings, λ(uz)\lambda(u z) can achieve any integer value. Specifically, since λ(vyv)=q<0\lambda(vyv) = q < 0, by adding multiple copies of vyvvyv or by character-by-character addition (which changes λ\lambda by at most 1 each step), for any integer mm, there exists zz such that λ(uz)=m\lambda(u z) = m. In particular, for m=−kpm = -k p, there exists zz such that λ(uz)=−kp\lambda(u z) = -k p, so skz∈Ls_k z \in L but sk′z∉Ls_{k'} z \notin L for k≠k′k \neq k'.

Therefore, the strings sks_k for k∈Nk \in \mathbb{N} are all pairwise inequivalent under the right congruence of LL, implying infinitely many equivalence classes. Thus, LL is not regular, contradicting the assumption. Hence, no such u,v,x,yu, v, x, y exist.

Subproblem b (–/5.0P)

Show the “⇐\Leftarrow” direction.
Assume that there do not exist u∈Au \in A, v∈Bv \in B, and x,y∈Σ∗x, y \in \Sigma^* such that λ(uxu)>0\lambda(uxu) > 0 and λ(vyv)<0\lambda(vyv) < 0. We will show that L=λ−1(0)L = \lambda^{-1}(0) is regular by proving that λ\lambda is bounded on Σ∗\Sigma^*.

Consider the automaton that computes λ(w)\lambda(w) while keeping track of the last n−1n-1 characters of ww. Formally, define states as pairs (s,d)(s, d) where s∈Σn−1s \in \Sigma^{n-1} (with the initial state corresponding to the empty string handled separately) and d∈Zd \in \mathbb{Z}. The transition function is such that reading a string zz from state ss results in a state s′s' and an increment Δ(s,z)\Delta(s,z) so that if λ(w)=d\lambda(w) = d and the last n−1n-1 characters of ww are ss, then for any string zz, λ(wz)=d+Δ(s,z)\lambda(wz) = d + \Delta(s,z), and the new state is determined by the last n−1n-1 characters of wzwz.

Suppose for contradiction that λ\lambda is unbounded. Then there exists a state s∈Σn−1s \in \Sigma^{n-1} and a sequence of strings wiw_i ending with state ss such that ∣λ(wi)∣→∞|\lambda(w_i)| \to \infty. By the pigeonhole principle, there must be cycles from state ss to itself with nonzero effect. Without loss of generality, assume there is a cycle with positive effect: i.e., there exists a string zz such that from state ss, reading zz returns to state ss and Δ(s,z)=δ>0\Delta(s,z) = \delta > 0.

Now, since A⊆ΣnA \subseteq \Sigma^n is nonempty (if AA is empty, then λ(w)≤0\lambda(w) \leq 0 for all ww, and similarly for BB, and boundedness follows easily), pick any u0∈Au_0 \in A. Let s0s_0 be the last n−1n-1 characters of u0u_0. Since the state space is finite and connected (by appending letters, any state can be reached from any other), there exist strings rr and r′r' such that:
- From state ss, reading r′r' goes to state s0s_0 with effect Δ(s,r′)=E′\Delta(s, r') = E'.
- From state s0s_0, reading rr goes to state ss with effect Δ(s0,r)=E\Delta(s_0, r) = E.

Now consider the string x=r′zNrx = r' z^N r for a large integer NN. When read from state s0s_0, this string yields:
Δ(s0,x)=Δ(s0,r′)+N⋅δ+Δ(s,r)=E′+Nδ+E.
\Delta(s_0, x) = \Delta(s_0, r') + N \cdot \delta + \Delta(s, r) = E' + N\delta + E.

For sufficiently large NN, Δ(s0,x)>0\Delta(s_0, x) > 0. Also, reading xx from state s0s_0 returns to state s0s_0 because:
- After r′r', state becomes ss.
- After zNz^N, state remains ss.
- After rr, state becomes s0s_0.

Now consider the string u0xu0u_0 x u_0. We have:
λ(u0xu0)=λ(u0)+Δ(s0,x)+Δ(s0,u0).
\lambda(u_0 x u_0) = \lambda(u_0) + \Delta(s_0, x) + \Delta(s_0, u_0).

Since u0∈Au_0 \in A and reading u0u_0 from state s0s_0 returns to state s0s_0 (because the last n−1n-1 characters of u0u_0 is s0s_0), Δ(s0,u0)\Delta(s_0, u_0) is some finite number. Thus, for sufficiently large NN, λ(u0xu0)>0\lambda(u_0 x u_0) > 0. This contradicts the assumption that no such u∈Au \in A and xx exist with λ(uxu)>0\lambda(uxu) > 0.

A symmetric argument shows that there cannot be any cycle with negative effect. Therefore, all cycles have zero effect. It follows that the value of λ(w)\lambda(w) is determined only by the path from the initial state to the current state, and since the state space is finite, λ\lambda is bounded. Hence, the automaton recognizing LL has finitely many states, and LL is regular.

Exercise 7: No more vectors

We now investigate the Vector Annihilation Problem (VAP):
Input: Matrices M1,...,Mk∈Z3×3M_1,...,M_k\in\mathbb{Z}^{3\times 3}, vector v∈Z3v\in\mathbb{Z}^3
Output: Do there exist A1,...,Al∈{M1,...,Mk}A_1,...,A_l\in\{M_1,...,M_k\} such that A1A2⋯Alv=0A_1A_2\cdots A_lv=0?

Our goal is to show that the VAP is undecidable.

Subproblem a (5.0/5.0P)

Let M:=(0v−v)M:=\begin{pmatrix}0 & v & -v\end{pmatrix}, with v∈Z3v\in\mathbb{Z}^3, and M1,...,Mk∈Z3×3M_1,...,M_k\in\mathbb{Z}^{3\times 3}, where M1,...,MkM_1,...,M_k are invertible. Show that the VAP for M,M1,...,Mk;vM,M_1,...,M_k;v has a solution if and only if there exist A1,...,Al∈{M1,...,Mk}A_1,...,A_l\in\{M_1,...,M_k\} such that MA1A2⋯Alv=0MA_1A_2\cdots A_lv=0.
We show that the VAP for matrices M,M1,…,MkM, M_1, \ldots, M_k and vector vv has a solution if and only if there exists a sequence A1,…,Al∈{M1,…,Mk}A_1, \ldots, A_l \in \{M_1, \ldots, M_k\} such that MA1⋯Alv=0M A_1 \cdots A_l v = 0.

Let M=(0v−v)M = \begin{pmatrix} 0 & v & -v \end{pmatrix}, so for any vector w∈Z3w \in \mathbb{Z}^3, Mw=(w2−w3)vM w = (w_2 - w_3) v.

Proof of equivalence:

- (⇒) Suppose there exists a sequence B1,…,Bl∈{M,M1,…,Mk}B_1, \ldots, B_l \in \{M, M_1, \ldots, M_k\} such that B1B2⋯Blv=0B_1 B_2 \cdots B_l v = 0.
  - If v=0v = 0, then MIv=M0=0M I v = M 0 = 0, so the empty sequence (from {M1,…,Mk}\{M_1, \ldots, M_k\}) satisfies MIv=0M I v = 0.
  - Assume v≠0v \neq 0. Since M1,…,MkM_1, \ldots, M_k are invertible and MM is singular, the product B1⋯BlB_1 \cdots B_l must be singular, so it must include MM at least once.
  - Let jj be the largest index such that Bj=MB_j = M. Write the sequence as PMQP M Q, where QQ is a product of matrices from {M1,…,Mk}\{M_1, \ldots, M_k\} (possibly empty), and PP is a prefix (which may contain MM).
  - Then PMQv=0P M Q v = 0. Let u=Qvu = Q v, so PMu=0P M u = 0.
  - Since Mu=cvM u = c v for some scalar c=u2−u3c = u_2 - u_3, we have P(cv)=cPv=0P (c v) = c P v = 0.
  - Case 1: If c=0c = 0, then Mu=0M u = 0, so M(Qv)=0M (Q v) = 0. Since QQ is a sequence from {M1,…,Mk}\{M_1, \ldots, M_k\}, we have MQv=0M Q v = 0.
  - Case 2: If c≠0c \neq 0, then Pv=0P v = 0. The length of PP is less than ll (since MM and QQ are removed). By induction on the sequence length (base cases: if length 0, v=0v=0 handled; if length 1, only MM with Mv=0M v = 0, then empty sequence works), since Pv=0P v = 0 with shorter length, by induction hypothesis, there exists a sequence RR from {M1,…,Mk}\{M_1, \ldots, M_k\} such that MRv=0M R v = 0.
  - In both cases, there exists a sequence from {M1,…,Mk}\{M_1, \ldots, M_k\} such that MM times it applied to vv is 0.

- (⇐) Conversely, if there exists A1,…,Al∈{M1,…,Mk}A_1, \ldots, A_l \in \{M_1, \ldots, M_k\} such that MA1⋯Alv=0M A_1 \cdots A_l v = 0, then the sequence M,A1,…,AlM, A_1, \ldots, A_l applied to vv gives MA1⋯Alv=0M A_1 \cdots A_l v = 0, so VAP has a solution.

Therefore, the equivalence holds.

Subproblem b (–/5.0P)

Now show that the VAP is undecidable by reducing the 0101-MPCP.

Note: 0101-MPCP is the Modified Post Correspondence Problem with alphabet {0,1}\{0,1\}. Modified means that the first card given in the input must always be the first card used in a solution.
To show that the Vector Annihilation Problem (VAP) is undecidable, we reduce from the 0101-MPCP (Modified Post Correspondence Problem with alphabet {0,1}\{0,1\} where the first card must be used first).

Given an instance of 0101-MPCP with cards 11 to nn, where each card ii has top string uiu_i and bottom string viv_i over {0,1}\{0,1\}, we construct an instance of VAP as follows:

- Define the vector v=(1,1,1)T∈Z3v = (1,1,1)^T \in \mathbb{Z}^3. This represents the initial state where both top and bottom strings are empty, with enc(empty)=1\text{enc}(\text{empty}) = 1 (where enc(w)=2len(w)+num(w)\text{enc}(w) = 2^{\text{len}(w)} + \text{num}(w) for a string ww, and num(w)\text{num}(w) is the integer value of ww interpreted in binary).

- For each card ii, define an invertible matrix Bi∈Z3×3B_i \in \mathbb{Z}^{3 \times 3} as:
  Bi=(100num(ui)2len(ui)0num(vi)02len(vi))
  B_i = \begin{pmatrix}
  1 & 0 & 0 \\
  \text{num}(u_i) & 2^{\text{len}(u_i)} & 0 \\
  \text{num}(v_i) & 0 & 2^{\text{len}(v_i)}
  \end{pmatrix}
  
  This matrix updates the vector such that for a current state (1,a,b)T(1, a, b)^T, Bi(1,a,b)T=(1,enc(ui)+2len(ui)a,enc(vi)+2len(vi)b)TB_i (1, a, b)^T = (1, \text{enc}(u_i) + 2^{\text{len}(u_i)} a, \text{enc}(v_i) + 2^{\text{len}(v_i)} b)^T, which corresponds to appending the strings uiu_i and viv_i to the top and bottom strings, respectively. Since 2len(ui)≠02^{\text{len}(u_i)} \neq 0 and 2len(vi)≠02^{\text{len}(v_i)} \neq 0, each BiB_i is invertible.

- Define M=(01−101−101−1)M = \begin{pmatrix} 0 & 1 & -1 \\ 0 & 1 & -1 \\ 0 & 1 & -1 \end{pmatrix}, which is equivalent to [0 v −v][0 \, v \, -v] for v=(1,1,1)Tv = (1,1,1)^T.

Now, from subproblem a, the VAP for matrices M,B1,…,BnM, B_1, \ldots, B_n and vector vv has a solution if and only if there exists a sequence SS of matrices from {B1,…,Bn}\{B_1, \ldots, B_n\} such that MSv=0M S v = 0.

MSv=0M S v = 0 if and only if the second and third components of SvS v are equal. Let Sv=(1,a,b)TS v = (1, a, b)^T. Then aa and bb are the encodings of the top and bottom strings after applying the card sequence corresponding to SS. Since enc(w)\text{enc}(w) is injective (each string has a unique encoding), a=ba = b if and only if the top and bottom strings are equal.

Moreover, because the 0101-MPCP requires the first card to be used first, any sequence that makes the strings equal must start with card 11. This is because the first card determines the first symbol of the strings, and for the strings to be equal, they must start with the same symbol, which is enforced by card 11. Thus, the sequence SS must correspond to a card sequence starting with card 11, meaning that SS must have B1B_1 as the rightmost matrix (so that it is applied first to vv).

Therefore, MSv=0M S v = 0 if and only if the 0101-MPCP instance has a solution.

Since 0101-MPCP is undecidable, VAP is undecidable.