% Created 2023-02-21 Tue 21:49
% Intended LaTeX compiler: lualatex
\documentclass[11pt]{article}
\usepackage{graphicx}
\usepackage{longtable}
\usepackage{wrapfig}
\usepackage{rotating}
\usepackage[normalem]{ulem}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{capt-of}
\usepackage{hyperref}
\notindent \notga \usepackage{ dsfont } \usepackage[utf8]{inputenc}  \usepackage{amsmath} \usepackage{fontspec} \usepackage[a4paper,margin=1in,portrait]{geometry} \usepackage{fontspec} \setmonofont{DejaVu Sans Mono}
\author{Lizzy Hunt}
\date{\today}
\title{Assignment Six}
\hypersetup{
 pdfauthor={Lizzy Hunt},
 pdftitle={Assignment Six},
 pdfkeywords={},
 pdfsubject={},
 pdfcreator={Emacs 28.2 (Org mode 9.6.1)}, 
 pdflang={English}}
\begin{document}

\maketitle
\setlength\parindent{0pt}

\section{Question One}
\label{sec:orgd2b70de}
\begin{verbatim}
A  -> BcDA'
A' -> eD | ε
B  -> xBB'
B' -> yD | zD | ε
D  -> Z
\end{verbatim}

\section{Question Two}
\label{sec:org3d41f44}
\begin{verbatim}
A  -> wA'
A' -> xA' | yA' | ε
\end{verbatim}

\section{Question Three}
\label{sec:org454e290}
\begin{verbatim}
A  -> wA' | yzA'
A' -> xA' | ε
\end{verbatim}

\section{Question Four}
\label{sec:orgafb492b}
\begin{verbatim}
A  -> Bx
B  -> Cy | Dz
C  -> Awp | z
D  -> t

For i = 1, there is no immediate left recursion

When i = 2 there is also no immediate left recursion

When i = 3 we substituted A in C:

A  -> Bx
B  -> Cy | Dz
C  -> Bxwp | z
D  -> t

Then B:
A  -> Bx
B  -> Cy | Dz
C  -> Cyxwp | Dzxwp | z
D  -> t

And remove the immediate left recursion in C:
A  -> Bx
B  -> Cy | Dz
C  -> Dzxwp | zC'
C' -> yxwpC' | ε
D  -> t

When i = 4, there's no left recursion

\end{verbatim}

\section{Question Five}
\label{sec:orged171dd}
\begin{verbatim}
A  -> Bx | Cy
B  -> Cz
C  -> Bw | v

When i = 1, no immediate left recursion

When i = 2, no immediate left recursion

When i = 3, we substitute B in C

A  -> Bx | Cy
B  -> Cz
C  -> Czw | v

, which we remove the immediate left recursion from

A  -> Bx | Cy
B  -> Cz
C  -> vC'
C' -> zwC' | ε
\end{verbatim}

\section{Question Six}
\label{sec:org0f2cc1b}
\begin{verbatim}
first(A)  = first(B) \ ε U first(x) U first(y) = {t, w, u, x, y}
first(B)  = first(C) U first(u) U {ε} = {t, w, u, ε}
first(C)  = first(t) U first(w) = {t, w}

follow(A) = {$} U follow(B) = {$, x}
follow(B) = {x}
follow(C) = follow(A) U {z} = {$, x, z}
\end{verbatim}

\section{Question Seven}
\label{sec:orgd013fa5}
\begin{verbatim}
first(A)  = first(C) = first(E) = {x, z}
first(B)  = first(a) U {ε} = {a, ε}
first(C)  = first(E) = {x, z}
first(D)  = first(b) U {ε} = {b, ε}
first(E)  = first(x) U first(z) = {x, z}

follow(A) = {$} U first(y) = {$, y}
follow(B) = follow(A) = {$, y}
follow(C) = first(B) \ ε U follow(B)= {a, $, y}
follow(D) = follow(C) = {a, $, y}
follow(E) = first(D) \ ε U follow(D) = {b, a, $, y}
\end{verbatim}
\end{document}