0
$\begingroup$

I'm not sure if reusing variable is allowed in CNF.

For example, I have this grammar not in CNF. So I have to convert it to CNF. 1. S->abAB|abB|abA|ab 2. A->bAa|ba 3. B->BAa|bAa|ba|Ba|Aa|a
For conversion, I'm using a convention where new variables and terminals are in the form (V1,V2,V3,...,Vk) for k > 0 Ti where i are terminals (a,b,c,...,z) Introduce new terminals for each terminal in the grammar S->(Ta)(Tb)AB|(Ta)(Tb)B|(Ta)(Tb)A|(Ta)(Tb) A->(Tb)A(Ta)|(Tb)(Ta) B->BA(Ta)|(Tb)A(Ta)|(Tb)(Ta)|B(Ta)|A(Ta)|a Ta->a Tb->b
For the purpose of my question, I'm only focusing only on B productions due to the repetition of A(Ta). ... B->BV1|(Tb)V2|(Tb)(Ta)|B(Ta)|A(Ta)|a V1->A(Ta) V2->A(Ta) ...
See V1 and V2, they have the same right-hand side that is A(Ta).

$\endgroup$
0
$\begingroup$

"Chomsky normal form" is something a grammar is, rather than the specific procedure used to make it. So nothing prevents you from reusing a symbol like that; the grammar will still be CNF if you do.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.