Eine ausreichende und notwendige Bedingung für die Regelmäßigkeit einer Sprache

Welche der folgenden Aussagen ist korrekt?

1. Es bestehen ausreichende und notwendige Bedingungen für die Regelmäßigkeit einer Sprache, die jedoch noch nicht entdeckt wurden.

2. Es gibt keine ausreichende und notwendige Bedingung für die Regelmäßigkeit einer Sprache.

3. Das Pumplemma ist eine notwendige Bedingung für die Nichtregelmäßigkeit einer Sprache.

4. Das Pumplemma ist eine ausreichende Bedingung für die Nichtregelmäßigkeit einer Sprache.

Ich weiß, dass # (4) richtig und # (3) falsch ist, weil "die Umkehrung dieser Aussage nicht wahr ist: Eine Sprache, die diese Bedingungen erfüllt, ist möglicherweise immer noch nicht regulär", aber was kann über (1) und gesagt werden? (2)?

Hier sind einige notwendige und ausreichende Bedingungen, damit eine Sprache regelmäßig ist.

Satz. Lassen . Die folgenden Bedingungen sind gleichwertig:$L\subseteq\Sigma^*$

• $L$ wird durch einen regulären Ausdruck (dh die Definition der regulären Sprache) erzeugt.
• wird von einem nichtdeterministischen endlichen Automaten (Kleene)erkannt$L$ ) .
• wird von einem nichtdeterministischen endlichen Automaten ohne ε erkannt$L$$\varepsilon$ Übergänge .
• wird von einem deterministischen endlichen Automaten (Scott und Rabin)erkannt.$L$
• wird durch eine Grammatik erzeugt ( N , Σ , P , S ) , wobei N eine endliche Teilmenge von Σ * (Frazier und Seite).$L$$(N,\Sigma,P,S)$$N$$\Sigma^*$
• wird durch eine linke (bzw. rechte) reguläre kontextfreie Grammatik erzeugt.$L$
• Der Index der Nerode-Beziehung ist endlich (Anil Nerode, Lineare Automatentransformationen , 1958). Dies ist weithin (und fälschlicherweise) als Myhill-Nerode-Theorem bekannt. ≡ L ist die Beziehung, die zum Erstellen des minimalen DFA einer regulären Sprache verwendet wird.$\equiv_L$$\equiv_L$
• Der Index der Myhill-Beziehung ist endlich (John Myhill, Finite Automata and the Representation of Events , 1957). ∼ L ist die Beziehung, die zum Aufbau des syntaktischen Monoids einer beliebigen Sprache verwendet wird.$\sim_L$$\sim_L$
• Das syntaktische Monoid von ist endlich (Folge von Myhills Ergebnis). Wir stellen hier fest, dass das syntaktische Monoid nicht nur durch die Verwendung der Beziehung ∼ L definiert werden kann, sondern auch als minimales Monoid (in der Größe) definiert werden kann, das L als Vorbild eines Homomorphismus erkennt .$L$$\sim_L$$L$
• kann von einer schreibgeschützten Turingmaschine erkannt werden (trivial).$L$
• kann durch eine Formel in der monadischen Logik zweiter Ordnung über Strings (Büchi) definiert werden.$L$

Wenn eine Sprache die Bedingungen des Pump-Lemmas für reguläre Sprachen nicht erfüllt , ist sie nicht regulär. Dies bedeutet, dass das Pumpen von Lemma eine ausreichende Bedingung für die Nichtregelmäßigkeit einer Sprache ist.

Zusammenfassend sind die Aussagen 1, 2 und 3 falsch, während die Aussage 4 wahr ist, wie Sie erwähnt haben.

Es ist ausreichend (und notwendig), das Vorhandensein eines DFA, einer NFA oder eines regulären Ausdrucks nachzuweisen, um zu beweisen, dass eine Sprache regulär ist, was (1) und (2) widerlegt. Um zu zeigen, dass eine Sprache nicht regulär ist, muss gezeigt werden, dass kein DFA, NFA oder regulärer Ausdruck vorhanden ist.

Das Pump-Lemma ist ein nützliches Werkzeug, um (möglicherweise im Widerspruch) zu zeigen, dass eine Sprache nicht regulär ist, indem gezeigt wird, dass kein DFA existiert.

Die Bedingung 'es gibt einen regulären Ausdruck, der genau erzeugt ' ist eine notwendige und ausreichende Bedingung für die Regelmäßigkeit einer Sprache L , da sie ihre Definition ist.$L$$L$

Diese Bedingung macht es jedoch nicht gerade einfach, die Unregelmäßigkeit einer Sprache zu beweisen. Mir sind keine leicht zu überprüfenden Bedingungen bekannt, die immer beweisen, dass eine nicht reguläre Sprache nicht regelmäßig ist.

Es gibt zwei weitere "Tests", die die Nicht-Regelmäßigkeit einer Sprache beweisen können (obwohl sie möglicherweise nicht funktionieren): Sie können versuchen, eine reguläre Sprache so anzugeben, dass ihre Vereinigung / Schnittmenge / Differenz / Verkettung / Quotient nicht regelmäßig ist ( Es gibt weitere Operationen wie diese), und Sie können versuchen, die Anzahl der generierten Wörter zu zählen und zu überprüfen, ob sie dem Ausdruck für die Anzahl der Wörter in einer regulären Sprache widersprechen (wie auf der von Ihnen verlinkten Wikipedia-Seite zu finden).

Es gibt diese wunderbare Verbindung zwischen formaler Sprachtheorie und formalen Potenzreihen, die von Chomsky und Schützenberger [CS63] bewiesen wurden . In der Form in [SS78] Kap. II, Satz 5.1

Sei eine reguläre Sprache und K ein Semiring. Dann c h a r ( L $L$$\mathbb{K}$$\mathrm{char}(L)$ ist ,$\mathbb{K}$ -rationalen.

Wenn Sie sich also die charakteristische Reihe c h a r ansehen$\mathrm{char}(L)$

[SS78] Arto Salomaa und Matti Soittola. Automatentheoretische Aspekte formaler Potenzreihen. Springer-Verlag, New York, 1978.

[CS63] Noam Chomsky und Marcel P. Schützenberger. Die algebraische Theorie kontextfreier Sprachen. In P. Braffort und D. Hirschberg, Herausgeber, Computerprogrammierung und formale Sprachen, Seiten 118–161. Nordholland, 1963.

$I_{L}$$x$$y$$x I_{L} y$

1. $z_{x}$$xz_{x} \in L$$yz_{x} \in L$ .
2. $z_{y}$$yz_{y} \in L$$xz_{y} \in L$ .

Intuitiv entspricht dies der Vorstellung, dass es in der Zustandsmaschine endlich viele Zustände gibt. In der Tat ist die Anzahl der verschiedenen Äquivalenzklassen unter der$I_{L}$$L$ .

Myhill-Nerode ist besonders nützlich, weil Sie positive Beweise (die Sprache ist regulär) und negative Beweise (die Sprache ist nicht regelmäßig) unter Verwendung des gleichen Rahmens erstellen können: der Beziehung $I_{L}$