Se uma gramática g é esquerda e direita regular, por que $ || l (g) ||\ leq || p || $?

Question

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

Answer 1

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.