Reguläre Ausdrücke ohne Abwechslung

9

Ich habe mich gefragt, welche Sprachen durch Einschränkungen regulärer Ausdrücke erzeugt werden. Angenommen, alle Einschränkungen haben ein konstantes Symbol für jedes Element von und Verkettung. Dann können acht Klassen durch das Vorhandensein oder Fehlen von Komplement / Negation, Veränderung / Vereinigung und dem Kleene-Stern gebildet werden. (Ja, 'normale' reguläre Ausdrücke haben keinen C- Operator, aber hier ist es praktisch.)ΣC

Ausdrücke, die einen Wechsel ermöglichen, und der Kleene-Stern mit oder ohne Ergänzung (was ist eine kleine doppelt exponentielle Explosion unter Freunden?) Erzeugen die regulären Sprachen. Ausdrücke, die Abwechslung und Ergänzung erlauben, aber nicht den Kleene-Stern, erzeugen die sternfreien Sprachen. Ausdrücke, die eine Abwechslung zulassen, aber nicht ergänzen, oder der Kleene-Stern erzeugen die endlichen Sprachen.

Aber können interessante Sprachklassen ohne Wechsel generiert werden? Ohne einen der drei Operatoren kann nur ein einziges Wort generiert werden. Der Komplementoperator hilft hier nicht viel.

Mit nur dem Kleene-Stern ist die Klasse etwas interessant ... es ist nicht klar, ob sie schneller als normale Sprachen erkannt werden können. (Ist etwas nicht Triviales darüber bekannt?)

Bekommst du mit dem Kleene-Stern und der Ergänzung etwas Interessantes? Hat diese Klasse einen Namen?

Diese Frage wurde von der Frage zum regulären Ausdruck auf math.se inspiriert.

Charles
quelle
Was bedeutet Wechsel? es ist auch "Kleene".
Suresh Venkat
1
@Suresh Venkat: Union, logisches ODER, |, /, ∪.
Charles
Beachten Sie, dass die Klasse im ursprünglichen Kontext kein Komplement, sondern Rückreferenzen hat.
Peter Taylor
@ Peter Taylor: Richtig. Ich habe vor, eine Folgefrage zu Rückreferenzen zu stellen, aber ich dachte, es wäre zu viel, um in diese Frage zu passen.
Charles

Antworten:

12

Die Klasse der regulären Sprachen, die durch reguläre Ausdrücke ohne Vereinigung (und ohne Ergänzung) beschrieben werden kann, wird als vereinigungsfreie reguläre Sprachen (auch: reguläre Sternpunktsprachen ) bezeichnet. Diese Klasse von Sprachen hat offenbar in letzter Zeit einige Aufmerksamkeit erhalten:

Benedek Nagy: "Union-freie reguläre Sprachen und 1-Zyklus-freie-Pfad-Automaten", Publicationes Mathematicae 68 (1-2), 2006.

Sergey Afonin und Denis Golomazov: "Minimale unionsfreie Zerlegung regulärer Sprachen", Theorie und Anwendungen von Sprache und Automaten, Springer 2009.

Galina Jirásková und Tomás Masopust: "Komplexität in unionsfreien regulären Sprachen", Entwicklungen in der Sprachtheorie, Springer 2010.

Hermann Gruber
quelle
1
Nett. Ist etwas über die zusätzliche Kraft der Komplementation bekannt?
Charles
1
Kurze Nitpicky-Korrektur: Das Papier von Afonin und Golomazov erschien bei LATA 2009, nicht bei DLT 2009.
Dominik D. Freydenberger