Assignment Five

1. Question One

\begin{verbatim} N -> N a N b N -> ε a N b N (using N -> ε) -> ε a N a N b N b N (using N -> N a N b N) -> ε a N a N b N a N b N b N (using N -> N a N b N) -> ε a ε a N b N a N b N b N (using N -> ε) -> ε a ε a ε b N a N b N b N (using N -> ε) -> ε a ε a ε b ε a N b N b N (using N -> ε) -> ε a ε a ε b ε a ε b N b N (using N -> ε) -> ε a ε a ε b ε a ε b ε b N (using N -> ε) -> ε a ε a ε b ε a ε b ε b ε (using N -> ε) -> aababb (remove epsilons for clarity) \end{verbatim}

1.excalidraw.png

2. Question Two

\begin{verbatim} N -> N N -> N * N (using N -> N *) -> (N) * N (using N -> (N)) -> (N + N) * N (using N -> N + N) -> (a + N) * N (using N -> a) -> (a + a) * N (using N -> a) -> (a + a) * a (using N -> a) \end{verbatim}

3. Question Three

\begin{verbatim} N -> b N a N -> b ε a N (using N -> ε) -> b ε a a N b N (using N -> a N b N) -> b ε a a a N b N b N (using N -> a N b N) -> b ε a a a ε b N b N (using N -> ε) -> b ε a a a ε b ε b N (using N -> ε) -> b ε a a a ε b ε b ε (using N -> ε) \end{verbatim}

4. Question Four

\begin{verbatim} N -> aNbN N -> bNaN N -> ε \end{verbatim}

5. Question Five

\(count(a) \neq count(b) \Rightarrow count(a) > count(b) \vee count(a) < count(b)\)

More A's than B's = G
Less A's than B's = L

\begin{verbatim} S -> G S -> L G -> GG G -> EAE L -> LL L -> EBE E -> aEaE E -> bEaE E -> ε A -> aA A -> a B -> bB B -> b \end{verbatim}

6. Question Six

This one we can actually create from a DFA!

6.excalidraw.png

\begin{verbatim} S -> aN N -> aM N -> bS M -> MM M -> a \end{verbatim}

7. Question Seven

Consider a grammar S with regular expressions in its production's bodies. After replacing any extensions on regular expressions with their corresponding algebraic equivalents as given in 3.3.5, hen, we can transform S into an equivalent grammar by the following rules for nonterminals or terminals:

7.1. Kleene Closure

If we have a match in a production body corresponding to Kleene Closure, then we can transform it into two new productions:

\begin{verbatim} B* \end{verbatim}

goes to

\begin{verbatim} A -> ε A -> BA \end{verbatim}

7.2. Union

If we have a match in a production body corresponding to the union operator, then we can rewrite it as two new productions:

\begin{verbatim} B | C \end{verbatim}

goes to

\begin{verbatim} A -> B A -> C \end{verbatim}

7.3. Example(s)

For example, consider the grammar:

\begin{verbatim} N -> (A | B)* A -> aA A -> ε B -> bB B -> ε \end{verbatim}

then we can form our first transformation by replacing N (no need to rename since it's already the start symbol):

\begin{verbatim} N -> ε N -> (A | B)N A -> aA A -> ε B -> bB B -> ε \end{verbatim}

which is then further reduced when we transform (A | B)

\begin{verbatim} N -> ε N -> DN D -> A D -> B A -> aA A -> ε B -> bB B -> ε \end{verbatim}