hw06.tex

\documentclass[11pt,letterpaper]{article}
\usepackage{preamble}

\title{Homework Assignment 06 \\
    \small Due: October 11, 2019}

\begin{document}
\maketitle

\section{neat(computer) $>$ neat(human)}
On expanding based on the first rule, we get $S = bA$. The $A$ can then be expanded in three different ways,
\begin{itemize}
    \item when $A = a$, $S = ba$ which contains an equal number of $a$'s and $b$'s.
    \item when $A = aS$, $S = baS$ which contains an equal number of $a$'s and $b$'s and then contains another string $S$.
    \item when $A = bAA$, $S = bbAA$ which contains two $b$'s and at least two $a$'s (as per the above two cases).
\end{itemize}
Therefore, the first column of rules yield a language consisting of all strings with an equal number of $a$'s and $b$'s. The second column is simply the first column with $a$ and $b$ swapped and to show that it too yields the same language is trivial. \\
Hence, the given grammar generates a language consisting of all strings with an equal number of $a$'s and $b$'s.
\pagebreak

\section{$\{(a^*b)^i c^i$ $|$ $i>0\}$}
\begin{table}[!h]
    \centering
    \begin{tabular}{c c c}
    $S \rightarrow (Ab)Ic$ & 
    $I \rightarrow \epsilon$ &
    $A \rightarrow \epsilon$ \\
    
    &
    $I \rightarrow (Ab)Ic$ &
    $A \rightarrow aA$
    \end{tabular}
    \label{tab:2}
\end{table}

\section{$\{a^i b^j c^k$ $|$ $i+k=j\}$}
\begin{table}[!h]
\centering
\begin{tabular}{c c c}
$S \rightarrow \epsilon$ & 
&
\\

$S \rightarrow aAbC$ &
$A \rightarrow \epsilon$ & 
$C \rightarrow \epsilon$ \\

$S \rightarrow AbCc$ &
$A \rightarrow aAb$ &
$C \rightarrow bCc$
\end{tabular}
\label{tab:03}
\end{table}

\section{$\{a^i b^j c^k d^l$ $|$ $i=k \vee j=l\}$}
Let us consider three cases, when $j=l=0$, when $i=k=0$, and when none of them are $i,j,k,l \neq 0$. The final grammar is simply a union of these cases.
\begin{table}[!h]
\label{tab:04a}
\centering
In addition, when $i=j=k=l=0$, $S \rightarrow \epsilon$ \\
\begin{tabular}{c c c}
&&\\
$j=l=0$ &
$i,j,k,l \neq 0$ &
$i=k=0$ \\
&&\\
$S \rightarrow aAc$ &
$S \rightarrow aBCd$ &
$S \rightarrow bDd$ \\

$A \rightarrow \epsilon$ &
$B \rightarrow b$ &
$D \rightarrow \epsilon$ \\

$A \rightarrow aAc$ &
$B \rightarrow aBc$ &
$D \rightarrow bDd$ \\

& $C \rightarrow c$ &\\
& $C \rightarrow bCd$ &\\

\end{tabular} 
\end{table}

\section{complement of $\{a^i b^j c^k$ $|$ $i \leq j \leq k\}$}
\begin{center}
$\{a^i b^j c^k$ $|$ $i \leq j \leq k\}^{'} = \{a^i b^j c^k$ $|$ $i > j > k\}$ \\
\end{center}
The above set does not contain the empty string. The smallest possible strings are $aab$ and $aaabbc$ for two cases, when $k=0$ and $k \neq 0$.
\begin{table}[!h]
    \centering
    \begin{tabular}{c c}
    $S \rightarrow S_1$ & 
    $S \rightarrow S_2$ \\
    
    $S_1 \rightarrow aaAb$ &
    $S_2 \rightarrow aaaBC$ \\
    
    $A \rightarrow \epsilon$ &
    $B \rightarrow bb$ \\
    
    $A \rightarrow aA$ &
    $B \rightarrow abBC$ \\
    
    $A \rightarrow aAb$ &
    $C \rightarrow \epsilon$ \\
    
    &
    $C \rightarrow c$
    \end{tabular}
    \label{tab:5}
\end{table}

\end{document}