\documentclass[12pt]{article}
\usepackage{amssymb}
\usepackage{tikz}
\usetikzlibrary{arrows,automata}
\begin{document}
\begin{center}
\large
MATH 4LT/6LT3 Assignment \#2
\\
Due: Friday, 8 October by 11:59pm.
\bigskip
\end{center}
\begin{enumerate}
\item Show that each of the following languages is not regular:
\begin{enumerate}
\item $L_0 = \{0^n1^n2^n\mid n \ge 0\}$.
\item $L_1 = \{www\mid w \in \{a,b\}^*\}$.
\item $L_2 = \{a^mb^n\mid m \ne n\}$.
\item $L_3 = \{x=y+z\mid \mbox{$|x| = |y| + |z|$ for $x$, $y$, $z \in \{1\}^*$}\}$. $L_3$ is a language over the alphabet $\{1, =, +\}$.
\item For $\Sigma$ an alphabet, $L_4$ is the set of all regular expressions over $\Sigma$.
\end{enumerate}
\item Let $\Sigma = \{a,b\}$ and let
$L$ consist of all strings $w \in \Sigma^*$ that contain an equal number of occurrences of the substring $ab$ as it does the substring $ba$. Show that $L$ is regular. So, $aba \in L$ since it contains one occurrence of $ab$ and one of $ba$, while $abab$ is not in $L$.
\item Let $\Sigma$ be an alphabet and $w \in \Sigma^*$. If $w = a_1a_2 \dots a_k$ for some $k \ge 0$ and $a_i \in \Sigma$, define the reverse of $w$ to be the string $w^r = a_ka_{k-1}\dots a_2a_1$. Show that if $L$ is a regular language, then so is $L^r = \{w^r\mid w \in L\}$.
\item Let $T = (\{q_0, q_1, q_2, q_{accept}, q_{reject}), \{a\}, \{a, \sqcup\}, \delta, q_0, q_{accept}, q_{reject})$ be the Turing Machine whose transition function is given by the following table:
\[
\begin{array}{c|c}
Q\times \Gamma& \delta\\\hline\hline
(q_0,\sqcup) & (q_{accept}, \sqcup, R)\\
(q_0, a) &(q_1,a,R)\\
(q_1,\sqcup) & (q_2,\sqcup, R)\\
(q_1,a) & (q_0,\sqcup,R)\\
(q_2,\sqcup) & (q_2, \sqcup, R)\\
(q_2, a) & (q_2, \sqcup, R)\\
\end{array}
\]
\begin{enumerate}
\item Show that $T$ accepts the string $aaaa$ by writing down the sequence of configurations that $T$ occupies, after being started in the initial configuration $q_0aaaa$.
\item Describe the sequence of configurations that $T$ occupies after being started in the configuration $q_0aaa$. Does $T$ accept $aaa$?
\item For $n \ge 0$, carefully describe what $T$ does when started in the configuration $q_0a^n$.
\item Describe the language accepted by $T$.
\end{enumerate}
\item Consider the language $L$ over the alphabet $\{0,1\}$ consisting of all words $w$ that contain an equal number of 0's and 1's.
\begin{enumerate}
\item Describe a Turing Machine that accepts $L$. Your description should describe how your TM operates on an input word $w$ without going into too much detail.
\item Draw a state diagram for the TM described in part a). To save time and effort you need not include any transitions that do not matter for the operation of your TM. You may use the JFLAP software for this part of the problem.
\end{enumerate}
\item A common definition of a Turing Machine allows for the machine to not move after reading a symbol, instead of always having to move one cell to the left or to the right. Consider a variant Turing Machine whose transition function may also produce a triple $\delta(q,s) = (q', a', S)$, where the $S$ indicates that the read/write head of the TM does not move.
Describe how a standard 1-tape Turing machine can be used to simulate the running of one of these variant (but still 1-tape) machines. More precisely, given a specification $T = (Q, \Sigma, \Gamma, \delta, q_s, q_{accept}, q_{reject})$ of a variant TM, give a definition of a standard TM $T'$ which essentially does the same things that $T$ does.
\end{enumerate}
The following questions are for students enrolled in MATH 6LT3. Students in MATH 4LT3 can treat them as bonus questions.
\begin{enumerate}
\item[B1] Let $L$ be a regular language over an alphabet $\Sigma$. Show that there is some TM that decides $L$.
\item[B2] For $L_1$ and $L_2$ languages over the alphabet $\Sigma$, define $L_1\wr L_2$ to be the language
\[
\{w \in \Sigma^*\mid \mbox{$w = a_1b_1a_2b_2\dots a_kb_k$ for some $k \ge 0$, $a_1a_2 \dots a_k \in L_1$}\]
\[ \mbox{ and $b_1b_2\dots b_k \in L_2$}\}.
\]
Prove that if $L_1$ and $L_2$ are regular then so is $L_1\wr L_2$.
\end{enumerate}
\end{document}