Wie kann man beweisen, dass eine Sprache normal ist?

48

Es gibt viele Methoden , um zu beweisen , dass eine Sprache nicht regulär ist , aber was muss ich tun, um zu beweisen , dass einige Sprache ist regelmäßig?

Wenn mir zum Beispiel gegeben wird, dass regelmäßig ist, wie kann ich dann beweisen, dass das folgende regelmäßig ist?L 'LL

L:={wL:uv=w for uΣL and vΣ+}

Kann ich einen nicht deterministischen endlichen Automaten zeichnen, um dies zu beweisen?

Corium
quelle
1
Es gibt einen Tippfehler in der Definition Ihres , bitte bearbeiten, um ihn zu beheben. L
Ran G.
2
"Zeichnen" ist kein Beweis; Sie müssen eine NFA angeben und nachweisen, dass diese die Sprache akzeptiert.
Raphael
Ich denke, die Sprachdefinition macht immer noch keinen Sinn ...
hugomg
2
Auf jeden Fall ist die spezifische Sprache irrelevant, wenn die Frage lautet: "Kann ich eine NFA zeichnen, um zu beweisen, dass sie regulär ist?". @corium, können wir die Frage so bearbeiten, dass sie die allgemeinere Frage widerspiegelt: "Wie kann man beweisen, dass ein bestimmtes regulär ist?" L
Ran G.

Antworten:

48

Ja, wenn Sie eine der folgenden Möglichkeiten haben:

für eine Sprache ist regulär. Es gibt äquivalentere Modelle , die oben genannten sind jedoch die am häufigsten verwendeten.LLL

Es gibt auch nützliche Eigenschaften außerhalb der "rechnerischen" Welt. ist auch regelmäßig, wennL

  • es ist endlich,
  • Sie können es erstellen, indem Sie bestimmte Vorgänge für reguläre Sprachen ausführen. Diese Vorgänge sind für reguläre Sprachen geschlossen , z

    • Überschneidung,
    • ergänzen,
    • Homomorphismus,
    • Umkehrung,
    • linker oder rechter Quotient,
    • regelmäßige Transduktion

    und mehr oder

  • unter Verwendung des Myhill-Nerode-Theorems, wenn die Anzahl der Äquivalenzklassen für endlich ist.L

Im vorliegenden Beispiel haben wir eine (reguläre) Sprache als Grundlage und möchten etwas über eine davon abgeleitete Sprache sagen . Wenn wir dem ersten Ansatz folgen - konstruieren Sie ein geeignetes Modell für -, können wir jedes äquivalente Modell für annehmen, das wir uns wünschen. es wird natürlich abstrakt bleiben, da unbekannt ist. Im zweiten Ansatz können wir direkt verwenden und Schließungseigenschaften darauf anwenden, um eine Beschreibung für .L ' L ' L L L L 'LLLLLLL

Ran G.
quelle
4
Es kann auch erwähnenswert sein, dass es ausreicht, zu beweisen, dass eine Sprache endlich ist, um zu beweisen, dass sie regelmäßig ist. Dies kann insbesondere bei nicht konstruktiven Einzelfallnachweisen sinnvoll sein.
Patrick87
2
reguläre Ausdrücke, wie sie in Programmiersprachen vorkommen, können viel mehr als normale Sprachen. Sie müssten sich auf "klassische" Konstrukte beschränken.
David Lewis
4
@DavidLewis: Auf dieser Site können Sie davon ausgehen, dass mit "regulärem Ausdruck" der klassische Begriff gemeint ist.
Raphael
@DavidLewis Ich stimme zu, man sollte "regexp" im Kontext der Theorie vermeiden, um Verwirrung zu vermeiden.
Raphael
Beachten Sie, dass Sie für die ersten vier Aufzählungszeichen einen Beweis benötigen, aus dem hervorgeht, dass Ihre Darstellung tatsächlich korrekt ist.
Raphael
10

Grundlegende Methoden

  1. Endliche Automaten (möglicherweise nicht deterministisch, mit leeren Übergängen).
  2. Reguläre Ausdrücke.
  3. Rechte (oder Linke, aber nicht beide) lineare Gleichungen, wie wobei K und L regelmäßig sind.X=KX+LKL
  4. Regelmäßige (Typ 3) Grammatik.
  5. Operationen, bei denen reguläre Sprachen erhalten bleiben (Boolesche Operationen, Produkt, Stern, Mischen, Morphismen, Inversen von Morphismen, Umkehrung usw.)
  6. Erkannt durch ein endliches Monoid.

Logische Methoden (oft bei der formalen Verifikation verwendet)

  1. Monadische Logik zweiter Ordnung (Satz von Büchi).
  2. Lineare zeitliche Logik (Satz von Kamp).
  3. Rabins Baumsatz (monadische Logik zweiter Ordnung mit zwei Nachfolgern). Sehr kraftvoll.

Fortgeschrittene Methoden

  1. Hoch entwickelte pumpende Deckspelzen. Siehe zum Beispiel
    [1] J. Jaffe, Ein notwendiges und ausreichendes Pumplemma für reguläre Sprachen, Sigact News - SIGACT 10 (1978) 48-49.
    [2] A. Ehrenfeucht, R. Parikh und G. Rozenberg, Pumping Lemmas for Regular Sets, SIAM J. Comput. 10 (1981), 536 & ndash; 541.
    [3] S. Varricchio, Eine Pumpbedingung für reguläre Sets, SIAM J. Comput. 26 (1997) 764-771.

  2. Na quasi Bestellungen. Siehe
    [4] W. Bucher, A. Ehrenfeucht, D. Haussler, Über die Gesamtzahl der durch Ableitungsbeziehungen erzeugten Regulatoren, Theor. Comput. Sci. 40 (1985) 131–148.
    [5] M. Kunz, Regelmäßige Lösungen von Sprachungleichheiten und Brunnenquasi-Ordnungen .

  3. N

  4. Algebraische Methoden, die auf Transduktionen basieren (siehe auch Operationen zum Beibehalten regulärer Sprachen ).

J.-E. Stift
quelle
4

Die Antwort von Ran G. enthält eine ziemlich ausführliche Auflistung der äquivalenten Modelle, mit denen reguläre Sprachen angegeben werden können (und die Liste geht weiter, Zwei-Wege-Automaten, MSO-Logik, die jedoch über den Link unter "äquivalentere Modelle" abgedeckt wird '). Und wie Raphael betont, brauchen wir ein Argument, um das Publikum davon zu überzeugen, dass die gewählte Darstellung tatsächlich richtig ist.

LLLL

L=(ΣL)Σ

LL

Hendrik Jan
quelle
1
L
@Raphael Entschuldigung, ich habe meinen Standpunkt klargestellt. Die früheren Antworten scheinen zu erklären, dass wir eine Beschreibung der Sprache erstellen können (als Automat, Operationen usw.). Genau. Die Frage scheint jedoch nach den Verschlusseigenschaften zu sein, siehe das angegebene Beispiel. Dieser Punkt fehlt mir in den anderen Antworten: Um eine Abschlusseigenschaft zu beweisen, gehen Sie davon aus, dass Sie eine Beschreibung haben, und konstruieren Sie eine neue.
Hendrik Jan
1
L
1
LLLLLLLLL
1
Oh ok. Eigentlich würde ich bearbeiten eher die Frage, und entfernen Sie den „zum Beispiel“ Teil, wodurch die Frage allgemeiner, und eine Referenz für zukünftige ähnliche Fragen .. (:
Ran G.
4

sks<some property>kk

Rick Decker
quelle
4

L1SL2={x1y1xnynΣ:x1xnL1,y1ynL2}
Ai=Σ,Qi,Fi,δi,q0iLii=1,2Σ,Q,F,δ,q0
  • Q1×Q2×{1,2}xiyi
  • q0=q01,q02,1
  • F=F1×F2×{1}
  • δ(q1,q2,1,σ)=δ1(q1,σ),q2,2δ(q1,q2,2,σ)=q1,δ2(q2,σ),1

LR={wR:wΣ}.
(w1wn)R=wnw1LΣ,Q,F,δ,q0Σ,Q,F,δ,q0
  • Q=Q{q0}
  • q0
  • q0
  • δ(q0,ϵ)=FqQσΣδ(q,σ)={q:δ(q,σ)=q}

q0


R(L)={yxΣ:xyL}.
LΣ,Q,F,δ,q0Σ,Q,F,δ,q0q=δ(q0,x)δ(q,y)Fδ(q0,x)=qyx
  • Q={q0}Q×Q×{1,2}q0q,qcurr,sqqcurrsyx
  • F={q,q,2:qQ}δ(q0,x)=q
  • δ(q0,ϵ)={q,q,1:qQ}q
  • δ(q,qcurr,s,σ)=q,δ(qcurr,σ),sq,qcurrQs{1,2}
  • δ(q,qf,1,ϵ)=q,q0,2qQqfFyxy

Ek(L)={xΣ: there exists yL whose edit distance from x is at most k}.
Σ,Q,F,δ,q0LΣ,Q,F,δ,q0Ek(L)
  • Q=Q×{0,,k}
  • q0=q0,0
  • F=F×{0,,k}
  • q,σ,iδ(q,σ),iδ(q,i,σ)
  • q,i+1δ(q,i,σ)q,σ,ii<k
  • δ(q,σ),i+1δ(q,i,ϵ)q,σ,ii<k
  • δ(q,σ),i+1δ(q,i,τ)q,σ,τ,ii<k
Yuval Filmus
quelle
3

Eine Sprache ist normal, wenn Sie einen Scanner schreiben können, der über beliebige Zeichenfolgen entscheidet, ob diese zur Sprache gehören oder nicht. Dabei wird nicht mehr als eine feste Menge an Speicher benötigt, dh die Erkennung kann im O (1) -Raum erfolgen.

reinierpost
quelle
O (1) Raum, meinst du? In jedem Fall wird dies dadurch abgedeckt, dass DFA ausreicht; es mag sich lohnen, diese äquivalenz bei der programmierung ausdrücklich zu erwähnen.
Raphael
Ja, es ist nur eine andere Perspektive.
Reinierpost
3

Die Transformation regulärer Ausdrücke ist eine Möglichkeit, das Schließen unter bestimmten Operationen zu beweisen. Die zwei einfachsten Beispiele sind der Verschluss unter Umkehrung und der Verschluss unter Homomorphismus .

rLLRL

  • ϵR=ϵσR=σR=
  • (r1+r2)R=(r1R+r2R)(r)R=(rR)(r1r2)R=r2Rr1R

(r1r2)R=r2Rr1R(01)R=10rRLR

h:ΣΔrLh(L)σrh(σ)

Yuval Filmus
quelle
0

Eine andere Möglichkeit besteht darin, die Sprache mithilfe von Operationen aufzubauen, bei denen Sie wissen, dass sie geschlossen sind. Dies ist eine Erweiterung zum Anzeigen eines regulären Ausdrucks, da Sie über viele weitere Operationen verfügen (Umkehren der Zeichenfolge, Komplementieren, Schneiden, Herausschneiden eines Teils, Beibehalten eines Teils, Homomorphismen und inverse Homomorphismen, ...).

vonbrand
quelle
2
Das ist bereits in Rans Antwort erwähnt.
Raphael