%&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{}$ is the start symbol and terminals are: \texttt{else,
basic\_stmt,
for\_clause, if, boolexpr, then, blk, compound.}
\begin{multline*}
&\texttt{}\ \to\ \texttt{} \ | \ \texttt{} \\
\texttt{} \ \to\ \texttt{basic-stmt} \ | \ \texttt{} |\ \ \texttt{blk}\ |\ \texttt{compound} \\
\texttt{}\ \to \texttt{for\_clause} \ \texttt{}\\
\texttt{}\ \to \ \texttt{}\ |\texttt{}\ \texttt{else} \ \texttt{}\\
\texttt{}\ \to\ \texttt{}\ \texttt{}\\
\texttt{}\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}