Consider the following context-free grammar \(G\) which generates some context-free language \(L(G)\):
\[ \begin{array}{l} S \rightarrow 0S1\ |\ A\\ A \rightarrow 1A\ |\ 1 \end{array} \]
What are the variables of this grammar?
What are the terminals of this grammar?
What is the start variable?
Give two strings of length 4 or greater that are in \(L(G)\), along with their derivations.
Draw parse trees for your two derivations in the preceding part.
Give two strings of length 4 or greater that are not in \(L(G)\).
Give a succinct description of the language \(L(G)\) using set-builder notation.
For each of the following languages, give a context-free grammar (in all cases, the alphabet \(\Sigma=\{0,1\}\)).
\(\{w\,|\,w\in\Sigma^*\mbox{ with } |w|\bmod 3 = 0\}\) (in other words, the length of \(w\) is a multiple of 3)
\(\{w\,|\,w=0^n1^n\) for even \(n\geq 0 \}\)
\(\{w\,|\,w\in\Sigma^*\) where \(w\) contains exactly three \(\texttt{1}\)s\(\}\)
\(\{x\texttt{0}y\,|\,x,y\in\Sigma^n\) for \(n\geq 0 \}\) (in other words, strings of odd length for which the middle symbol is \(\texttt{0}\)).
Which of the languages above are regular? (You don’t need to justify your answer in any way – just list which ones are regular.)
Design a pushdown automata for each of the languages in question 2. Note that I am not asking you to perform the CFG-to-PDA conversion — design a PDA directly from the description of the language.
Convert the following grammar into Chomsky Normal Form (show and describe each step): \[ \begin{array}{l} S \rightarrow 0A0\ |\ 1B1\ |\ BB\\ A \rightarrow C\\ B \rightarrow S\ |\ A\\ C \rightarrow S\ |\ \varepsilon\\ \end{array} \]
Perform the CFG-to-PDA conversion procedure from the book (pages 117–120) to convert the following grammar into a PDA that recognizes the same language
\[ \begin{array}{l} A \rightarrow BAA\ |\ B\\ B\rightarrow 01\ |\ \varepsilon \end{array} \]
A sequence of transitions on a PDA can be written out by making a sequence of pairs \((q,s)\), where \(q\in Q\) is the current state and \(s\in\Gamma^*\) is the current stack, with the top of the stack on the left, and transitions written as arrows with the input symbol (or \(\varepsilon\)) on top of the arrow indicating the input used to make the transition. For example, processing input \(\texttt{0011}\) in PDA \(M_1\) give in Figure 2.15 (page 115) of the textbook could be written as: \[(q_1,\varepsilon) \xrightarrow{\varepsilon} (q_2,\texttt{\$}) \xrightarrow{\texttt{0}} (q_2,\texttt{0\$}) \xrightarrow{\texttt{0}} (q_2,\texttt{00\$}) \xrightarrow{\texttt{1}} (q_3,\texttt{0\$}) \xrightarrow{\texttt{1}} (q_3,\texttt{\$}) \xrightarrow{\varepsilon} (q_4,\varepsilon)\]
Write out an accepting sequence of transitions for input \(\texttt{011110}\) on PDA \(M_3\) given in Figure 2.19 (page 116).
Consider what the CFG would look like if \(M_3\) were converted to a CFG according to the PDA-to-CFG conversion algorithm described on pages 121–124 of the textbook. Note that \(M_3\) is almost in the form required for this conversion (properties 1–3 on page 121), so only a small initial translation is necessary: You need to add one new state to handle the transition from \(q_2\) to \(q_3\) that neither pushes nor pops, so call that new state \(q_9\). You do not need to write out the CFG, because it would require far too many variables, but you are encouraged to write out the most significant production rules created for the CFG (there are about a half dozen “important” ones that are created using “Rule 1” from the top of page 122).
Whether you write out the production rules or not, use the standard CFG variable names to write out the derivation that would occur for the transition sequence you found in part (a). To simplify your notation, you can write \(A_{13}\) instead of \(A_{q_1q_3}\) (for example), which is what you’d get by literal application of the rules.