|
|
Kurze Darstellung von Sprachen und Grammatik in Bezug auf die Unterteilung in Typen
Der Pfeil einer Produktionsregel wird durch das Zeichen ::=. Alternativen werden durch eine vertikale Linie getrennt ½ Gebogene Klammern {} bedeuten Wiederholungen und eckige Klammern [] umschließen optionale Teile.
Terminalsymbole sind Zeichen oder Wörter, die nicht mehr weiter aufgeschlüsselt werden können und zur Formulierung jedes Satzes einer Sprache verwendet werden.
Deutsch = {a, …z, A, …Z, derjenige, der”der, Professor, Student,…}
T*: Satz aller Wörter, die durch Aneinanderreihung vieler Terminalsymbole erzeugt werden können, einschließlich des leeren Wortes e. Non-terminal N: Hilfssymbole, die zur Formulierung der Grammatikregeln verwendet werden können. Jedes nichtterminale Symbol entspricht einer Variablen und kann in eine Folge von anderen nichtterminalen und terminalen Symbolen umgeschrieben werden. .}
äquivalent zu T*, N* ist definiert.
Produktionen P: enthält Regeln für den Aufbau von Sprachstrings und legt fest, wie ein nicht-terminales Symbol weiter ersetzt werden kann. Sie werden üblicherweise in der Notation u v angegeben. Es gilt: u,v 0 (T È N)* Für eine solche Regel muss u mindestens ein nicht-terminales Symbol enthalten. . Dies bedeutet, dass ein Satz aus einem Subjekt, einem Prädikat (e
s gibt zwei konkurrierende Begriffe des Prädikat
s in den Theorien der Grammatik), einem Objekt und einem Punkt am Ende besteht.
Startzeichen S: Ein Startsymbol S ist ein hervorragendes nicht-terminales Symbol, mit dem jede Anwendung von Produktionsregeln beginnt. Beispielsweise ist für die deutsche Sprache das nicht-terminale Symbol-Set ein Startsymbol.
Die formale Sprache (In der Mathematik, Informatik und Linguistik ist eine formale Sprache ein Satz von Zeichenketten zusammen mit einem Satz von Regeln, die für sie spezifisch sind) L(G), der durch die Grammatik G erzeugt wird, wird durch den Satz aller Wörter w definiert, die nur aus terminalen Symbolen bestehen und die alle aus dem Startsymbol abgeleitet werden können (In der formalen Sprachtheorie ist eine Grammatik ein Satz von Produktionsregeln für Zeichenketten in einer formalen Sprache). Dies sind endliche Automaten, die um einen Keller erweitert werden, um bereits erkannte Zeichen zu speichern.
“u v von P bedeutet: u Î (T È N)+ = (T È N)* \ {e}, v Î (T È N)* Die beiden damit verbundenen Anforderungen sind, dass sich auf der linken Seite mindestens ein nicht-terminales Symbol befinden muss und u nicht das leere Wort e ist.2 Beispiel Die folgende Grammatik erzeugt die Sprache L(G)={ai ½ mit i als positiver Potenz von zwei} G=(T, N, P, S) G=({S, A, B, C, D, E},{a}, P, S) P={S ACaB, aD Da, Ca aaC, AD AC, CB DB, aE Ea, CB E, AE e} Eine Turingmaschine ist ein 7-Tupel (ein Tupel ist eine endlich geordnete Liste von Elementen) T = (X,B,Z,d,b,z0,ZE), wobei folgendes gilt: 1 kontextsensitive Grammatik (Eine kontextsensitive Grammatik ist eine formale Grammatik, bei der die linke und die rechte Seite einer Produktionsregel von einem Kontext aus terminalen und nicht-terminalen Symbolen umgeben sein können): “x y aus P, $ A Î N und w1, w2, v Î (T È N)* mit v ¹ e, so dass ab x = w1Aw2 y=w1vw2 folgt Das bedeutet, dass A nur im Kontext w1……
(X, Y, Z, h, z0, F) eine (nicht-deterministische) Turingmaschine (Eine Turingmaschine ist eine abstrakte Maschine, die Symbole auf einem Bandstreifen nach einer Regeltabelle manipuliert; genauer gesagt, es ist ein mathematisches Rechenmodell, das ein solches Gerät definiert) (ohne Leerzeichen), – – [] (Die Kantenmarken dürfen weder geschrieben, verändert noch überschritten werden. 4. Typ 2 Sprachen Dies sind Sprachen mit einer Typ 2 Grammatik.
Zulässig: N = {(, ), +, -, *, /, a, b, c, d, e} S = S P = { S A, A T½+T½-T½+T½A (2A19 oder T-12 ist eine sowjetische glatte 100-mm-Panzerabwehrkanone, die von 1960 bis Ende der 1980er Jahre als Hauptpanzerabwehrkanone des Ostblocks diente) -T, T P½T*P½T/P, P (A) ½a½b½c½d½e} Definition: Eine Struktur K = ( X, Y, Z, h, z0, S, F) bedeutet (endlicher) Automat, wenn – X (Eingangsalphabet), Y (Kelleralphabet), Z (Zustandsmenge) nicht leere endliche Mengen, – z0Î Z (Anfangszustand), SÎ Y (Startsymbol), FÍ Z (Endzustand), – h eine Funktion von ( XÈ {e} )x Zx Y in die Menge aller endlichen Teilmengen von Zx Y*.
Das bisher verwendete zusammengesetzte Zeichen È kann nicht verwendet werden, da hier die genaue Reihenfolge wichtig ist und die Kombination der Größen kommutativ ist.
Zulässig: A aaB, B b Verboten: Hinweis: Die hier aufgeführten Einzeltypen werden in den meisten Literaturquellen als Chomsky-Typen bezeichnet. Das ist auch richtig, aber ich habe den Chomsky hier wegen seiner Einfachheit weggelassen. Lassen Sie mich in diesem Zusammenhang nur ein paar Worte sagen. Eine Sprache L Í T* ist vom Chomsky-Typ-i(i=0,1,2,3), wenn eine Chomsky-Grammatik (In den formalen Sprachen der Informatik und Linguistik ist die Chomsky-Hierarchie eine Einschließungshierarchie von Klassen formaler Grammatiken) G dieses Typs i existiert, die diese Sprache L = L(G) erzeugt. Die gängigen Programmiersprachen sind alle kontextfrei (wiederum der Wichtigkeit und Vollständigkeit halber). Um an der Vollendung festzuhalten. Die Vollständigkeit der Chomsky Lehre (Hierarchie) wird durch die Klassifizierung der algorithmischen Sprachklassen (Entscheidungsfähigkeit) und der Klassen der akzeptierenden Automaten erreicht: