 Suggested languages for you:

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 