FINITE-STATE-GRAMMAR

Gramática de estados finitos

(Recop.) Justo Fernández López

 

Vgl.:

Markov-Prozess / Automat / Stochastischer Prozess

 

Grammatik mit endlich vielen Zuständen / Regulär begrenzte Grammatik / finite state grammar

Die einfachsten von Chomsky diskutierten Grammatiken, die eine unendliche Menge von Sätzen mit Hilfe einer endlichen Menge von rekursiven Regeln über einem endlichen Wortschatz generieren können, sind die von ihm so genannten Grammatiken mit endlich vielen Zuständen (finite state grammars); sie gehen von der Annahme aus, dass Sätze durch eine Serie von Entscheidungen, die ‘von links nach rechts’ getroffen werden, generiert werden: d.h. nachdem das erste oder am meisten links stehende Element ausgewählt worden ist, hängt jede nachfolgende Wahl von den unmittelbar vorhergehenden Elementen ab.

Chomskys Beweis der Inadäquatheit der finite state grammar ist in ‘Syntactic Struktures’ zu finden. Er beruht auf der Tatsache, dass zwischen nicht benachbarten Wörtern Abhängigkeiten bestehen können und dass solche voneinander abhängigen Wörter ihrerseits wieder durch Sätze oder Satzglieder getrennt sein können, die noch ein Paar nichtbenachbarter, aber voneinander abhängiger Wörter enthalten. [...] Diese Grammatiken sind äquivalent zu endlichen Automaten hinsichtlich ihres Beschreibungsumfangs.“ 

[Abraham, Werner: Terminologie zur neueren Linguistik. 2 Bde., Tübingen: Niemeyer, 1988, S. 248]

Finite State Grammar [engl. ‘Grammatik mit endlich vielen Zuständen. - Auch: Reguläre Sprache, Finiter Automat]. Im Zweiten Weltkrieg zum Zwecke ökonomischer Nachrichtenverarbeitung entwickeltes Grammatikmodell. Es beruht auf der linearen Struktur der Sprache und dient der Erzeugung einer unendlichen Menge von Sätzen mit Hilfe einer endlichen Menge von Rekursiven Regeln über einem endlichen Wortschatz. Die Produktion von Sätzen verläuft von links nach rechts, d.h. die Wahl des am weitesten links stehenden Elements (= erstes Wort im Satz) determiniert die Wahlmöglichkeit für das unmittelbar folgende Element usf. Beginnt ein Satz mit jener, so kann das folgende Element aus der Menge der maskulinen Nomina ausgewählt werden, das nächste aus der Menge der Verben usf. N. Chomsky hat in "Syntactic Structures" (1957) nachgewiesen, dass F. S. G. deshalb zur Beschreibung natürlicher Sprachen nicht ausreichend sind, weil auch zwischen nicht unmittelbar aufeinander folgenden Elemente syntaktische Abhängigkeiten bestehen können; z. B. wenn ein Relativsatz eingeschoben wird. Zur Gegenposition vgl. P. A. Reich [1969]: „The finitness of natural language“. In: Language. Journal of the Linguistic Society of America, Baltimore, 45, S. 831-843].“ [Bußmann, S. 242-243]

Automat (Grammatik) mit endlich vielen Zuständen

[finite state automaton (grammar) / automate (grammaire) à états finis]

Ein Automat mit endlich vielen Zuständen ist ein primitives, auf der linearen Struktur der Sprache basierendes, kommunikationstheoretisch orientiertes Grammatikmodell, mit dem Sätze generiert werden in einer Serie sukzessiver Entscheidungen, wobei die Selektion eines Elements die (endliche Anzahl von) Wahlmöglichkeiten hinsichtlich unmittelbar folgender Elemente determiniert.

Der Mechanismus verfügt über einen Anfangszustand (initial state/état initial) und einen Endzustand (final state/état final). Bei jedem Übergang (transition/transition) von einem Zustand in einen anderen wird ein bestimmtes Symbol emitiert.

Die so produzierten Symbolsequenzen definieren eine Sprache, die man als ‘Sprache mit endlich vielen Zuständen’ (finite state language/langage à états finis) oder als ‘reguläre Sprache’ (regular language/langage régulier) bezeichnet.

Graphische Darstellungen von reguläre Sprachen generierenden Mechanismen heißen Zustandsdiagramme (state diagrams/diagrammes d’états).

Betrachten wir ein einfaches konkretes Beispiel (cf. auch Rohrer 1971, pp. 30f.):

 

 

Wenn a = der, b1 = Irre, b2 = Chef, c1 = grinst, c2 = schreit, d1 = unentwegt, d2 = selten, so sind mit dem eben skizzierten Automaten folgende Sätze generierbar:

 

 

Im Gegensatz zu Phrasenstrukturgrammatiken, die Sätze ‘vertikal’ (d.h. von oben nach unten) erzeugen, generiert eine Grammatik mit endlich vielen Zuständen Sätze ‘horizontal’ (d.h. der linearen Abfolge der chaîne parlée entsprechend von links nach rechts.

Automanten des vorgeführten Typs sind auch mit den von N. Chomsky entwickelten Konventionen darstellbar:

 

 

Chomsky erbrachte den Beweis, dass die Beschreibung sämtlicher syntaktischer Strukturen einer natürlichen Sprache mit einer Grammatik mit endlich vielen Zuständen grundsätzlich unmöglich ist (cf. Chomsky 1957, pp. 21ff.; Rohrer 1971, pp. 32ff.). P. A. Reich („The Finiteness of Natural Language“, Lg 45 (1969), 831-843) allerdings hält Chomskys Argumentation für zirkulär. Seiner Ansicht nach ist Englisch (und er vermutet: alle natürlichen Sprachen) durchaus mit einer ‘finite state grammar’ beschreibbar.“ 

[Welte, W.: Moderne Linguistik: Terminologie / Bibliographie, Bd. 1, S. 81-82]