Die Definition regulärer Sprachen

Question

Ich habe versucht, und mein Gehirn verbrannt, um die Definition von Regular Languages ​​in Discrete Mathematics and its Applications(Rosen) zu verstehen, ohne das Ziel zu erreichen zu verstehen, warum die Definition so ist, dass in diesem Buch. Auf Seite (789), ich bin die Definition Umformulierung:

Typ 3 Grammatiken definiert werden als:

w1 --> w2 

Wo w1 ein Nicht-Terminal ist, und w2 ist von der Form:

w2 = aB 
w2 = a 

wobei B ein nicht-Terminal ist, und a ist ein Terminal. Ein Sonderfall ist, wenn w1 das Startsymbol und w2 ist Lambda (leerer String):

w1 = S 
S --> lambda 

Zwei Fragen, die ich konnte keine Antwort finden. Erstens, warum kann nicht w2 von der Form sein Ba. Zweitens, warum Lambda ist nur für das Startsymbol nur zulässig. Das Buch besagt, dass reguläre Sprachen dem Finite-State-Automaten entsprechen, und wir können leicht erkennen, dass wir FSA für beide Fälle erstellen können. Ich habe mir andere Ressourcen angeschaut, und diese Einschränkungen existieren in diesen Ressourcen nicht.

Answer 1

Erstens, warum kann nicht w2 von der Form Ba sein.

Nehmen Sie die folgende Grammatik mit W als Ausgangssymbol:

W -> lambda 
W -> aX 
X -> Wb 

es erzeugt {a n b n: n natürliche}, welche keine reguläre Sprache ist. Diese Einschränkung ist also notwendig, wenn Sie nur reguläre Sprachen generieren möchten. Alternativ können Sie w2 = Ba erlauben, aber verbieten Regeln der Art w2 = aB - das gibt auch normale Sprachen. Diese Grammatik wird ein Wort "rückwärts" aufbauen. Wenn Sie beide Arten von Regeln zulassen, erhalten Sie eine Klasse mit der Bezeichnung linear languages.

Zweitens, warum Lambda nur für das Startsymbol erlaubt ist.

Dies ist keine notwendige Einschränkung.

Sie können alle Verwendungen von Lambda für nichtterminale Symbole entfernen: Nehmen Sie eine Regel W -> Lambda, entfernen Sie sie und ersetzen Sie alle Regeln U -> aW durch U -> aW und U -> a. Offensichtlich können Sie die Verwendung von Lambda für das Terminalsymbol nicht eliminieren (die Sprache erzeugt kein leeres Wort mehr).

So kann jede Grammatik vom Typ 3, die an vielen Stellen Lambda verwendet, auf eine Grammatik "normalisiert" werden, die Lambda nur für das Startsymbol verwendet.