Step 1: add a new start state:
S0->S S->aAB A->aAa A->bb B->a
Step 2: remove epsilon rules (No such rules in this CFG)
Step 3: remove non-terminal to non-terminal rules
S0->aAB S->aAB A->aAa A->bb B->a
Step 4: make right-hand-side not contain more than 2 non terminals OR 1 terminal:
S0->BC S->BC A->BF | EE (A->aAa and A->bb in one line) B->a C->AB E->b F->AB So this is where i get confused… I’ve now got C and F that are both ->AB. If i’ve done correct that would mean that either C or F can simply be removed. Or of course i’ve done something wrong in this proof. Hopefully someone here on stackexchange can shed some light in the matter. /Byf
Asked By : Byfjunarn
Answered By : reinierpost
A → BC, or A → a, or S → ε, where S is the start symbol.
Consider the grammar
S → TU S → UT T → a U → a
Is this a valid context-free grammar in Chomsky Normal Form? Yes, it is. Each rule is of one of the allowed forms. But – you say – T and U have the exact same rules; one can be replaced with the other! Congratulations: you have invented a normal form! A grammar is in Byfjunarn Normal Form if and only if it has no two different nonterminals for which the rules have the exact same right hand sides. This is clearly a normal form: in fact, normalizing grammars into this form is so easy that we do it routinely, without even thinking about it. But the algorithm you’re using to bring arbitrary grammars into Chomsky Normal Form doesn’t. Why should it? Grammars can be in Chomsky Normal Form without being in Byfjunarn Normal Form; my example above proves it. Yes, it would be easy to modify the algorithm to bring grammars not only into Chomsky Normal Form, but also into Byfjunarn Normal Form. But nobody asked it to. Except you. Just let the poor algorithm go about its ways. You know what to do once it’s finished 🙂
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/63646 Ask a Question Download Related Notes/Documents
