Suggested languages for you:

Americas

Europe

Problem 14

Convert the following CFG into an equivalent CFG in Chomsky normal form, using the procedure given in Theorem \(2.9 .\) $$ \begin{aligned} &A \rightarrow B A B|B| \varepsilon \\ &B \rightarrow 00 \mid \varepsilon \end{aligned} $$

Expert verified

The final Chomsky Normal Form of the given CFG is:
\(
\begin{aligned}
&S \rightarrow B A B \mid B \mid B B\mid \varepsilon\\
&B \rightarrow D D \\
&D \rightarrow 0 \\
\end{aligned}
\)

What do you think about this solution?

We value your feedback to improve our textbook solutions.

- Access over 3 million high quality textbook solutions
- Access our popular flashcard, quiz, mock-exam and notes features
- Access our smart AI features to upgrade your learning

Chapter 2

Let \(G=(V, \Sigma, R,\langle\mathrm{STMT}\rangle)\) be the following grammar. $$ \begin{aligned} \langle\mathrm{STMT}\rangle & \rightarrow\langle\mathrm{ASSIGN}\rangle|\langle\mathrm{IF}-\mathrm{THEN}\rangle|\langle\mathrm{IF}-\mathrm{THEN}-\mathrm{ELSE}\rangle \\\ \langle\mathrm{IF}-\mathrm{THEN}\rangle & \rightarrow \text { if condition then }\langle\mathrm{STMT}\rangle \\ \langle\mathrm{IF}-\mathrm{THEN}-\mathrm{ELSE}\rangle & \rightarrow \text { if condition then }\langle\mathrm{STMT}\rangle \text { else }\langle\mathrm{STMT}\rangle \\ \langle\mathrm{ASSIGN}\rangle & \rightarrow \mathrm{a}:=1 \\ \Sigma=&\\{\text { if, condition, then, else, a:=1 }\\} \\ V=&\\{\langle\mathrm{STMT}\rangle,\langle\mathrm{IF}-\mathrm{THEN}\rangle,\langle\mathrm{IF}-\mathrm{THEN}-\mathrm{ELSE}\rangle,\langle\mathrm{ASSIGN}\rangle\\} \end{aligned} $$ \(G\) is a natural-looking grammar for a fragment of a programming language, but \(G\) is ambiguous. a. Show that \(G\) is ambiguous. b. Give a new unambiguous grammar for the same language.

Chapter 2

Show that the class of context-free languages is closed under the regular operations, union, concatenation, and star.

Chapter 2

Use the results of Exercise \(2.16\) to give another proof that every regular language is context free, by showing how to convert a regular expression directly to an equivalent context-free grammar.

Chapter 2

Let \(G\) be the following grammar: $$ \begin{aligned} &S \rightarrow T \dashv \\ &T \rightarrow T \mathrm{a} T \mathrm{~b}|T \mathrm{~b} T \mathrm{a}| \varepsilon \end{aligned} $$ a. Show that \(L(G)=\\{w-1 \mid w\) contains equal numbers of a's and b's $\\} .\( Use a proof by induction on the length of \)w$. b. Use the \(D K\)-test to show that \(G\) is a DCFG. c. Describe a DPDA that recognizes \(L(G)\).

Chapter 2

Let \(C=\left\\{w w^{\mathcal{R}} \mid w \in\\{0,1\\}^{*}\right\\} .\) Prove that \(C\) is not a DCFL. (Hint: Suppose that when some DPDA \(P\) is started in state \(q\) with symbol \(x\) on the top of its stack, \(P\) never pops its stack below \(x\), no matter what input string \(P\) reads from that point on. In that case, the contents of \(P\) 's stack at that point cannot affect its subsequent behavior, so \(P\) 's subsequent behavior can depend only on \(q\) and \(x\).)

The first learning app that truly has everything you need to ace your exams in one place.

- Flashcards & Quizzes
- AI Study Assistant
- Smart Note-Taking
- Mock-Exams
- Study Planner