Beziehung zwischen einfachen und regulären Grammatiken

Ich lese "Eine Einführung in formale Sprachen und Automaten" von Peter Linz und nach dem Lesen der ersten fünf Kapitel habe ich das folgende Problem mit einfachen und regelmäßigen (insbesondere rechtslinearen) Grammatiken, die einander sehr ähnlich sind.

Welche Beziehung besteht zwischen diesen? Was ist der Unterschied? Können Sie (nicht deterministische) endliche Automaten für einfache Grammatiken erstellen (offensichtlich ohne Verwendung eines Stapels)?

Eine einfache Grammatik (S-Grammatik) ist eine, bei der jede Produktion die Form hat $A \rightarrow aB_1B_2...B_n$ wo $a$ ist ein Terminal und alles $B_i, i\geq0$ sind keine Terminals und es gibt nur eine Produktion mit einem Paar $\langle A,a\rangle$.

Es ist klar, dass jede S-Sprache (erzeugt durch eine S-Grammatik) eindeutig und leicht zu analysieren ist, da jedes Terminalsymbol von links nach rechts und nicht-terminal die anzuwendende Produktion eindeutig bestimmt. Zum Beispiel, wenn die Zeichenfolge ist$abc$dann das Paar $\langle S,a\rangle$Bestimmt eindeutig die erste Produktion des Parsings usw. für jedes Terminal und das Nicht-Terminal rechts davon. Somit kann eine durch eine S-Grammatik definierte Sprache symbolweise ohne Lookahead analysiert werden, was eine lineare Analysezeit, tatsächlich Zeit, ergibt$|x|$.

S-Grammatiken sind an sich nicht besonders wichtig, da die meisten realen Sprachen ihre Fähigkeiten überschreiten. Aber sie sind ein Sprungbrett zu anderen Grammatiken, die in linearer Zeit analysiert werden, wie z$LL(k)$ Grammatiken, in denen es eine Grenze gibt $k$auf dem Lookahead benötigt, um eine Produktion während des Parsens zu bestimmen. In der Tat ist eine S-Grammatik eine$LL(0)$ Grammatik.

Die Verbindung zu Automaten besteht darin, dass eine S-Sprache mit einem Pushdown-Automaten mit einem einzelnen Status analysiert werden kann, der nur das Eingabesymbol und das oberste Stapelsymbol betrachtet, um eine Folge von zu drückenden Stapelsymbolen zu bestimmen. Aber seit der S-Grammatik ...

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

... erzeugt nicht reguläre $\{a^i\#a^i:i \geq 0\}$, S-Sprachen können im Allgemeinen nicht durch deterministische oder nicht deterministische Automaten mit endlichen Zuständen erkannt werden.