Pergunta

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).

Nenhuma solução correta

Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange
scroll top