Formelle Sprache

Struktur des syntaktisch gut geformten, wenn auch unsinnigen, englischen Satzes, "Farblose grüne ideen schlafen wütend" (Historisches Beispiel aus Chomsky 1957).

Im Logik, Mathematik, Informatik, und Linguistik, a formelle Sprache besteht aus Wörter Deren Briefe werden von einem entnommen Alphabet und sind gut geformt Nach einer bestimmten Reihe von Regeln.

Das Alphabet einer formalen Sprache besteht aus Symbolen, Buchstaben oder Token, die sich in Strings der Sprache verkünden.^[1] Jede Zeichenfolge, die von Symbolen dieses Alphabets verkettet wird, wird ein Wort genannt, und die Wörter, die zu einer bestimmten formalen Sprache gehören Gut geformte Wörter oder gut geformte Formeln. Eine formale Sprache wird oft durch a definiert formelle Grammatik so wie ein Regelmäßige Grammatik oder Kontextfreie Grammatik, was aus seinem besteht Formationsregeln.

Das Feld von Formale Sprachtheorie Studien in erster Linie die rein syntaktisch Aspekte solcher Sprachen, dh ihre internen strukturellen Muster. Die formale Sprachtheorie entstand aus der Linguistik, um die syntaktischen Regelmäßigkeiten von zu verstehen natürliche Sprachen. In der Informatik werden formale Sprachen unter anderem als Grundlage für die Definition der Grammatik von verwendet Programmiersprachen und formalisierte Versionen von Teilmengen natürlicher Sprachen, in denen die Wörter der Sprache Konzepte darstellen, die mit bestimmten Bedeutungen verbunden sind oder Semantik. Im Computerkomplexitätstheorie, Entscheidungsprobleme werden normalerweise als formale Sprachen definiert, und Komplexitätsklassen werden definiert als die Sätze der formalen Sprachen, die sein können Analysiert von Maschinen mit begrenzter Rechenleistung. Im Logik und die Grundlagen der Mathematik, formale Sprachen werden verwendet, um die Syntax von darzustellen Axiomatische Systeme, und mathematischer Formalismus ist die Philosophie, dass alle Mathematik auf diese Weise auf die syntaktische Manipulation formaler Sprachen reduziert werden können.

Geschichte

Der erste Gebrauch der formalen Sprache wird angenommen Gottlob Frege1879 BEGRIFFSSCHRIFT, was "Konzeptschreiben" bedeutet, die eine "formale Sprache, die auf die der Arithmetik modelliert wurde, für reine Gedanken" modelliert ".^[2]

Axel Thue'S früh Semi-Thue-System, die zum Umschreiben von Saiten verwendet werden können, war einflussreich auf formelle Grammatiken.

Worte über einem Alphabet

Ein Alphabetim Kontext formaler Sprachen kann jeder sein einstellen, obwohl es oft sinnvoll ist, eine zu verwenden Alphabet im üblichen Sinne des Wortes oder allgemeiner endlich Zeichenkodierung wie zum Beispiel ASCII oder Unicode. Die Elemente eines Alphabets werden als ITS bezeichnet Briefe. Ein Alphabet kann eine enthalten unendlich Anzahl der Elemente;^{[Anmerkung 1]} Die meisten Definitionen in der formalen Sprachtheorie geben Alphabete jedoch mit einer begrenzten Anzahl von Elementen an, und die meisten Ergebnisse gelten nur für sie.

A Wort über einem Alphabet kann jede endliche Sequenz sein (d. H., Saite) von Briefen. Die Menge aller Wörter über einem Alphabet σ wird normalerweise durch σ bezeichnet^* (Verwendung der Kleene Star). Die Länge eines Wortes ist die Anzahl der Buchstaben, aus denen es besteht. Für jedes Alphabet gibt es nur ein Wort der Länge 0, die leeres Wort, was oft mit E, ε, λ oder sogar λ bezeichnet wird. Durch Verkettung Man kann zwei Wörter kombinieren, um ein neues Wort zu bilden, dessen Länge die Summe der Längen der ursprünglichen Wörter ist. Das Ergebnis der Verkettung eines Wortes mit dem leeren Wort ist das ursprüngliche Wort.

In einigen Anwendungen, insbesondere in LogikDas Alphabet ist auch als das bekannt als das Wortschatz und Worte sind als bekannt als Formeln oder Sätze; Dies bricht die Buchstaben-/Wortmetapher und ersetzt ihn durch eine Wort-/Satzmetapher.

Definition

A formelle Sprache L über einem Alphabet σ ist a Teilmenge von σ^*Das heißt, eine Reihe von Wörtern über das Alphabet. Manchmal werden die Wörtersätze in Ausdrücke unterteilt, während Regeln und Einschränkungen für die Erstellung von „gut geformten Ausdrücken“ formuliert werden können.

In Informatik und Mathematik, die sich normalerweise nicht befassen natürliche SprachenDas Adjektiv "formal" wird oft als überflüssig weggelassen.

Während die formale Sprachtheorie sich normalerweise mit formalen Sprachen betrifft, die durch einige syntaktische Regeln beschrieben werden, ist die tatsächliche Definition des Konzepts "formale Sprache" nur wie oben: a (möglicherweise unendlich) Satz von Strings mit endlicher Länge aus einem bestimmten Alphabet, Nicht mehr und nicht weniger. In der Praxis gibt es viele Sprachen, die nach Regeln beschrieben werden können, wie z. reguläre Sprachen oder Kontextfreie Sprachen. Die Vorstellung von a formelle Grammatik kann dem intuitiven Konzept einer "Sprache" näher sein, eine durch syntaktische Regeln beschriebene. Durch einen Missbrauch der Definition wird eine bestimmte formale Sprache oft als mit einer formalen Grammatik ausgestattet, die sie beschreibt.

Beispiele

Die folgenden Regeln beschreiben eine formale Sprache $L$ über dem Alphabet σ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9,+, =}:

Jede nicht leere Zeichenfolge, die nicht -or "=" enthält und nicht mit "0" beginnt $L$ .
Die Zeichenfolge "0" ist in $L$ .
Eine Zeichenfolge, die "=" enthält $L$ Wenn und nur wenn es genau eins "=" gibt und es zwei gültige Zeichenfolgen von trennt $L$ .
Eine Zeichenfolge, die "+", aber nicht "=" enthält $L$ Wenn und nur wenn jeder "+" in der Zeichenfolge zwei gültige Zeichenfolgen von trennt $L$ .
Keine Zeichenfolge ist in $L$ Anders als diejenigen, die durch die vorherigen Regeln impliziert sind.

Nach diesen Regeln befindet sich die Zeichenfolge "23+4 = 555" in $L$ , aber die Zeichenfolge "= 234 =+" ist nicht. Diese formale Sprache drückt aus natürliche Zahlen, gut geformte Ergänzungen und gut geformte Zusatzgleichheiten, aber es drückt nur aus, wie sie aussehen (ihre Syntax), nicht das, was sie meinen (Semantik). Nirgendwo in diesen Regeln gibt es einen Hinweis darauf, dass "0" die Zahl Null bedeutet, "+" Zugabe "23+4 = 555" falsch usw.

Konstruktionen

Für endliche Sprachen kann man alle gut geformten Wörter explizit aufzählen. Zum Beispiel können wir eine Sprache beschreiben $L$ wie gerecht $L$ = {A, b, ab, cba}. Das degenerieren Fall dieser Konstruktion ist der leere Sprache, was überhaupt keine Worte enthält ( $L$ =∅).

Aber selbst über ein endliches (nicht leeres) Alphabet wie σ = {a, b} gibt es eine unendliche Anzahl von Wörtern mit endlicher Länge, die möglicherweise ausgedrückt werden können: "A", "Abb", "Ababba", "," aaababbbbaab ", .... Daher sind formale Sprachen typischerweise unendlich, und die Beschreibung einer unendlichen formalen Sprache ist nicht so einfach wie das Schreiben L= {A, b, ab, cba}. Hier sind einige Beispiele für formale Sprachen:

$L$ = Σ^*, der Satz von alle Wörter über σ;
$L$ = {a}^* = {aⁿ}, wo n reicht über die natürlichen Zahlen und "aⁿ"bedeutet" a "wiederholt n Zeiten (dies ist die Menge von Wörtern, die nur aus dem Symbol "a" bestehen);
Der Satz syntaktisch korrekter Programme in einer bestimmten Programmiersprache (deren Syntax wird normalerweise durch a definiert Kontextfreie Grammatik);
die Menge von Eingängen, auf denen eine bestimmte Turing Maschine hält an; oder
der Satz maximaler Saiten von alphanumerisch ASCII Zeichen in dieser Zeile, d. H.,
Das Set {the, set, von, maximal, saiten, alphanumerisch, ascii, Zeichen, auf, this, line, i, e}.

Sprachspezifikationsformalismen

Formale Sprachen werden in mehreren Disziplinen als Tools verwendet. Die formale Sprachtheorie betrifft sich jedoch selten mit bestimmten Sprachen (außer als Beispiele), befasst sich jedoch hauptsächlich mit der Untersuchung verschiedener Arten von Formalismen zur Beschreibung von Sprachen. Zum Beispiel kann eine Sprache als angegeben werden

diese Strings, die von einigen erzeugt werden formelle Grammatik;
Diese von einem bestimmten beschriebenen oder übereinstimmenden Saiten regulären Ausdruck;
diese von einigen akzeptierten Saiten Automat, so wie ein Turing Maschine oder Finite-State-Automaten;
diese Saiten, für die einige Entscheidungsverfahren (ein Algorithmus Damit wird eine Abfolge von verwandten Ja/Nein -Fragen gefragt) die Antwort Ja.

Typische Fragen zu solchen Formalismen sind:

Was ist ihre ausdrucksstarke Kraft? (Kann Formalismus X Beschreiben Sie jede Sprache, die diesen Formalismus Y Kann beschreiben? Kann es andere Sprachen beschreiben?)
Was ist ihre Erkennbarkeit? (Wie schwierig ist es zu entscheiden, ob ein bestimmtes Wort einer vom Formalismus beschriebenen Sprache gehört X?)
Was ist ihre Vergleichbarkeit? (Wie schwierig ist es zu entscheiden, ob zwei Sprachen im Formalismus beschrieben werden X und eine im Formalismus Y, oder in X sind wieder tatsächlich die gleiche Sprache?).

Überraschend oft lautet die Antwort auf diese Entscheidungsprobleme "Es kann überhaupt nicht getan werden" oder "es ist extrem teuer" (mit einer Charakterisierung der teuer). Daher ist die formale Sprachtheorie ein wichtiger Anwendungsbereich von Computerbarkeitstheorie und Komplexitätstheorie. Formale Sprachen können in der klassifiziert werden Chomsky -Hierarchie basierend auf der ausdrucksstarken Kraft ihrer generativen Grammatik sowie der Komplexität ihrer Erkennung Automat. Kontextfreie Grammatiken und Regelmäßige Grammatiken einen guten Kompromiss zwischen Ausdruck und Leichtigkeit bieten Parsingund werden in praktischen Anwendungen häufig verwendet.

Operationen auf Sprachen

Bestimmte Operationen zu Sprachen sind üblich. Dies umfasst die Standard -Set -Operationen wie Gewerkschaft, Kreuzung und Komplement. Eine weitere Betriebsklasse ist die elementweise Anwendung von String-Operationen.

Beispiele: Angenommen ${\ displayStyle l_ {1}}$ und ${\ displayStyle l_ {2}}$ sind Sprachen über einem gemeinsamen Alphabet ${\ displayStyle \ sigma}$ .

Das Verkettung ${\ displayStyle l_ {1} \ cdot l_ {2}}$ besteht aus allen Saiten der Form ${\ displayStyle vw}$ wo ${\ displayStyle v}$ ist eine Zeichenfolge von ${\ displayStyle l_ {1}}$ und ${\ displayStyle W}$ ist eine Zeichenfolge von ${\ displayStyle l_ {2}}$ .
Das Überschneidung ${\ displayStyle l_ {1} \ cap l_ {2}}$ von ${\ displayStyle l_ {1}}$ und ${\ displayStyle l_ {2}}$ besteht aus allen Zeichenfolgen, die in beiden Sprachen enthalten sind
Das ergänzen ${\ displaystyle \ neg l_ {1}}$ von ${\ displayStyle l_ {1}}$ in Gedenken an ${\ displayStyle \ sigma}$ besteht aus allen Saiten vorbei ${\ displayStyle \ sigma}$ das sind nicht in ${\ displayStyle l_ {1}}$ .
Das Kleene Star: Die Sprache, die aus allen Wörtern besteht, die in der Originalsprache mit Zerkleinerung von Null oder mehr Wörtern bestehen;
Umkehrung:
- Lassen ε Sei dann das leere Wort ${\ displayStyle \ varepsilon ^{r} = \ varepsilon}$ , und
- Für jedes nicht leere Wort ${\ displayStyle w = \ sigma _ {1} \ cdots \ sigma _ {n}}$ (wo ${\ displaystyle \ sigma _ {1}, \ ldots, \ sigma _ {n}}$ sind Elemente eines Alphabets), lassen ${\ displayStyle w^{r} = \ sigma _ {n} \ cdots \ sigma _ {1}}$ ,
- dann für eine formelle Sprache ${\ displayStyle l}$ , ${\ displayStyle l^{r} = \ {w^{r} \ Mid W \ in l \}}$ .
String -Homomorphismus

Eine solche String -Operationen werden verwendet, um zu untersuchen Verschlusseigenschaften von Sprachenklassen. Eine Klasse von Sprachen wird unter einer bestimmten Operation geschlossen, wenn die Operation, die auf Sprachen in der Klasse angewendet wird, immer wieder eine Sprache in derselben Klasse erzeugt. Zum Beispiel die Kontextfreie Sprachen sind bekanntermaßen unter Union, Verkettung und Schnittpunkt mit geschlossen reguläre Sprachen, aber nicht unter Kreuzung oder Komplement geschlossen. Die Theorie von Trios und abstrakte Familien von Sprachen Studien Sie die häufigsten Schließeigenschaften von Sprachfamilien.^[3]

Verschlusseigenschaften von Sprachfamilien ( ${\ displayStyle l_ {1}}$ Op ${\ displayStyle l_ {2}}$ wo beide ${\ displayStyle l_ {1}}$ und ${\ displayStyle l_ {2}}$ sind in der Sprachfamilie, die durch die Spalte gegeben wird). Nach Hopcroft und Ullman.
Betrieb		Regulär	DCFL	CFL	Ind	CSL	rekursiv	BETREFFEND
Union	$oder$	Ja	Nein	Ja	Ja	Ja	Ja	Ja
Überschneidung	$oder$	Ja	Nein	Nein	Nein	Ja	Ja	Ja
Ergänzen	${\ displayStyle \ neg l_ {1} = \ {w \ Mid W \ nicht \ in l_ {1} \}}$	Ja	Ja	Nein	Nein	Ja	Ja	Nein
Verkettung	$oder$	Ja	Nein	Ja	Ja	Ja	Ja	Ja
Kleene Star	$oder$	Ja	Nein	Ja	Ja	Ja	Ja	Ja
(String) Homomorphismus ${\ displayStyle H}$	${\ displayStyle h (l_ {1}) = \ {h (w) \ Mid W \ in l_ {1} \}}$	Ja	Nein	Ja	Ja	Nein	Nein	Ja
ε-frei (String) Homomorphismus ${\ displayStyle H}$	${\ displayStyle h (l_ {1}) = \ {h (w) \ Mid W \ in l_ {1} \}}$	Ja	Nein	Ja	Ja	Ja	Ja	Ja
Auswechslung ${\ displayStyle \ varphi}$	${\ displaystyle \ varphi (l_ {1}) = \ bigcup _ {\ sigma _ {1} \ cdots \ sigma _ {n} \ in l_ {1} \ varphi (\ sigma _ {1}) \ cdot \ ldots \ cdot \ varphi (\ sigma _ {n})}$	Ja	Nein	Ja	Ja	Ja	Nein	Ja
Inverser Homomorphismus ${\ displayStyle H^{-1}}$	${\ displayStyle h^{-1} (l_ {1}) = \ bigcup _ {w \ in l_ {1}} h^{-1} (w)}$	Ja	Ja	Ja	Ja	Ja	Ja	Ja
Umkehren	${\ displayStyle l^{r} = \ {w^{r} \ Mid W \ in l \}}$	Ja	Nein	Ja	Ja	Ja	Ja	Ja
Kreuzung mit a Regelmäßige Sprache ${\ displayStyle r}$	${\ displayStyle l \ cap r = \ {W \ Mid W \ in l \ land W \ in r \}}$	Ja	Ja	Ja	Ja	Ja	Ja	Ja

Anwendungen

Programmiersprachen

Ein Compiler hat normalerweise zwei unterschiedliche Komponenten. EIN Lexikalanalysator, manchmal von einem Werkzeug wie erzeugt wie Lexidentifiziert die Token der Programmiersprache Grammatik, z. Kennungen oder Schlüsselwörter, numerische und String -Literale, Zeichensetzung und Bedienersymbole, die selbst durch eine einfachere formale Sprache angegeben sind Reguläre Ausdrücke. Auf der grundlegendsten konzeptionellen Ebene a Parser, manchmal von a generiert Parser -Generator wie yacc, Versuche zu entscheiden, ob das Quellprogramm syntaktisch gültig ist, dh wenn es in Bezug auf die Programmiersprache, für die der Compiler gebaut wurde, gut geformt ist.

Natürlich analysieren Compiler mehr als nur den Quellcode - sie übersetzen ihn normalerweise in ein ausführbares Format. Aus diesem Grund gibt ein Parser normalerweise mehr als eine Ja/Nein -Antwort aus, normalerweise eine Zusammenfassung Syntaxbaum. Dies wird durch nachfolgende Stadien des Compilers verwendet, um schließlich eine zu erzeugen ausführbar enthält Maschinensprache das läuft direkt auf der Hardware oder einer Zwischencode das erfordert a virtuelle Maschine ausführen.

Formale Theorien, Systeme und Beweise

Dieses Diagramm zeigt das syntaktisch Abteilungen innerhalb von a formelles System. Saiten von Symbolen kann weitgehend in Unsinn unterteilt sein und gut geformte Formeln. Der Satz wohlgeformter Formeln ist in unterteilt in Theoreme und Nicht-Theoreme.

Im Mathematische Logik, a Formale Theorie ist ein Satz von Sätze in einer formalen Sprache ausgedrückt.

A formelles System (auch a genannt logischer Kalkül, oder ein logisches System) besteht aus einer formalen Sprache zusammen mit a deduktionierter Apparat (auch a genannt deduktives System). Der deduktive Apparat kann aus einem Satz von bestehen Transformationsregeln, die als gültige Inferenzregeln oder als Satz von interpretiert werden können Axiome, oder beides haben. Ein formales System wird gewohnt ableiten Ein Ausdruck aus einem oder mehreren anderen Ausdrücken. Obwohl eine formale Sprache mit ihren Formeln identifiziert werden kann, kann ein formales System nicht durch seine Theoreme identifiziert werden. Zwei formale Systeme ${\ displaystyle {\ mathcal {fs}}}$ und ${\ displaystyle {\ mathcal {fs '}}}$ kann alle die gleichen Theoreme haben und unterscheiden sich dennoch in einer signifikanten Proode-theoretischen Weise (eine Formel A kann eine syntaktische Folge einer Formel B in einem, aber nicht in einem anderen sein).

A formeller Beweis oder Ableitung ist eine endliche Folge wohlgeformter Formeln (die als Sätze interpretiert werden können, oder Aussagen) Jedes davon ist ein Axiom oder folgt aus den vorhergehenden Formeln in der Sequenz durch a Inferenzregel. Der letzte Satz in der Sequenz ist ein Satz eines formalen Systems. Formale Beweise sind nützlich, da ihre Theoreme als wahre Aussagen interpretiert werden können.

Interpretationen und Modelle

Formale Sprachen sind völlig syntaktisch, können aber gegeben werden Semantik das gibt den Elementen der Sprache Sinn. Zum Beispiel in mathematischer Sprache Logik, die Menge möglicher Formeln einer bestimmten Logik ist eine formale Sprache und eine Deutung weist jedem der Formeln eine Bedeutung zu - normalerweise a Wahrheitswert.

Das Studium der Interpretationen formaler Sprachen wird genannt formelle Semantik. In der mathematischen Logik wird dies oft in Bezug auf Modelltheorie. In der Modelltheorie werden die Begriffe, die in einer Formel auftreten Mathematische Strukturen, und feste Zusammensetzungsinterpretationsregeln bestimmen, wie der Wahrheitswert der Formel aus der Interpretation ihrer Begriffe abgeleitet werden kann; a Modell Denn eine Formel ist eine Interpretation von Begriffen, so dass die Formel wahr wird.

Siehe auch

Anmerkungen

^ Zum Beispiel, Logik erster Ordnung wird oft unter Verwendung eines Alphabets ausgedrückt, das neben Symbolen wie ∧, ¬, ∀ und Klammern unendlich viele Elemente enthält x₀Anwesendx₁Anwesendx₂,… Das spielt die Rolle von Variablen.

Verweise

Zitate

^ Siehe z. Reghizzi, Stefano Crespi (2009), Formelle Sprachen und Zusammenstellung, Texte in Informatik, Springer, p. 8,, Bibcode:2009flc..book ..... c, ISBN 9781848820500, Ein Alphabet ist ein endliches Set.
^ Martin Davis (1995). "Einflüsse der mathematischen Logik auf die Informatik". In Rolf Herken (Hrsg.). Die universelle Turing-Maschine: eine Umfrage des halben Jahrhunderts. Springer. p. 290. ISBN 978-3-211-82637-9.
^ Hopcroft & Ullman (1979), Kapitel 11: Verschlusseigenschaften von Familien von Sprachen.

Quellen

Werke zitiert

John E. Hopcroft und Jeffrey D. Ullman, Einführung in die Automatentheorie, Sprachen und Berechnung, Addison-Wesley Publishing, Reading Massachusetts, 1979. ISBN81-7808-347-7.

Allgemeine Referenzen

A. G. Hamilton, Logik für Mathematiker, Cambridge University Press, 1978, ISBN0-521-21838-1.
Seymour Ginsburg, Algebraische und automatische theoretische Eigenschaften formaler Sprachen, North-Holland, 1975, ISBN0-7204-2506-9.
Michael A. Harrison, Einführung in die formale Sprachtheorie, Addison-Wesley, 1978.
Rautenberg, Wolfgang (2010). Eine kurze Einführung in die mathematische Logik (3. Aufl.). New York, NY: Springer Science+Business Media. doi:10.1007/978-1-4419-1221-3. ISBN 978-1-4419-1220-6..
Grzegorz Rozenberg, Arto Salomaa, Handbuch der formellen Sprachen: Band I-III, Springer, 1997, ISBN3-540-61486-9.
Patrick untersucht, Einführung in die Logik, D. van Nostrand, 1957,, ISBN0-442-08072-7.

Externe Links

"Formelle Sprache", Enzyklopädie der Mathematik, EMS Press, 2001 [1994]
Universität von Maryland, Formale Sprachdefinitionen
James Power, "Anmerkungen zur formalen Sprachtheorie und zur Parsen" Archiviert 21. November 2007 bei der Wayback -Maschine, 29. November 2002.
Entwürfe einiger Kapitel im "Handbuch der formalen Sprachtheorie", vol. 1–3, G. Rozenberg und A. Salomaa (Hrsg.), Springer Verlag, (1997):
- Alexandru Mateescu und Arto Salomaa, "Vorwort" in Vol.1, S. V - VIII und "Formale Sprachen: Eine Einführung und eine Zusammenfassung", Kapitel 1 in Vol. 1, S. 1–39
- Sheng Yu, "Reguläre Sprachen", Kapitel 2 in Vol. 1
- Jean-Michel Autert, Jean Berstel, Luc Boasson, "Kontextfreie Sprachen und Push-Down-Automaten", Kapitel 3 in Vol. 1
- Christian Choffrut und Juhani Karhumäki, "Kombinatorik von Wörtern", Kapitel 6 in Vol. 1
- Tero harju und juhani karhumäki, "Morphismen", Kapitel 7 in Vol. 1, S. 439–510
- Jean-erischer Pin, "Syntaktische Semigroups", Kapitel 10 in Vol. 1, S. 679–746
- M. Crochemore und C. Hancart, "Automaten für Matching -Muster", Kapitel 9 in Vol. 2
- Dora Giammarresi, Antonio Restivo, "Zweidimensionale Sprachen", Kapitel 4 in Vol.3, S. 215–267

[3] Zum Beispiel, Logik erster Ordnung wird oft unter Verwendung eines Alphabets ausgedrückt, das neben Symbolen wie ∧, ¬, ∀ und Klammern unendlich viele Elemente enthält x₀Anwesendx₁Anwesendx₂,… Das spielt die Rolle von Variablen.

[1] Siehe z. Reghizzi, Stefano Crespi (2009), Formelle Sprachen und Zusammenstellung, Texte in Informatik, Springer, p. 8,, Bibcode:2009flc..book ..... c, ISBN 9781848820500, Ein Alphabet ist ein endliches Set.

[Herken1279-2] Martin Davis (1995). "Einflüsse der mathematischen Logik auf die Informatik". In Rolf Herken (Hrsg.). Die universelle Turing-Maschine: eine Umfrage des halben Jahrhunderts. Springer. p. 290. ISBN 978-3-211-82637-9.

[4] Hopcroft & Ullman (1979), Kapitel 11: Verschlusseigenschaften von Familien von Sprachen.

[1]

[2]

[Anmerkung 1]

[3]