In der Mathematik, Informatik und Linguistik, ist eine formelle Sprache eine Reihe von Reihen von Symbolen.

Das Alphabet einer formellen Sprache ist der Satz von Symbolen, Briefen oder Jetons, von denen die Schnuren der Sprache gebildet werden können; oft ist es erforderlich, begrenzt zu sein. Die von diesem Alphabet gebildeten Schnuren werden Wörter genannt, und die Wörter, die einer besonderen formellen Sprache gehören, werden manchmal gut gebildete Wörter oder gut gebildete Formeln genannt. Eine formelle Sprache wird häufig mittels einer formellen Grammatik wie eine regelmäßige Grammatik oder Grammatik ohne Zusammenhänge, auch genannt seine Bildungsregel definiert.

Das Feld der formellen Sprachtheorie studiert die rein syntaktischen Aspekte solcher Sprachen — d. h. ihre inneren Strukturmuster. Formelle Sprachtheorie ist aus der Linguistik als eine Weise gesprungen, die syntaktische Regelmäßigkeit von natürlichen Sprachen zu verstehen.

In der Informatik werden formelle Sprachen häufig als die Basis verwendet, um Programmiersprachen und andere Systeme zu definieren, in denen die Wörter der Sprache mit besonderen Bedeutungen oder Semantik vereinigt werden. In der rechenbetonten Kompliziertheitstheorie werden Entscheidungsprobleme normalerweise als formelle Sprachen definiert, und Kompliziertheitsklassen werden als die Sätze der formellen Sprachen definiert, die durch Maschinen mit der beschränkten rechenbetonten Macht grammatisch analysiert werden können. In der Logik und den Fundamenten der Mathematik werden formelle Sprachen verwendet, um die Syntax von axiomatischen Systemen zu vertreten, und mathematischer Formalismus ist die Philosophie, dass die ganze Mathematik auf die syntaktische Manipulation von formellen Sprachen auf diese Weise reduziert werden kann.

Geschichte

Die erste formelle Sprache wird gedacht, diejenige zu sein, die von Gottlob Frege in seinem Begriffsschrift (1879) verwendet ist, wörtlich "das Konzeptschreiben" bedeutend, und den Frege als eine "formelle Sprache des reinen Gedankens beschrieben hat."

Das frühe Semi-Thue System von Axel Thue, das verwendet werden kann, um Schnuren umzuschreiben, war auf formelle Grammatiken einflussreich.

Wörter über ein Alphabet

Ein Alphabet, im Zusammenhang von formellen Sprachen, kann jeder Satz sein, obwohl es häufig Sinn hat, ein Alphabet in der üblichen Bedeutung des Wortes, oder mehr allgemein eine Codierung wie ASCII zu verwenden. Alphabete können auch unendlich sein; z.B wird Logik der ersten Ordnung häufig mit einem Alphabet ausgedrückt, das, außer Symbolen wie , ¬,  und Parenthesen, ungeheuer viele Elemente x, x, x, … enthält, die die Rolle von Variablen spielen. Die Elemente eines Alphabetes werden seine Briefe genannt.

Ein Wort über ein Alphabet kann jede begrenzte Folge oder Schnur von Briefen sein. Der Satz aller Wörter über ein Alphabet Σ wird gewöhnlich durch Σ angezeigt (den Stern von Kleene verwendend). Für jedes Alphabet gibt es nur ein Wort der Länge 0, das leere Wort, das häufig durch e, ε oder λ angezeigt wird. Durch die Verkettung kann man zwei Wörter verbinden, um ein neues Wort zu bilden, dessen Länge die Summe der Längen der ursprünglichen Wörter ist. Das Ergebnis, ein Wort mit dem leeren Wort zu verketten, ist das ursprüngliche Wort.

In einigen Anwendungen, besonders in der Logik, ist das Alphabet auch bekannt als das Vokabular, und Wörter sind als Formeln oder Sätze bekannt; das bricht die Metapher des Briefs/Wortes und ersetzt sie durch eine Metapher des Wortes/Satzes.

Definition

Eine formelle Sprache L über ein Alphabet Σ ist eine Teilmenge von Σ, d. h. einer Reihe von Wörtern über dieses Alphabet.

In der Informatik und Mathematik, die sich mit natürlichen Sprachen nicht gewöhnlich befassen, wird das "formelle" Adjektiv häufig als überflüssig weggelassen.

Während sich formelle Sprachtheorie gewöhnlich mit formellen Sprachen beschäftigt, die durch einige syntaktische Regeln beschrieben werden, ist die wirkliche Definition des Konzepts "formelle Sprache" nur als oben: (vielleicht unendlich) Satz von Schnuren der begrenzten Länge, nicht mehr noch weniger. In der Praxis gibt es viele Sprachen, die durch Regeln, wie regelmäßige Sprachen oder Sprachen ohne Zusammenhänge beschrieben werden können. Der Begriff einer formellen Grammatik kann am intuitiven Konzept einer "Sprache", eines beschriebenen durch syntaktische Regeln näher sein. Durch einen Missbrauch der Definition wird von einer besonderen formellen Sprache häufig als gedacht, mit einer formellen Grammatik ausgestattet werden, die es beschreibt.

Beispiele

Die folgenden Regeln beschreiben eine formelle Sprache über das Alphabet Σ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9,  +,  = }:

• Jede nichtleere Schnur, die "+" oder "=" nicht enthält und mit "0" nicht anfängt, ist darin.
• Die Schnur "0" ist darin.
• Eine Schnur, die "=" enthält, ist in wenn und nur, wenn es genau ein "=" gibt, und es zwei gültige Schnuren dessen trennt.
• Eine Schnur, die "+", aber nicht "=" enthält, ist darin, wenn, und nur wenn jeder "+" in der Schnur zwei gültige Schnuren dessen trennt.
• Keine Schnur ist im anderen als diejenigen, die durch die vorherigen Regeln einbezogen sind.

Laut dieser Regeln ist die Schnur "23+4=555" darin, aber die Schnur "=234 = +" ist nicht. Diese formelle Sprache drückt natürliche Zahlen, gut gebildete Hinzufügungsbehauptungen und gut gebildete Hinzufügungsgleichheiten aus, aber sie drückt nur aus, was sie (ihre Syntax), nicht aussehen, was sie (Semantik) vorhaben. Zum Beispiel, nirgends in diesen Regeln ist dort jede Anzeige, die "0" die Zahl-Null bedeutet, oder dass "+" Hinzufügung bedeutet.

Aufbauten

Für begrenzte Sprachen kann man alle gut gebildeten Wörter ausführlich aufzählen. Zum Beispiel können wir eine Sprache als gerade = {"a",  "b",  "ab",  "cba"} beschreiben. Der degenerierte Fall dieses Aufbaus ist die leere Sprache, die keine Wörter überhaupt enthält.

Jedoch, sogar über ein begrenztes (nichtleeres) Alphabet wie Σ = {a, b} gibt es ungeheuer viele Wörter: "a", "abb", "ababba", "aaababbbbaab", …. Deshalb sind formelle Sprachen normalerweise unendlich, und das Beschreiben einer unendlichen formellen Sprache ist nicht so einfach wie L = {"a",  "b",  "ab",  "cba"} schreibend. Hier sind einige Beispiele von formellen Sprachen:

• = Σ, der Satz aller Wörter über Σ;

• = {"a"} = {"a"}, wo N-Reihen über die natürlichen Zahlen und "den a" bedeutet, hat "a" n Zeiten wiederholt (das ist der Satz von Wörtern, die nur aus dem Symbol bestehen);
• der Satz dessen korrigiert syntaktisch Programme auf einer gegebenen Programmiersprache (dessen Syntax gewöhnlich durch eine Grammatik ohne Zusammenhänge definiert wird);
• der Satz von Eingängen, auf die eine bestimmte Maschine von Turing hinkt; oder
• der Satz von maximalen Reihen von alphanumerischen ASCII Charakteren auf dieser Linie, (d. h., der Satz {"Satz", "maximal", "Schnuren", "alphanumerisch", "ASCII", "Charaktere", "auf", "das", "Linie", "ich", "e"}).

Sprachspezifizierungsformalismen

Formelle Sprachtheorie beschäftigt sich selten mit besonderen Sprachen (außer als Beispiele), aber ist hauptsächlich mit der Studie von verschiedenen Typen von Formalismen beschäftigt, um Sprachen zu beschreiben. Zum Beispiel kann eine Sprache als gegeben werden

• jene Schnuren durch eine formelle Grammatik erzeugt;
• jene Schnuren, die beschrieben oder durch einen besonderen regelmäßigen Ausdruck verglichen sind;
• jene Schnuren, die durch einen Automaten, wie eine Maschine von Turing oder Zustandsautomat akzeptiert sind;
• jene Schnuren, für die ein Entscheidungsverfahren (ein Algorithmus, der eine Folge von zusammenhängenden JA/NO Fragen fragt) die Antwort JA erzeugt.

Typische nach solchen Formalismen gefragte Fragen schließen ein:

• Wie ist ihre ausdrucksvolle Macht? (Kann Formalismus X, jede Sprache beschreiben, die Formalismus Y beschreiben kann? Kann es andere Sprachen beschreiben?)
• Wie ist ihr recognizability? (Wie schwierig soll es entscheiden, ob ein gegebenes Wort einer Sprache gehört, die durch den Formalismus X beschrieben ist?)
• Wie ist ihre Vergleichbarkeit? (Wie schwierig soll es entscheiden, ob zwei Sprachen, ein beschriebener im Formalismus X und ein im Formalismus Y, oder in X wieder, wirklich dieselbe Sprache sind?).

Überraschend häufig ist die Antwort auf diese Entscheidungsprobleme "sie kann überhaupt nicht getan werden", oder "es ist" (mit einer Charakterisierung wie teuer) äußerst teuer. Deshalb ist formelle Sprachtheorie ein Hauptanwendungsgebiet der Berechenbarkeitstheorie und Kompliziertheitstheorie. Formelle Sprachen können in der Hierarchie von Chomsky klassifiziert werden, die auf der ausdrucksvollen Macht ihrer generativen Grammatik sowie der Kompliziertheit ihres Erkennens des Automaten gestützt ist. Grammatiken ohne Zusammenhänge und regelmäßige Grammatiken stellen einen guten Kompromiss zwischen expressivity und Bequemlichkeit der Syntaxanalyse zur Verfügung, und werden in praktischen Anwendungen weit verwendet.

Operationen auf Sprachen

Bestimmte Operationen auf Sprachen sind üblich. Das schließt die Standardsatz-Operationen, wie Vereinigung, Kreuzung und Ergänzung ein. Eine andere Klasse der Operation ist die mit dem Element kluge Anwendung von Schnur-Operationen.

Beispiele: Nehmen Sie L an, und L sind Sprachen über ein allgemeines Alphabet.

• Die Verkettung LL besteht aus allen Schnuren der Form vw, wo v eine Schnur von L und w ist, ist eine Schnur von L.
• Die Kreuzung L  L L und L besteht aus allen Schnuren, die in beiden Sprachen enthalten werden
• Die Ergänzung ¬ L einer Sprache in Bezug auf ein gegebenes Alphabet besteht aus allen Schnuren über das Alphabet, die nicht auf der Sprache sind.
• Der Kleene Stern: Die Sprache, die aus allen Wörtern besteht, die Verkettungen von 0 oder mehr Wörtern auf der ursprünglichen Sprache sind;
• Umkehrung:
• Lassen Sie e das leere Wort, dann e = e, und sein
• für jedes nichtleere Wort w = x … x über ein Alphabet, lassen Sie w = x … x,
• dann für eine formelle Sprache L, L = {w w  L}.
• Schnur-Homomorphismus

Solche Schnur-Operationen werden verwendet, um Verschluss-Eigenschaften von Klassen von Sprachen zu untersuchen. Eine Klasse von Sprachen wird unter einer besonderen Operation geschlossen, wenn die Operation, die auf Sprachen in der Klasse angewandt ist, immer eine Sprache in derselben Klasse wieder erzeugt. Zum Beispiel, wie man bekannt, werden die Sprachen ohne Zusammenhänge unter der Vereinigung, Verkettung und Kreuzung mit regelmäßigen Sprachen geschlossen, aber unter der Kreuzung oder Ergänzung nicht geschlossen. Die Theorie des Trios und der abstrakten Sprachfamilien studiert die allgemeinsten Verschluss-Eigenschaften von Sprachfamilien in ihrem eigenen Recht.

:

Anwendungen

Programmiersprachen

Ein Bearbeiter hat gewöhnlich zwei verschiedene Bestandteile. Ein lexikalischer Analysator, der durch ein Werkzeug wie erzeugt ist, identifiziert die Jetons der Programmiersprache-Grammatik, z.B Bezeichner oder Schlüsselwörter, die selbst auf einer einfacheren formellen Sprache gewöhnlich mittels regelmäßiger Ausdrücke ausgedrückt werden. Am grundlegendsten Begriffsniveau versucht ein parser, der gewöhnlich durch einen parser Generator wie erzeugt ist, zu entscheiden, ob das Quellprogramm gültig ist, ist dieser, wenn es der Programmiersprache gehört, für die der Bearbeiter gebaut wurde. Natürlich analysieren Bearbeiter wirklich mehr als gerade den Quellcode grammatisch — sie übersetzen ihn gewöhnlich in ein rechtskräftiges Format. Wegen dessen, ein parser gewöhnlich Produktionen mehr als ja/no Antwort, normalerweise ein abstrakter Syntax-Baum, der durch nachfolgende Stufen des Bearbeiters verwendet wird, um schließlich einen rechtskräftigen zu erzeugen, der Maschinencode enthält, der direkt auf der Hardware oder einem Zwischencode läuft, der verlangt, dass eine virtuelle Maschine durchführt.

Formelle Theorien, Systeme und Beweise

In der mathematischen Logik ist eine formelle Theorie eine Reihe von auf einer formellen Sprache ausgedrückten Sätzen.

Ein formelles System (hat auch eine logische Rechnung oder ein logisches System genannt), besteht aus einer formellen Sprache zusammen mit einem deduktiven Apparat (auch hat ein deduktives System genannt). Der deduktive Apparat kann aus einer Reihe von Transformationsregeln bestehen, die als gültige Regeln der Schlussfolgerung oder einer Reihe von Axiomen interpretiert werden, oder beide haben können. Ein formelles System wird verwendet, um einen Ausdruck von einem oder mehr anderen Ausdrücken abzuleiten. Obwohl eine formelle Sprache mit seinen Formeln identifiziert werden kann, kann ein formelles System nicht durch seine Lehrsätze ebenfalls identifiziert werden. Zwei formelle Systeme und können alle gleich Lehrsätze haben und sich noch auf eine bedeutende probetheoretische Weise unterscheiden (eine Formel A kann eine syntaktische Folge einer Formel B in einer, aber nicht einem anderen zum Beispiel sein).

Ein formeller Beweis oder Abstammung sind eine begrenzte Folge von gut gebildeten Formeln (der als Vorschläge interpretiert werden kann), von denen jeder ein Axiom ist oder aus den vorhergehenden Formeln in der Folge durch eine Regel der Schlussfolgerung folgt. Der letzte Satz in der Folge ist ein Lehrsatz eines formellen Systems. Formelle Beweise sind nützlich, weil ihre Lehrsätze als wahre Vorschläge interpretiert werden können.

Interpretationen und Modelle

Formelle Sprachen sind in der Natur völlig syntaktisch, aber können Semantik gegeben werden, die Bedeutung den Elementen der Sprache geben. Zum Beispiel, in der mathematischen Logik, ist der Satz von möglichen Formeln einer besonderen Logik eine formelle Sprache, und eine Interpretation teilt eine Bedeutung jeder der Formeln — gewöhnlich, ein Wahrheitswert zu.

Die Studie von Interpretationen von formellen Sprachen wird formelle Semantik genannt. In der mathematischen Logik wird das häufig in Bezug auf die Mustertheorie getan. In der Mustertheorie werden die Begriffe, die in einer Formel vorkommen, als mathematische Strukturen interpretiert und befestigt compositional Interpretationsregeln bestimmen, wie der Wahrheitswert der Formel aus der Interpretation seiner Begriffe abgeleitet werden kann; ein Modell für eine Formel ist eine Interpretation von solchen Begriffen, dass die Formel wahr wird.

Siehe auch

• Combinatorics auf Wörtern
• Grammatik-Fachwerk
• Formelle Methode
• Mathematische Notation

Referenzen

Allgemeine Verweisungen

• A. G. Hamilton, Logik für Mathematiker, Universität von Cambridge Presse, 1978, internationale Standardbuchnummer 0 521 21838 1.
• Seymour Ginsburg, Algebraisch und Automaten theoretische Eigenschaften von formellen Sprachen, Nordholland, 1975, internationale Standardbuchnummer 0 7204 2506 9.
• Michael A. Harrison, Einführung in die Formelle Sprachtheorie, Addison-Wesley, 1978.
• John E. Hopcroft und Jeffrey D. Ullman, Einführung in Automaten-Theorie, Sprachen, und Berechnung, Addison-Wesley Publishing, Massachusetts, 1979 Lesend. Internationale Standardbuchnummer 8178083477.

.

• Grzegorz Rozenberg, Arto Salomaa, Handbuch von Formellen Sprachen: Volumen I-III, Springer, 1997, internationale Standardbuchnummer 3 540 61486 9.
• Patrick Suppes, Einführung in die Logik, D. Van Nostrand, 1957, internationale Standardbuchnummer 0 442 08072 7.

Außenverbindungen

• Universität Marylands, formelle Sprachdefinitionen
• James Power, "Zeichen auf der Formellen Sprachtheorie und Syntaxanalyse", am 29. November 2002.
• Entwürfe von einigen Kapiteln im "Handbuch der Formellen Sprachtheorie", Vol. 1-3, G. Rozenberg und A. Salomaa (Hrsg.). Springer Verlag, (1997): t
• Alexandru Mateescu und Arto Salomaa, "Einleitung" in Vol.1, Seiten v-viii, und "Formelle Sprachen: Eine Einführung und eine Synopse", Kapitel 1 in Vol. 1, pp.1-39
• Sheng Yu, "Regelmäßige Sprachen", Kapitel 2 in Vol. 1
• Jean-Michel Autebert, Jean Berstel, Luc Boasson, "Sprachen ohne Zusammenhänge und Automaten des Stoßes unten", Kapitel 3 in Vol. 1
• Christian Choffrut und Juhani Karhumäki, "Combinatorics von Wörtern", Kapitel 6 in Vol. 1
• Tero Harju und Juhani Karhumäki, "Morphisms", Kapitel 7 in Vol. 1, Seiten 439 - 510
• Jean-Eric Pin, "Syntaktische Halbgruppen", Kapitel 10 in Vol. 1, Seiten 679-746
• M. Crochemore und C. Hancart, "Automaten, um Muster", Kapitel 9 in Vol zu vergleichen. 2
• Dora Giammarresi, Antonio Restivo, "Zweidimensionale Sprachen", Kapitel 4 in Vol. 3, Seiten 215 - 267