Open in App
Log In Start studying!

Select your language

Suggested languages for you:

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

Short Answer

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} \)
See the step by step solution

Step by step solution

Unlock all solutions

Get unlimited access to millions of textbook solutions with Vaia Premium

Over 22 million students worldwide already upgrade their learning with Vaia!

Step 1: 1. Introduce a new start symbol

: We will introduce a new start symbol, S, and add a new rule in the grammar with S as the non-terminal. S -> A Adding the new rule, the CFG becomes: \( \begin{aligned} &S \rightarrow A \\ &A \rightarrow B A B|B| \varepsilon \\ &B \rightarrow 00 \mid \varepsilon \end{aligned} \)

Step 2: 2. Remove epsilon (𝜀) production rules

: There are two epsilon-producing rules in our grammar: A -> 𝜀 B -> 𝜀 First, we will remove the rule A -> 𝜀 but retain the possibilities in the grammar where A can be replaced with 𝜀. Our new CFG looks like this: \( \begin{aligned} &S \rightarrow A \\ &A \rightarrow B A B \mid B \mid B B \mid \varepsilon\\ &B \rightarrow 00 \mid \varepsilon \end{aligned} \) Similarly, we will remove the rule B -> 𝜀: \( \begin{aligned} &S \rightarrow A \\ &A \rightarrow B A B \mid B \mid B B \mid \varepsilon\\ &B \rightarrow 00 \\ \end{aligned} \)

Step 3: 3. Remove unit production rules

: There is one unit-production rule in our grammar: S -> A We will replace this rule with all of the right-hand side possibilities of A: \( \begin{aligned} &S \rightarrow B A B \mid B \mid B B\mid \varepsilon\\ &A \rightarrow B A B \mid B \mid B B \mid \varepsilon\\ &B \rightarrow 00 \\ \end{aligned} \) Now, since we have removed every unit-production rule, we can remove the original non-terminal symbol A and its rules. Our new grammar becomes: \( \begin{aligned} &S \rightarrow B A B \mid B \mid B B\mid \varepsilon\\ &B \rightarrow 00 \\ \end{aligned} \)

Step 4: 4. Convert the remaining rules to Chomsky Normal Form format

: We're almost done. We just need to replace the nonterminal B and form Chomsky Normal Form rules. Let's create a new nonterminal D such that D -> 0: \( \begin{aligned} &S \rightarrow B A B \mid B \mid B B\mid \varepsilon\\ &B \rightarrow D D \\ &D \rightarrow 0 \\ \end{aligned} \) Our grammar is now in Chomsky Normal Form: \( \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 millions of textbook solutions in one place

  • 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
Get Vaia Premium now
Access millions of textbook solutions in one place

Most popular questions from this chapter

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\).)

Join over 22 million students in learning with our Vaia App

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
Join over 22 million students in learning with our Vaia App Join over 22 million students in learning with our Vaia App

Recommended explanations on Math Textbooks