×

Studies in abstract families of languages. (English) Zbl 0194.31402

Mem. Am. Math. Soc. 87, 51 p. (1969).
Diese Arbeit besteht aus drei Artikeln, die im folgenden einzeln besprochen werden. Die grundlegenden Definitionen und Erläuterungen finden sich in dem ersten der drei Artikel.
I. Abstract families of languages (S. Ginsburg und S. Greibach).
Im Unterschied zu der herkömmlichen Vorgehensweise, Sprachen durch Grammatiken oder erkennende Automaten einzuführen, werden hier Klassen von Sprachen (Teilmengen eines freien Monoids) untersucht, welche gewisse formale Abschlußeigenschaften besitzen. Eine Sprachklasse \(\mathcal L\) heißt abstract family of languages (AFL), wenn \(\mathcal L\) abgeschlossen ist gegenüber den Operationen Vereinigung, Produkt, Sternprodukt, inverser Homomorphismus, \(\varepsilon\)-freier Homomorphismus, und Durchschnitt mit regulären Mengen. Wenn \(\mathcal L\) zusätzlich gegenüber allen Homomorphismen abgeschlossen ist, dann heißt \(\mathcal L\) full AFL. Eine Reihe bekannter Sprachklassen sind full AFL (z. B. reguläre Mengen, kontext-freie Sprachen, rekursiv aufzählbare Mengen), andere dagegen sind nur AFL (z.B. \(\varepsilon\)-freie kontext-freie Sprachen, kontext-sensitive Sprachen). Es wird gezeigt, daß die obigen Abschlußeigenschaften der AFL (full AFL) eine Reihe weiterer Abschlußeigenschaften implizieren. Dies ist insofern interessant, weil man diese Abschlußeigenschaften dann nicht einzeln herleiten muß, wie dies bisher geschah. Es genügt, einige dieser Abschlußeigenschaften zu erwähnen. Z.B. enthält jede AFL alle \(\varepsilon\)-freien regulären Mengen. Jede AFL ist abgeschlossen gegenüber den \(\varepsilon\)-freien von endlichen Automaten erzeugten Relationen und somit insbesondere gegenüber \(\varepsilon\)-freien Abbildungen, welche von generalized sequential machines erzeugt werden und deren Inversen.
In einem weiteren Kapitel wird der sehr allgemeine Begriff “abstract family of acceptors” (AFA) eingeführt. Unter diese nicht-deterministischen Akzeptoren (erkennende Automaten) fallen u.a. die nicht-deterministischen push down, one way stack und one counter acceptors. Da im allgemeinen auch nicht-konstruktive Übergangsfunktionen in Akzeptoren zugelassen sind, sind diese Akzeptoren im allgemeinen keine Maschinen im intuitiven Sinn. Die von einer AFA erzeugte Sprachklasse ist stets eine full AFL. Daneben werden auch die von AFA erzeugten Sprachklassen untersucht bei Beschränkung der Größe des Hilfsspeichers in Abhängigkeit von der Länge des zu erkennenden Wortes, bzw. bei Zeitbeschränkung. Unter einschränkenden Voraussetzungen ergeben sich hier ebenfalls AFL. Interessant ist, daß die Gesamtheit der full AFL gerade durch die AFA charakterisiert werden. Eine AFL \(\mathcal L\) wird genau dann durch eine AFA erzeugt, wenn \(\mathcal L\) full AFL ist. Andererseits wird jede AFL, welche die Menge \(\{\varepsilon\}\) enthält von einer AFA mit Zeitbeschränkung erzeugt.
Im letzten Abschnitt werden Akzeptoren mit Ausgabestruktur (Transducers) in Zusammenhang mit dem Abschluß von AFL gegenüber der Durchschnittsbildung mit allen Sprachen einer gegebenen AFL behandelt.
II. Independence of AFL Operations (S. Greibach und J. Hopcroft).
Die Abschlußeigenschaften der AFL werden auf ihre Unabhängigkeit untersucht. Der Abschluß gegenüber Vereinigung, bzw. Multiplikation von Sprachen folgt jeweils aus der Abgeschlossenheit gegenüber den restlichen der sechs Abschlußeigenschaften der AFL. Im Falle, daß die AFL \(\mathcal L\) \(\varepsilon\)-frei ist, folgt die Abgeschlossenheit von \(\mathcal L\) gegenüber dem Durchschnitt mit regulären Mengen aus der Abgeschlossenheit gegenüber der Multiplikation, den \(\varepsilon\)-freien Homomorphismen und den Inversen von Homomorphismen. Alle unabhängigen Teilsysteme der AFL-Operationen werden angegeben. Ferner werden weitere Beziehungen zwischen Kombinationen der AFL-Operationen und einigen anderen Abschlußeigenschaften wie z. B. längenerhaltenden Homomorphismen sowie einigen speziellen Substitutionen untersucht.
III. Pre-AFL (S. Ginsburg, S. Greibach, J. Hopcroft).
Es werden Sprachklassen untersucht, deren Abschlußeigenschaften schwächer sind, als die der AFL. Zu zwei Sprachen \(L_1\subset X_1^*\), \(L_2\subset X_2^*\) und \(c\notin X_1\cup X_2\) heißt \(L_1cL_2\) ein markiertes Produkt. Die Iteration \((Lc)^*\) des markierten Produkts heißt der markierte Sternoperator. Eine Sprachklasse ist nach Definition Pre-AFL, wenn sie abgeschlossen gegenüber dem markierten Produkt, dem markierten Sternoperator, inversen Homomorphismen, Durchschnitt von regulären Mengen ist. Die Verff. geben Beispiele von Pre-AFL an und untersuchen die Beziehungen von Pre-AFL zu AFL. Z. B. ist der Abschluß von Pre-AFL unter \(\varepsilon\)-freien Homomorphismen eine AFL. Der Boolesche Abschluß einer AFL ist Pre-AFL.
Reviewer: C.-P. Schnorr

MSC:

68Q45 Formal languages and automata
Full Text: DOI