Ein Versuch, die Grammatik einer Sprache in mathematische Ausdrücke zu formulieren. Sprache Theorie ist ein wichtiger Teilbereich der Linguistik und Informatik. Formale Sprache Theorie wurde in der Mitte der 1950er Jahre in einem Versuch, Theorien auf natürlichen Spracherwerb initiiert. Dieser Theorie, und insbesondere kontextfreien Grammatiken, wurde festgestellt, dass in Computern verwendeten Sprachen relevant sein. Interesse an der Beziehung zwischen abstrakten Sprachen und Automaten Theorie begann mit einer bahnbrechenden Papier von S. C. Kleene 1956, in dem er die Sprachen gekennzeichnet in denen Mitgliedschaft eines Satzes durch ein endlicher Automat beschlossen werden könnte. Formal oder abstrakt Sprachen basieren auf den mathematischen Begriff einer Sprache wie etwa 1956 von Noam Chomsky definiert. , Dieses Konzept zu verstehen wir zunächst definieren was eine Sprache ist. The New Oxford American Dictionary definiert es als "die Methode der menschlichen Kommunikation, gesprochen oder geschrieben, bestehend aus der Verwendung von Wörtern in einer strukturierten und konventionelle Weise." Diese Definition ist jedoch zu vage, als ein Baustein einer Theorie der Sprache zu verwenden. , Die Vorstellung von einer abstrakten Sprache zu formalisieren ist es erforderlich, einige vorläufigen Definitionen einzuführen. Ein Alphabet, Wortschatz oder der Satz von Terminals, gekennzeichnet durch Σ, ist jede endliche, nichtleere Menge der unteilbaren Symbole. Z. B. das binäre Alphabet hat nur zwei Symbole. Dieser Satz wird im Allgemeinen als Σ dargestellt = (0, 1). Ein Wort oder eine Zeichenfolge über ein bestimmtes Alphabet ist eine endliche Abfolge von Symbolen des Alphabets. In mathematische Ausdrücke, ein typisches Wort, X, x geschrieben werden können = ein ₁, ₂, ₃, …, ein _k wo k ≥ 0, ein _ich ∊ Σ für 1 ≤ ich ≤ k. beachten Sie, dass bei k = 0, das Wort heißt das Wort null oder die leere Wort und ist gekennzeichnet durch Λ. Z. B. mit dem binäre Alphabet bilden wir können die Worte X = 0010 und y = 010. , Eine Wort, gegeben X, die Anzahl der Vorkommen der Symbole für ein bestimmtes Alphabet im Wort nennt man die Länge des Wortes und ist gekennzeichnet durch