%&latex
\documentclass[12pt]{article}
\usepackage{fullpage-old} \usepackage{fancyhdr}
\usepackage{amsmath}    \usepackage{amsfonts}   \usepackage{amssymb}
\usepackage{graphics}   \usepackage{epsfig}     \usepackage{wrapfig}
\usepackage{enumitem}

\lhead{} \cfoot[]{Page \thepage{}}%{ of 1}
\pagestyle{fancy} \renewcommand{\headrulewidth}{0pt}
\fancypagestyle{plain}{ \renewcommand{\headrulewidth}{0pt} }
\parskip 1ex
\parindent 0mm

\newcommand*{\ii}[1]{\textit{#1\/}}
\def\mi{\mathit}
\def\ttt{\texttt}
\def\ss{\hspace{1pt}}

% Logical operators
\def\andl{\wedge}
\def\orl{\vee}
\def\xorl{\oplus}
\def\notl{\neg}


\begin{document}

%{\flushright Name: \rule{15em}{0.25pt} \par}
\vspace{-2ex}
{\center \Large FLAC Assignment 7\par}
\vspace{2ex}

%\begin{wrapfigure}{r}{3.3in}
%\vspace{-3ex}
%\includegraphics[scale=1.2]{hw2-fig.pdf}
%\end{wrapfigure}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\paragraph{}
\paragraph{Exercise 1} Give  a  Turing machine with  at most 12  states that doubles a
number in unary representation. You will lose  points if you use extra states.
It should be clear your solution is correct; give explanation if necessary.
\paragraph{Exercise 2} 
(a)\ Convert the following CFG into Chomsky Normal Form.
Write down your steps.

\begin{multline*}
& S\to \texttt{a}A\texttt{a}\ |\ \texttt{b}B\texttt{b}\ |\ \epsilon\\
 A\to C\ |\ \texttt{a}\\
 B\to C\ |\ \texttt{b}\\
 C\to CDA\ |\ \epsilon\\
 D\to A\ |\ B\ |\ \texttt{ab} \\
\end{multline*}

(b) Use Younger's Algorithm to to decide whether ``ababa'' is in the language.
Write down the steps.
\paragraph{Exercise 3} We already know $\{\texttt{a}^n\texttt{b}^n\texttt{c}^n\ |\ n\geq 0\}$ is not
a context free language. Give a Turing machine that  decides this language.
It should be clear your solution is correct; give explanation if necessary.\newpage
\paragraph{Exercise 4} We know following grammar is ambiguous. Please 
give some string in the language and show such that it has two different parse
trees. 

 Here, $\texttt{<stmt>}$ is the start symbol and terminals are: \texttt{else,
basic\_stmt,
for\_clause, if, boolexpr, then, blk, compound.} 

\begin{multline*}
&\texttt{<stmt>}\ \to\  \texttt{<uncond\_stmt>} \ | \ \texttt{<cond\_stmt>} \\
\texttt{<uncond\_stmt>} \ \to\  \texttt{basic-stmt} \ | \ \texttt{<for\_stmt>} |\  \ \texttt{blk}\ |\ \texttt{compound} \\
\texttt{<for\_stmt>}\  \to \texttt{for\_clause} \ \texttt{<stmt>}\\
\texttt{<cond\_stmt>}\  \to \ \texttt{<if\_stmt>}\ |\texttt{<if\_stmt>}\  \texttt{else} \ \texttt{<stmt>}\\
\texttt{<if\_stmt>}\ \to\  \texttt{<if\_clause>}\ \texttt{<uncond\_stmt>}\\
\texttt{<if\_clause>}\to \texttt{if} \ \texttt{boolexpr}\ \texttt{then}\\
\end{multline*}

\paragraph{Exercise 5} In class we introduced a type of Turing Machine whose
tape is  two-way infinite, which means the machine can keep moving left
or right indefinitely. Also the action that the machine can take is one of $\{L,R,N\}$. 

In the book, the definition is slightly different. The tape of the Turing Machine is
 one-way infinite, which means there is a leftmost square of the tape
and the machine cannot move left when at that position. In addition, the action the machine can take is one of $\{L,R\}$. 

You task is to prove that a Turing Machine of the type defined in the textbook can simulate a Turing Machine of the type defined in class.
\paragraph{Exercise 6} (Bonus) Prove that any context-free language over alphabet
size 1, for example $\Sigma =\{1\}$, is also regular language.




\end{document}
