Relação entre gramáticas simples e regulares

Estou lendo "Uma Introdução às Línguas Formais e Autômatos", escrito por Peter Linz e, depois de ler os cinco primeiros capítulos, enfrento o problema com gramáticas simples e regulares (especialmente lineares à direita), muito parecidas entre si.

Que relação existe entre estes? Qual é a diferença? Você pode criar autômatos finitos (não determinísticos) para gramáticas simples (obviamente sem usar uma pilha)?

Uma gramática simples (gramática s) é aquela em que toda produção é da forma $A \rightarrow aB_1B_2...B_n$ Onde $a$ é um terminal e tudo $B_i, i\geq0$ são não terminais e existe apenas uma produção com qualquer par $\langle A,a\rangle$.

Claramente, todo idioma s (produzido por uma gramática s) é inequívoco e facilmente analisado, pois cada símbolo terminal da esquerda para a direita e não terminal determina exclusivamente a produção a ser aplicada. Por exemplo, se a sequência for$abc$, então o par $\langle S,a\rangle$determina exclusivamente a primeira produção da análise e assim por diante para cada terminal e o não terminal à sua direita imediata. Assim, um idioma definido por uma gramática s pode ser analisado um símbolo de cada vez, sem lookahead, resultando em tempo de análise linear; de fato, tempo$|x|$.

As gramáticas S não são muito importantes por si só, uma vez que a maioria das línguas reais excede seu poder. Mas eles são um trampolim para outras gramáticas analisadas em tempo linear, como$LL(k)$ gramáticas em que há um limite $k$no lookahead necessário para determinar uma produção durante a análise. Com efeito, uma gramática s é um$LL(0)$ gramática.

A conexão com os autômatos é que um s-langauge pode ser analisado com um autômato de empilhamento com um único estado, que apenas olha o símbolo de entrada e o símbolo de pilha superior para determinar uma sequência de símbolos de pilha a serem empurrados. Mas desde a gramática s ...

$S \rightarrow aSB|\#\\ B\rightarrow a$

... gera não regular $\{a^i\#a^i:i \geq 0\}$Em geral, as linguagens s não podem ser reconhecidas por autômatos de estados finitos, determinísticos ou não determinísticos.