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 nNn\in\N we define wn+1:=wnwnw_{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.
abcdef
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 , ab 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 , ab 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, abbbc 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, abbbcdabb 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, abbbcdeefcd 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} , deeefcdabbcdabb 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+1mod6) 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=1mod6=1 \frac{0}{2} + 1 = 1 \mod 6 = 1 , b b 
- n=2 n=2 : 22+1=2mod6=2 \frac{2}{2} + 1 = 2 \mod 6 = 2 , c c 
- n=4 n=4 : 42+1=3mod6=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 51mod6=3 51 \mod 6 = 3  (since 6×8=48 6 \times 8 = 48 , 5148=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.
abcdef
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 n0n \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=Bn1An1,Bn=An1Bn1for n1.
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 n2n \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 n2n \geq 2, meaning AnA_n has period 4 for n2n \geq 2. Thus, for n2n \geq 2, An=Anmod4A_n = A_{n \mod 4}, where the values are:
- If n0mod4n \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 n1mod4n \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 n2mod4n \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 n3mod4n \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 210022^{100} \geq 2 and 21000mod42^{100} \equiv 0 \mod 4 (because 22=40mod42^2 = 4 \equiv 0 \mod 4 and 2k0mod42^k \equiv 0 \mod 4 for k2k \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.
TrueFalse
The statement is true. The condition that MM' is a DFA implies that for every state rQr \in Q and every symbol cΣc \in \Sigma, there is exactly one qQq \in Q such that δ(q,c)=r\delta(q, c) = r. This means that for each cΣc \in \Sigma, the function δc:QQ\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 FF \neq \emptyset, then if no final state is reachable from q0q_0, L(M)=L(M) = \emptyset. If some final state fFf \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 LL' is regular.
TrueFalse
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 wLw \in L' is equivalent to requiring that for all k0k \geq 0, wkLw^k \in L. This is equivalent to ϕ(w)kϕ(L)\phi(w)^k \in \phi(L) for all k0k \geq 0, where ϕ(L)\phi(L) is the image of LL under ϕ\phi.

Let SmS_m be the subsemigroup generated by mMm \in M, i.e., Sm={mk:k1}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 mMm \in M, as it is the inverse image of a singleton under the syntactic morphism. Therefore, LL' can be expressed as:
L={[m]:mM,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 LL' is regular.

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

Subproblem b (0.0/5.0P)

Let nn and nn' be the number of states of the minimal DFA accepting LL and LL', respectively. Of the following options, select the strongest possible bound on nn' 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 LL' is not regular, we set n:=n':=\infty.
nO(n)n'\in\O(n)nO(n2)n'\in\O(n^2)nO(n100)n'\in\O(n^{100})nO(nn)n'\in\O(n^n)nO(Ack(n))n'\in\O(\Ack(n))none of the above
wrong answer for choice (0)
The strongest possible bound is nO(n)n' \in O(n), and it is always true that nnn' \leq n since LL' is a union of syntactic classes of LL, implying that the syntactic congruence of LL' is coarser than that of LL, so the number of states in the minimal DFA for LL' 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 LL' 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}:w0(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:w0(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=wLw^1 = w \notin L. Thus, n=nn' = n, showing that nn' 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+10v(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 fractionxx is rationalxx is algebraicxx 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.d1d2dm(dm+1dm+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 1im1 \le i \le m represents that the first ii digits match exactly the first ii digits of γ\gamma.
  - rjr_j for 1jp1 \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 1i<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 1jp1 \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 fractionxx is rationalxx is algebraicxx 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 nN n \in \mathbb{N} , the prefix sn=d1d2dn 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 k1 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=s1s2sm u = s_1 s_2 \dots s_m  and v=sm+1sm+2sn v = s_{m+1} s_{m+2} \dots s_n , so v=nm>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 uxLγ 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 uxLγ 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 uvxLγ 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 nNn\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,145L\varepsilon,12345,145\in L and 321,141,1335L321,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(log2n)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 iQi \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=0n1(ni)=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(log2n)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 nN>0n\in\mathbb{N}_{>0}, Σ:={a,b}\Sigma:=\{a,b\}, A,BΣnA,B\subseteq\Sigma^n. We write xA:={u:x=uvw,vA}|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Σ:wA=wB}L':=\{w\in\Sigma^*:|w|_A=|w|_B\} is regular. For this purpose, we define λ(wc):=wAwB\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, LL' 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 uAu\in A, vBv\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 uAu \in A, vBv \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 kNk \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 sks_{k'} with kkk \neq k', if they were equivalent under the right congruence of LL, then for all zz, skzLs_k z \in L iff skzLs_{k'} z \in L. However, skzLs_k z \in L iff λ(skz)=0\lambda(s_k z) = 0 iff kp+λ(uz)=0k p + \lambda(u z) = 0, and similarly for skzs_{k'} z. Thus, for all zz, kp+λ(uz)=0k p + \lambda(u z) = 0 iff kp+λ(uz)=0k' p + \lambda(u z) = 0. This implies that for all zz, if λ(uz)=kp\lambda(u z) = -k p then λ(uz)=kp\lambda(u z) = -k' p, which requires k=kk = 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 skzLs_k z \in L but skzLs_{k'} z \notin L for kkk \neq k'.

Therefore, the strings sks_k for kNk \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 uAu \in A, vBv \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 n1n-1 characters of ww. Formally, define states as pairs (s,d)(s, d) where sΣn1s \in \Sigma^{n-1} (with the initial state corresponding to the empty string handled separately) and dZd \in \mathbb{Z}. The transition function is such that reading a string zz from state ss results in a state ss' and an increment Δ(s,z)\Delta(s,z) so that if λ(w)=d\lambda(w) = d and the last n1n-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 n1n-1 characters of wzwz.

Suppose for contradiction that λ\lambda is unbounded. Then there exists a state sΣn1s \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 u0Au_0 \in A. Let s0s_0 be the last n1n-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 rr' such that:
- From state ss, reading rr' 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=rzNrx = 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 rr', 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 u0Au_0 \in A and reading u0u_0 from state s0s_0 returns to state s0s_0 (because the last n1n-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 uAu \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,...,MkZ3×3M_1,...,M_k\in\mathbb{Z}^{3\times 3}, vector vZ3v\in\mathbb{Z}^3
Output: Do there exist A1,...,Al{M1,...,Mk}A_1,...,A_l\in\{M_1,...,M_k\} such that A1A2Alv=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:=(0vv)M:=\begin{pmatrix}0 & v & -v\end{pmatrix}, with vZ3v\in\mathbb{Z}^3, and M1,...,MkZ3×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 MA1A2Alv=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 MA1Alv=0M A_1 \cdots A_l v = 0.

Let M=(0vv)M = \begin{pmatrix} 0 & v & -v \end{pmatrix}, so for any vector wZ3w \in \mathbb{Z}^3, Mw=(w2w3)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 B1B2Blv=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 v0v \neq 0. Since M1,,MkM_1, \ldots, M_k are invertible and MM is singular, the product B1BlB_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=u2u3c = 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 c0c \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 MA1Alv=0M A_1 \cdots A_l v = 0, then the sequence M,A1,,AlM, A_1, \ldots, A_l applied to vv gives MA1Alv=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)TZ3v = (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 BiZ3×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=(011011011)M = \begin{pmatrix} 0 & 1 & -1 \\ 0 & 1 & -1 \\ 0 & 1 & -1 \end{pmatrix}, which is equivalent to [0vv][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.