Einführung in die Grammatik

Im literarischen Sinne des Wortes bezeichnen Grammatiken syntaktische Regeln für die Konversation in natürlichen Sprachen. Die Linguistik hat seit Beginn natürlicher Sprachen wie Englisch, Sanskrit, Mandarin usw. versucht, Grammatiken zu definieren.

Die Theorie der formalen Sprachen findet ihre Anwendbarkeit weitgehend in den Bereichen der Informatik. Noam Chomsky gab 1956 ein mathematisches Grammatikmodell, das zum Schreiben von Computersprachen wirksam ist.

Grammatik

Eine Grammatik G kann formal als 4-Tupel (N, T, S, P) geschrieben werden, wobei -

N oder V_N ist eine Reihe von Variablen oder nicht-terminalen Symbolen.
T oder ∑ ist eine Reihe von Terminalsymbolen.
S ist eine spezielle Variable namens Startsymbol, S ∈ N.
Pist Produktionsregeln für Terminals und Nicht-Terminals. Eine Produktionsregel hat die Form α → β, wobei α und β Zeichenfolgen auf V _N ∪ ∑ sind und mindestens ein Symbol von α zu V _{N gehört} .

Beispiel

Grammatik G1 -

({S, A, B}, {a, b}, S, {S → AB, A → a, B → b})

Hier,

S, A, und B sind nicht-terminale Symbole;
a und b sind Terminalsymbole
S ist das Startsymbol, S ∈ N.
Produktionen, P : S → AB, A → a, B → b

Beispiel

Grammatik G2 -

(({S, A}, {a, b}, S, {S → aAb, aA → aaAb, A → ε})

Hier,

S und A sind nicht terminale Symbole.
a und b sind Terminalsymbole.
ε ist eine leere Zeichenfolge.
S ist das Startsymbol, S ∈ N.
Produktion P : S → aAb, aA → aaAb, A → ε

Ableitungen aus einer Grammatik

Strings können unter Verwendung der Produktionen in einer Grammatik von anderen Strings abgeleitet werden. Wenn eine GrammatikG hat eine Produktion α → β, Wir können das sagen x α y leitet ab x β y im G. Diese Ableitung wird geschrieben als -

x α y ⇒G x β y