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} +