Se uma gramática g é esquerda e direita regular, por que $ || l (g) ||\ leq || p || $?
-
29-09-2020 - |
Pergunta
Eu estava estudando teoria de autômatos e línguas formais e nos deparamos com esta questão:
Se uma gramática $ g $ é esquerda e direita regular, por que $ || l (g) || \ leq || p || $ ?
Eu procurei a teoria, mas estou perdendo alguma coisa. E eu não consigo encontrar a resposta em qualquer lugar, então estou perguntando aqui.
Definições:
$ P $ = conjunto de regras
Regra regular de direito: gramática $ g= (n, p, p, p, s) $ , uma regra é na $ P $ Se a regra estiver no formulário: $ a \ rightarrow BA $ $ (A, B \ in n) \ cunha (a \ in t) $
regra externa: gramática $ g= (n, p, p, p, s) $ , uma regra está na $ P $ se a regra estiver no formulário: $ a \ rightarrow AB $ $ (A, B \ in n) \ cunha (a \ in t) $ .
gramática regular: uma gramática onde todas as regras são regras regulares.
Gramática regular à direita: uma gramática onde todas as regras são regras regulares corretas.
Exemplo de uma regra definida $ P $ com regras regulares à esquerda e à direita: $ p={\ righttarrow a, b \ righttarrow b \} $
e ser tanto para a esquerda e direita-regular torna a gramática regular e o tipo 3
Solução
Sua gramática contém apenas regras do formulário $ a \ para um $ , para $ a \ in n $ e $ a \ em t $ .Portanto $ l (g)={\ sigma \ in t: s \ to \ sigma \ in p \} $ .Você pega daqui.