% ---------
%  Compile with "pdflatex hw0".
% --------
%!TEX TS-program = pdflatex
%!TEX encoding = UTF-8 Unicode

\documentclass[11pt]{article}
\usepackage{jeffe,handout,graphicx}
\usepackage[utf8]{inputenc}		% Allow some non-ASCII Unicode in source

\def\Sym#1{\textbf{\texttt{\color{BrickRed}#1}}}

%  Redefine suits
\usepackage{pifont}
\def\Spade{\text{\ding{171}}}
\def\Heart{\text{\textcolor{Red}{\ding{170}}}}
\def\Diamond{\text{\textcolor{Red}{\ding{169}}}}
\def\Club{\text{\ding{168}}}

% =========================================================
%   Define common stuff for solution headers
% =========================================================
\Class{CS 374}
\Semester{Spring 2015}
\Authors{2}
\AuthorOne{Akshat Gupta}{agupta60}
\AuthorTwo{Rohit Mukerji}{rmukerj2}
\AuthorThree


% =========================================================
\begin{document}

% ---------------------------------------------------------
\HomeworkHeader{1}{3}	% homework number, problem number

\def\LL{\textcolor{NavyBlue}{\,\llbracket\,}}
\def\RR{\textcolor{Red}{\,\rrbracket\,}}





\begin{solution} \leavevmode

\begin{flushleft}
a) $M$ = ($Q$, $\sum$, $\delta$, $q_o$, $F$) \\

\end{flushleft}

\begin{flushleft}
Q = $Q_1$ x $Q_2$ x $Q3$\\
$\sum$ = $\sum$\\
$\delta$(($q_1$, $q_2$, $q_3$), a) = ($\delta$($q_1$, a), $\delta$($q_2$, a), $\delta$($q_3$, a)) where ($q_1$, $q_2$, $q_3$) $\in$ $Q$\\
$F$ =  ($F_1$ x $F_2$ x $Q_3$) + ($F_1$ x $Q_2$ x $F_3$) + ($Q_1$ x $F_2$ x $F_3$)

\end{flushleft}

\begin{flushleft}
b)

\end{flushleft}

\begin{flushleft}
\underline{To Prove}: Let $X$ be a regular language accepted by $M$. We need to show that $X$ = L. \\
$\implies$ $X$ $\subseteq$ L and L $\subseteq$ X \\




\end{flushleft}

\begin{flushleft}

($q_1$, $q_2$, $q_3$) $\xrightarrow{w}$ ($a_1$, $a_2$, $a_3$)\\
\end{flushleft}

\begin{flushleft}
\underline{Inductive Hypothesis:} For all strings w such that |w| < n, \\($q_1$, $q_2$, $q_3$) $\xrightarrow{w}$ ($p_1$, $p_2$, $p_3$) in M iff $q_1$ $\xrightarrow{w}$ $p_1$ in $M_1$, $q_2$ $\xrightarrow{w}$ $p_2$ in $M_2$, and $q_3$ $\xrightarrow{w}$ $p_3$ in $M_3$.\\
\underline{Inductive Step:} Let s be an arbitary string such that |s| = n. We can write s as s = aw, where |w| < n.\\
Suppose, ($q_1$, $q_2$, $q_3$) $\xrightarrow{a}$ ($r_1$, $r_2$, $r_3$). Then by definition, $q_1$ $\xrightarrow{a}$ $r_1$, $q_2$ $\xrightarrow{a}$ $r_2$, and $q_3$ $\xrightarrow{a}$ $r_3$\\
Also by the Inductive Hypothesis, $r_1$ $\xrightarrow{w}$ $p_1$, $r_2$ $\xrightarrow{w}$ $p_2$, and $r_3$ $\xrightarrow{w}$ $p_3$.\\
Pasting the computations back together, as $q_1$ $\xrightarrow{a}$ $r_1$ and $r_1$ $\xrightarrow{w}$ $p_1$, $q_1$ $\xrightarrow{aw}$ $p_1$\\
As we know aw = s, $q_1$ $\xrightarrow{s}$ $p_1$\\
Without Loss of Generality, $q_2$ $\xrightarrow{s}$ $p_2$ and $q_3$ $\xrightarrow{s}$ $p_3$\\
$\implies$ ($q_1$, $q_2$, $q_3$) $\xrightarrow{s}$ ($p_1$, $p_2$, $p_3$)

\end{flushleft}



\end{solution}

\end{document}