2.27.2024
Question 1: Which of the following is the correct updated rule for replacing the nonterminal $S$ after the $A \rightarrow \epsilon$ rule is removed from the following CFG: $S \rightarrow AS \vert bA, A \rightarrow B \vert \epsilon, B \rightarrow b$?
(3 points)
A. $S \rightarrow AS \vert bA \vert A$
B. $S \rightarrow AS \vert b$
C. $S \rightarrow S \vert b$
D. $S \rightarrow AS \vert S \vert bA \vert b$
Answer
D. $S \rightarrow AS \vert S \vert bA \vert b$Question 2: Which of the following is the correct updated rule for replacing the nonterminal $S$ after the $B \rightarrow \epsilon$ rule is removed from the following CFG: $S \rightarrow ASB \vert BAB, B \rightarrow b \vert \epsilon, A \rightarrow Aa \vert \epsilon$?
(3 points)
A. $S \rightarrow ASB \vert BAB \vert AS \vert AB \vert BA \vert A$
B. $S \rightarrow ASB \vert BAB \vert AS \vert AB \vert BA$
C. $S \rightarrow ASB \vert BAB \vert AB \vert BA$
D. $S \rightarrow ASB \vert BAB \vert AS \vert S \vert AB \vert BA$
Answer
A. $S \rightarrow ASB \vert BAB \vert AS \vert AB \vert BA \vert A$Question 3: Which of the following is the correct conversion of the grammar rule $S \rightarrow SAA \vert ba$ to CNF?
(3 points)
A. $S \rightarrow A1A \vert BA, A1 \rightarrow AS, B \rightarrow b$
B. $S \rightarrow A1A \vert bA, A1 \rightarrow AS$
C. $S \rightarrow A1A \vert BA, A1 \rightarrow SA, B \rightarrow b$
D. $S \rightarrow A1 \vert AB, A1 \rightarrow SA, B \rightarrow b$