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

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}

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

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