Reusing variable in converting grammar to Chomsky Normal Form
-
05-11-2019 - |
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