My Professor says I got this problem wrong but I do not see how so. Note that for the problem we do not need to make sure the final answer is in CNF, we are only told to fix one of the violations we see. Also, we are told to only deal with one violation.
Original Problem:
Consider the CFG G: $(V=\{S,A,B,X,y\}, \sum=\{a,b\}, R,S)$ where R is defined as below:
$$S\to XA|YB$$ $$A\to XS|YA$$ $$B\to YB|b$$ $$X\to a|\epsilon$$ $$Y\to b$$
- Give the grammar rule that violates the Chomsky Normal Form
- Rewrite the rules after fixing for the violation you identified in the previous question.
My Answer:
$$S\to XA|YB$$
$$A\to XS|YA$$
$$B\to YB|b$$
$$X\to a|\epsilon$$
$$Y\to b$$
(i) Violation: $A$ cannot go to start variable
(ii)
$$S\to XA|YB$$
$$A\to XXA|XYB|YA$$
$$B\to YB|b$$
$$X\to a|\epsilon$$
$$Y\to b$$
link to CNF rules: CNFrules