\documentclass[12pt]{article}
\textheight 9.5in
\textwidth 6.6in
\parskip=\smallskipamount
\parindent=0.5in
\oddsidemargin -.1in
\evensidemargin -.1in
\topmargin -.4in
\headsep 0in
\topsep 0in

\usepackage{pgf,tikz}
\usepackage{mathrsfs}
\usetikzlibrary{arrows}
\usepackage{fancyhdr,txfonts,pxfonts}
%\usepackage{amsmath}
\usepackage{amstext}
\usepackage{amssymb}
\usepackage{hyperref}

\newcommand{\set}[1]{\{\,#1\,\}}
\newcommand{\into}{\longrightarrow}
\newcommand{\implies}{\Longrightarrow}
\newcommand     {\Choose} [2]   {(\,^{#1}_{#2}\,)}
\newcommand{\Nat}{{\rm \bf N}}


\begin{document}
\pagestyle{empty}
\thispagestyle{empty}
\sloppy

\noindent
{\large\bf
\begin{tabular*}{\textwidth}
{@{}l@{\extracolsep{\fill}}c@{\extracolsep{\fill}}r@{}}
CSE596 & Problem Set 2 Answer Key & Fall 2019
\end{tabular*}
}

\bigskip
(1)~Prove that two of the following three languages are non-regular, via
a Myhill-Nerode argument.  For the regular one, give a regular expression.
Here $\#a(x)$ denotes the number of occurrences of the character
$a$ in the string $x$, and more generally,
$\#w(x)$ denotes the number of occurrences of the substring $w$ in $x$.
For example, $\#0010(00100100) = 2$ even though the two occurrences
of the substring $0010$ overlap each other.
Also, for two strings $x,y$ of the same length, $x \oplus y$
denotes the bitwise exclusive-OR, e.g.\ $1011 \oplus 0010 = 1001$.
All three languages are over the alphabet $\Sigma = \{0,1\}$.

\begin{enumerate}
\item[(i)]
$L_1 = \{x: \#0(x) \leq \#1(x)\}$.
\item[(ii)]
$L_2 = \{x: \#01(x) = \#10(x)\}$.
\item[(iii)]
$L_3 = \{xy: |x| = |y| \wedge x \oplus y = 1^{|x|}\}$.
\end{enumerate}

($3 \times 12 = 36$ pts.)

\bigskip
\emph{Answers:} $L_2$ is regular; the others are not.  For $L_2$, the point is that 
for any binary string $x$, $\#01(x) = \#10(x)$ exactly when $x$ begins and ends with
the same character (or is the empty string).  If the first char is $0$, then every
changeover to $1$s involves one $01$ substring, and changing back to $0$s creates
exactly one balancing $10$ substring.  For beginning and ending with $1$ it is similar.
Paying due attention to edge cases, a regular expression is
\[
r_2 = 0(0+1)^* 0 + 1(0+1)^* 1 + 0 + 1 + \epsilon.
\]
For both $L_1$ and $L_3$, we can choose $S = 0^*$, which is clearly infinite.
Let any $x,y \in S$, $x \neq y$, be given.  Then we can write $x = 0^m$, $y = 0^n$, where
without loss of generality we may assert $m < n$.  Take $z = 1^m$.  Then
$xz \in L_1$ and $xz \in L_3$, the latter because $0^m \oplus 1^m = 1^m$.  But
$yz \notin L_1$ because $\#0(yz) = n > m = \#1(yz)$, and $yz \notin L_3$ for these reasons:
First,  if $n+m$ is odd then there is no way to break $yz$ into equal pieces.  For
$n+m$ being even, let us rewrite the definition of $L_3$ without a ``symbol clash'' as
$L_3 = \{uv: |u| = |v| \wedge u \oplus v = 1^{|u|}\}$.  Then the only way to break
$yz$ into equal-length pieces $u,v$ makes $u$ all-$0$s and includes at least one $0$ into $v$.
Those two $0$s have an XOR value of $0$, not $1$, so $u \oplus v \neq 1^{|u|}$.
Thus $S$ is an infinite PD set for $L_1$ and also for $L_3$, so both $L_1$ and $L_3$ are non-regular.

\bigskip
(2)~Now consider $L_4 = \{x: \#010(x) = 0 \wedge \#101(x) = 0\}$.
Use the Myhill-Nerode technique to show that any DFA $M$
such that $L(M) = L_4$ requires at least 6 states.  Then design
such a DFA $M$---ideally showing how your proof guided you to it
(or vice-versa).  Finally explain why you can basically ``collapse''
$M$ into a generalized NFA with only 2 states $s,f$ such that
\[
L(M) = L_{s,s} \cup L_{s,f} \cup L_{f,s} \cup L_{f,f},
\]
and use that to give a regular expression for $L_4$.
(12 + 6 + 9 = 27 pts.)

\bigskip
\emph{Answer:} The strings on the way to building $010$ and/or $101$ are
$\{\epsilon,0,1,01,10\}$, plus either $010$ or $101$ causes a ``dead condition.''
Let's choose $010$, so $S = \{\epsilon,0,1,01,10,010\}$.  Now $010$ is
separated from the other five strings by $\epsilon$, since $010 \notin L_4$ whereas
the other five strings all belong to $L_4$.  So we need only separate those
five strings from each other.  It was fine to do so by itemizing all
$\Choose{5}{2} = 10$ pairs, but here is a shortcut: For those pairs $x,y$ with
$|x| < |y|$, take $z$ such that $yz = 010$ or $yz = 101$; then $yz \notin L_4$
while $|xz| \leq 2$ so $xz$ belongs to $L_4$.  This leaves just the pair
$x = 0$, $y = 1$, which is separated by $z = 10$ (or by $z = 01$) and the pair
$x = 01$, $y = 10$, which is separated by $z = 0$ (or by $z = 1$).
Thus $S$ is a PD set of size $6$.

This means every DFA $M$ such that $L(M) = L_4$ must process the strings in $S$
to different states, including $010$ (and $101$) going to a dead state---with the
other states accepting.  This pretty much dictates the design shown at left in
the figure.  Now to find a regular expression, we can first delete the dead
state since it can never be used in an accepting computation.  Then the states
$q_{01}$ and $q_{10}$ have only one incoming and one outgoing arc, so they can
be elided to produce the second machine.  Then because the start state is
accepting, nothing is disturbed by deleting it but allowing either $q_0$ or
$q_1$ to be the start state.  This yields the hinted two-state GNFA $N$ with:
%
\begin{eqnarray*}
L(M) = L(N) &=& L_{0,0} \cup L_{0,1} \cup L_{1,0} \cup L_{1,1}\\
&=& (0 + 111^* 00)*(\epsilon + 111^*) + (1 + 000^* 11)^*(\epsilon + 000^*).
\end{eqnarray*}


\begin{center}
\begin{tikzpicture}[scale=0.2]
\tikzstyle{every node}+=[inner sep=0pt]
\draw [black] (5.1,-12.9) circle (3);
\draw (5.1,-12.9) node {$s$};
\draw [black] (5.1,-12.9) circle (2.4);
\draw [black] (14.1,-5.1) circle (3);
\draw (14.1,-5.1) node {$0$};
\draw [black] (14.1,-5.1) circle (2.4);
\draw [black] (14.1,-21.7) circle (3);
\draw (14.1,-21.7) node {$1$};
\draw [black] (14.1,-21.7) circle (2.4);
\draw [black] (29.3,-5.1) circle (3);
\draw (29.3,-5.1) node {$01$};
\draw [black] (29.3,-5.1) circle (2.4);
\draw [black] (29.3,-21.7) circle (3);
\draw (29.3,-21.7) node {$10$};
\draw [black] (29.3,-21.7) circle (2.4);
\draw [black] (37.2,-13.6) circle (3);
\draw (37.2,-13.6) node {$d$};
\draw [black] (47.7,-13.6) circle (3);
\draw (47.7,-13.6) node {$s$};
\draw [black] (47.7,-13.6) circle (2.4);
\draw [black] (57.5,-3.4) circle (3);
\draw (57.5,-3.4) node {$0$};
\draw [black] (57.5,-3.4) circle (2.4);
\draw [black] (57.5,-21.7) circle (3);
\draw (57.5,-21.7) node {$1$};
\draw [black] (57.5,-21.7) circle (2.4);
\draw [black] (71.7,-3.6) circle (3);
\draw (71.7,-3.6) node {$0$};
\draw [black] (71.7,-3.6) circle (2.4);
\draw [black] (71.7,-21.8) circle (3);
\draw (71.7,-21.8) node {$1$};
\draw [black] (71.7,-21.8) circle (2.4);
\draw [black] (5.1,-39.7) circle (3);
\draw (5.1,-39.7) node {$s$};
\draw [black] (20.9,-39.7) circle (3);
\draw (20.9,-39.7) node {$copy$};
\draw [black] (44.6,-39.7) circle (3);
\draw (44.6,-39.7) node {$lenchk$};
\draw [black] (66.7,-39.7) circle (3);
\draw (66.7,-39.7) node {$match$};
\draw [black] (66.7,-54.2) circle (3);
\draw (66.7,-54.2) node {$qacc$};
\draw [black] (66.7,-54.2) circle (2.4);
\draw [black] (44.6,-53.4) circle (3);
\draw (44.6,-53.4) node {$qrej$};
\draw [black] (3.9,-9) -- (4.22,-10.03);
\draw (1.87,-8.39) node [above] {$Start$};
\fill [black] (4.22,-10.03) -- (4.46,-9.12) -- (3.5,-9.42);
\draw [black] (7.37,-10.94) -- (11.83,-7.06);
\fill [black] (11.83,-7.06) -- (10.9,-7.21) -- (11.56,-7.97);
\draw (10.61,-9.49) node [below] {$0$};
\draw [black] (7.25,-15) -- (11.95,-19.6);
\fill [black] (11.95,-19.6) -- (11.73,-18.69) -- (11.03,-19.4);
\draw (8.58,-17.78) node [below] {$1$};
\draw [black] (17.1,-5.1) -- (26.3,-5.1);
\fill [black] (26.3,-5.1) -- (25.5,-4.6) -- (25.5,-5.6);
\draw (21.7,-5.6) node [below] {$1$};
\draw [black] (11.112,-5.121) arc (298.13633:10.13633:2.25);
\draw (7.32,-1.08) node [left] {$0$};
\fill [black] (12.27,-2.74) -- (12.33,-1.8) -- (11.45,-2.27);
\draw [black] (11.878,-23.698) arc (-20.29988:-308.29988:2.25);
\draw (6.83,-24.08) node [left] {$1$};
\fill [black] (11.16,-21.15) -- (10.59,-20.41) -- (10.24,-21.34);
\draw [black] (17.1,-21.7) -- (26.3,-21.7);
\fill [black] (26.3,-21.7) -- (25.5,-21.2) -- (25.5,-22.2);
\draw (21.7,-22.2) node [below] {$0$};
\draw [black] (31.39,-19.55) -- (35.11,-15.75);
\fill [black] (35.11,-15.75) -- (34.19,-15.97) -- (34.9,-16.67);
\draw (33.78,-19.12) node [right] {$1$};
\draw [black] (31.34,-7.3) -- (35.16,-11.4);
\fill [black] (35.16,-11.4) -- (34.98,-10.48) -- (34.25,-11.16);
\draw (32.72,-10.81) node [left] {$0$};
\draw [black] (37.653,-10.646) arc (199.00798:-88.99202:2.25);
\draw (42.82,-7.57) node [above] {$0,1$};
\fill [black] (39.82,-12.16) -- (40.74,-12.38) -- (40.41,-11.43);
\draw [black] (16.988,-5.899) arc (69.98466:14.97368:18.868);
\fill [black] (16.99,-5.9) -- (17.57,-6.64) -- (17.91,-5.7);
\draw (24.98,-9.42) node [right] {$0$};
\draw [black] (28.857,-8.064) arc (-13.28967:-71.66868:17.98);
\fill [black] (17.01,-21) -- (17.93,-21.22) -- (17.62,-20.27);
\draw (25.15,-17.53) node [right] {$1$};
\draw [black] (47.7,-7.9) -- (47.7,-10.6);
\draw (47.7,-7.4) node [above] {$Start$};
\fill [black] (47.7,-10.6) -- (48.2,-9.8) -- (47.2,-9.8);
\draw [black] (49.78,-11.44) -- (55.42,-5.56);
\fill [black] (55.42,-5.56) -- (54.51,-5.79) -- (55.23,-6.49);
\draw (53.13,-9.97) node [right] {$0$};
\draw [black] (54.82,-4.723) arc (-36:-324:2.25);
\draw (50.25,-3.4) node [left] {$0$};
\fill [black] (54.82,-2.08) -- (54.47,-1.2) -- (53.88,-2.01);
\draw [black] (54.82,-23.023) arc (-36:-324:2.25);
\draw (50.25,-21.7) node [left] {$1$};
\fill [black] (54.82,-20.38) -- (54.47,-19.5) -- (53.88,-20.31);
\draw [black] (50.01,-15.51) -- (55.19,-19.79);
\fill [black] (55.19,-19.79) -- (54.89,-18.89) -- (54.25,-19.66);
\draw (53.61,-17.16) node [above] {$1$};
\draw [black] (57.172,-18.718) arc (-174.9423:-185.0577:69.968);
\fill [black] (57.17,-18.72) -- (57.6,-17.88) -- (56.6,-17.97);
\draw (56.4,-12.55) node [left] {$11$};
\draw [black] (58.15,-6.328) arc (10.10176:-10.10176:35.475);
\fill [black] (58.15,-6.33) -- (57.8,-7.2) -- (58.78,-7.03);
\draw (59.2,-12.55) node [right] {$00$};
\draw [black] (74.674,-3.311) arc (123.2808:-164.7192:2.25);
\draw (78.77,-6.82) node [right] {$0$};
\fill [black] (73.74,-5.79) -- (73.76,-6.73) -- (74.6,-6.18);
\draw [black] (73.774,-19.648) arc (163.79379:-124.20621:2.25);
\draw (78.81,-18.74) node [right] {$1$};
\fill [black] (74.67,-22.14) -- (75.3,-22.84) -- (75.58,-21.88);
\draw [black] (66.8,-4.9) -- (68.8,-4.37);
\draw (66.04,-5.4) node [left] {$Start$};
\fill [black] (68.8,-4.37) -- (67.9,-4.09) -- (68.16,-5.06);
\draw [black] (67.2,-19.8) -- (68.96,-20.58);
\draw (66.47,-18.81) node [left] {$Start$};
\fill [black] (68.96,-20.58) -- (68.43,-19.8) -- (68.02,-20.71);
\draw [black] (72.866,-6.361) arc (18.57222:-18.57222:19.902);
\fill [black] (72.87,-19.04) -- (73.59,-18.44) -- (72.65,-18.12);
\draw (74.4,-12.7) node [right] {$11$};
\draw [black] (70.941,-18.899) arc (-168.18382:-191.81618:30.272);
\fill [black] (70.94,-6.5) -- (70.29,-7.18) -- (71.27,-7.39);
\draw (69.8,-12.7) node [left] {$00$};
\draw [black] (8.1,-39.7) -- (17.9,-39.7);
\fill [black] (17.9,-39.7) -- (17.1,-39.2) -- (17.1,-40.2);
\draw (13,-39.2) node [above] {$(cB/c\wedge,SR)$};
\draw [black] (21.375,-36.75) arc (198.58673:-89.41327:2.25);
\draw (29.84,-33.7) node [above] {$(cB/cc,RR)$};
\fill [black] (23.53,-38.28) -- (24.45,-38.5) -- (24.13,-37.55);
\draw [black] (23.9,-39.7) -- (41.6,-39.7);
\fill [black] (41.6,-39.7) -- (40.8,-39.2) -- (40.8,-40.2);
\draw (32.75,-39.2) node [above] {$(\#B/\#\$,RL)$};
\draw [black] (45.097,-36.753) arc (198.1609:-89.8391:2.25);
\draw (53.41,-33.73) node [above] {$(0c/0c,RL)$};
\fill [black] (47.24,-38.3) -- (48.16,-38.53) -- (47.85,-37.58);
\draw [black] (47.6,-39.7) -- (63.7,-39.7);
\fill [black] (63.7,-39.7) -- (62.9,-39.2) -- (62.9,-40.2);
\draw (55.65,-40.2) node [below] {$(\#\wedge/\#\wedge,RR)$};
\draw [black] (66.977,-36.725) arc (202.40793:-85.59207:2.25);
\draw (75.04,-33.45) node [above] {$(cc/cc,RR)$};
\fill [black] (69.23,-38.11) -- (70.16,-38.27) -- (69.78,-37.34);
\draw [black] (67.16,-42.664) arc (6.53384:-6.53384:37.668);
\fill [black] (67.16,-51.24) -- (67.75,-50.5) -- (66.75,-50.38);
\draw (67.9,-46.95) node [right] {$(B\$,B\$,SS)$};
\draw [black] (64.402,-41.629) arc (-51.05809:-65.35157:80.635);
\fill [black] (47.35,-52.2) -- (48.28,-52.32) -- (47.87,-51.41);
\draw (60.9,-47.95) node [below] {$(cd/cd,SS)$};
\draw [black] (45.21,-42.636) arc (8.49937:-8.49937:26.485);
\fill [black] (45.21,-50.46) -- (45.82,-49.75) -- (44.83,-49.6);
\draw (46,-46.55) node [right] {$(0\wedge/0\wedge,SS)$};
\draw [black] (43.012,-50.867) arc (-156.00605:-203.99395:10.616);
\fill [black] (43.01,-50.87) -- (43.14,-49.93) -- (42.23,-50.34);
\draw (41.59,-46.55) node [left] {$(\#c/\#c,SS)$};
\draw [black] (4,-35.3) -- (4.37,-36.79);
\draw (2.28,-34.63) node [above] {$Start$};
\fill [black] (4.37,-36.79) -- (4.66,-35.89) -- (3.69,-36.13);
\draw [black] (41.905,-54.683) arc (-74.74047:-285.25953:8.43);
\fill [black] (41.91,-54.68) -- (41,-54.41) -- (41.27,-55.38);
\draw (30.76,-46.55) node [left] {$(1c/1c,SS)$};
\end{tikzpicture}
\end{center}

\bigskip
(3)
Design a two-tape deterministic Turing machine $M_2$ that recognizes the
language
\[
L_3 = \{x\#0^k\#y: x,y \in \{0,1\}^*, x = y \wedge |x| = k\}.
\]
Here $\Sigma = \{0,1,\#\}$ but the $\#$ character is only allowed as a
marker to divide the input string $w$ into thirds.
Your $M_2$ should run in $O(n)$ time where $n = |w|$; note that any accepted
string gives $n = 3k + 2$ with $k$ as above.
(A well-commented arc-node drawing is fine; if you use the Turing Kit,
please take a screenshot since its own Postscript-based print feature
is old and may be wonky.)

\bigskip
\emph{Answer shown above.}  It needs some comments, first that `$c$' and `$d$'
are ``wildcards'' standing for $0$ or $1$.  In the ``match'' state, the interpretation
is that the more-specific arc $(cc/cc,RR)$ where the chars are equal takes precedence
over the most-general case $(cd/cd,SS)$, leaving ``$cd$'' in the latter to apply to
those cases where the characters are different.  Some arcs going to the reject state
are not shown---they are cases in which the input has fewer than two or more than two
`\#' characters.  When there are exactly two `\#' characters, the input has the form
$x\#u\#y$.  The ``copy'' state copies $x$ to the second tape as $\wedge x \$$ where the
endmarkers $\wedge$ and $\$$ make the next stages easier to code and interpret.
While moving the second tape head leftward---and \emph{not} writing blanks which is
where $M_2$ is not a PDA---it checks that $u$ has no $1$ and that $|u| = |x|$.
The condition $|u| < |x|$ is caught by the tape-1 head seeing the second $\#$ while the
tape-2 is still reading 0s and 1s that were copied; the condition $|u| > |x|$ is caught
by the tape-2 head reaching the left-endmarker $\wedge$ (which was placed down in the 
initial step) while the input head is still reading $0$s.  When $u = 0^{|x|}$ is 
verified, the heads are in perfect position to check $y = x$, which is then the condition
for $M_2$ to accept.  Not only does $M_2$ run in linear time, it moves its input head
right in each step except the single initial and final steps, which means it runs 
\emph{in real time}.

\bigskip
Then argue as best you can that every single-tape TM $M_1$ such that
$L(M_1) = L_3$ requires $\Omega(n^2)$ time.  Since $n$ is linear in $k$,
it may help to think of this as $\Omega(k^2)$ time.  Start by showing
that $S = \{0,1\}^k$ is PD fopr $L_3$.  Then argue that this means
$k$ bots of information must somehow cross the middle $0^k$ part in order
to decide $y = x$ correctly.  Finally reckon how much total time $M_1$ must
spend in that middle region, noting that $M$ has a fixed number $r = |Q|$
of states but $k$ can grow.  (You may consult last year's key
\href{https://cse.buffalo.edu/~regan/cse596/F18/CSE596ps3key.pdf}{https://cse.buffalo.edu/~regan/cse596/F18/CSE596ps3key.pdf} for a related problem
where the one-tape time is $\Omega(n\log n)$, but your answer does not
have to use the Australian imagery.  18 + 18 = 36 pts.)

\bigskip
\emph{Answer:} For any $k$, let any distinct $x_1,x_2 \in \{0,1\}^k$ be given.
Take $z = \#0^k\#x_1$.  Then $x_1 z \in L_3$ since its ``$y$ part'' equals $x_1$
and its middle has the right length $k$, but $x_2 z \notin L_3$.  In particular,
it is not in the ``slice'' of $L_3$ that deals with this value of $k$.
So $S$ is PD for $L_3$.  The intuititve meaning of this is that the ``$x$ part''
requires $2^k$ distinctions to be made at the other end of the tape, which is
captured by saying that (at least) $k$ bits of information need to be transported
from left to right.  

It was acceptable to say that anytime the single-tape TM $M_1 = (Q,\Sigma,\Gamma,\dots)$
crosses the second $\#$ sign left-to-right, it carries in only the information in its
current state.  So it can carry at most $q = \log_2(|Q|)$ bits at a time.  Thus the
computation needs $k/q$ trips from the ``$x$'' part to the ``$y$'' part.  Since there are
$k$ cells in-between, this takes order-of $k\cdot k/q = \Omega(k^2)$ steps overall.
This is hence a lower bound on the running time.  

If this last part seems hand-wavy to you, then you may appreciate how \emph{Kolmogorov complexity}
rigorizes the argument.  This will be done as a separate post after the first exam.
Briefly put, if $M$ could work in time $t = o(k^2)$ then the average time it spends
among the $k$ cells in the middle part is $t/k = o(k)$.  Some cell $j$ is at most average.
Every string $y \in \{0,1\}^k$ could then be specified by giving just the sequence of
states $M$ is in on its at most $t/k$ crossings---since the ``$x\#0^k\#$'' part would
have to automatically match it for $M$ to accept.  Then every string $y \in \{0,1\}^k$
would be specifiable in $< k$ bits, which is impossible.

\bigskip
(4)~Show that the concatenation of any two decidable languages is
decidable, and that the concatenation of any two c.e.\ languages is
c.e.  Argue further that if $A$ is c.e., then so it $A^*$.  (There is an
analogous fact when $A$ is decidable, but we will revisit it when 
doing complexity theory.  9+6+6 = 21 pts., for 120 pts.\ on the set)

\bigskip
\emph{Answer:} Call the three parts of this question (a,b,c).  For (a),
we may take TMs $M_A$ and $M_B$ accepting the given decidable languages $A$ and $B$
that are \emph{total}, i.e., halt for all inputs.  To make a total machine
deciding whether a given string $w$ belongs to $A \cdot B$, run this for-loop:

\begin{verbatim}
   for i = 0 to n {  //where n = |w|
      x := w[1 .. i]
      y := w[i+1 .. n]
      if (M_A accepts x && M_B accepts y) {
         accept w;
      }
   } //control here means that no breakdown i works
   reject w;
\end{verbatim}

The issue for (b) is that when $A$ and $B$ are only given as c.e.\ languages, 
we may not suppose that $M_A$ and $M_B$ are total.  If one fails to halt
on some iteration $i$, the loop will never reach iteration $i+1$ which might
be an accepting case.  The solution is to maintain $2(n+1)$ computations of
$M_A$ and $M_B$ on the possible breakdowns in parallel rather than in serial like above:

\begin{verbatim}
for t = 1 to infinity:
   for i = 0 to n {  //where n = |w|
      xi := w[1 .. i]
      yi := w[i+1 .. n]
      Do one more step of the computations M_A(xi) and M_B(yi)
      if (both have accepted within t steps) {
         accept w;
      }
   } //control here means try another step
} //control never goes beyond here---this routine might not halt either
\end{verbatim}

This is correct because whenever there is a working breakdown $w = x_i \cdot y_i$, there is
a time $t$ by which $M_A$ will have accepted $x_i$ and $M_B$ will have accepted $y_i$, and
then that iteration of the loop will see the acceptances and accept $w$.

For (c), the code instead maintains a database of $M_A$ working on all possible substrings
of $w$.  It is like filling out a ``bingo'' card, where ``bingo!'' means the loop over $t$
has found acceptances of a bunch of substrings that catenate together to form $w$.
Again the logic is that any acceptance (shouting ``bingo!'') is \emph{sound}, meaning that
the accepted string $w$ really belongs to $A^*$.  And whenever $w \in A^*$, there is a 
breakdown into finitely many substrings (all nonempty, or if $w = \epsilon$ then we automatically
accept) that all get accepted by $M_A$, in some maximum time $t$, and iteration number $t$
finds them all and accepts.  In logic, the analogous condition is ``every true statement
is proved'' and is called \emph{completeness}, but because ``completeness'' has a more
important meaning with reductions and the context is more general, I prefer to call it
\emph{comprehensiveness}.



\end{document}
