Überschneidung des Kontexts frei mit regulären Sprachen

Der Schnittpunkt einer kontextfreien Sprache L mit einer regulären Sprache M soll immer kontextfrei sein. Ich habe den produktübergreifenden Konstruktionsnachweis verstanden, verstehe aber immer noch nicht, warum er kontextfrei, aber nicht regelmäßig ist.

Die durch eine solche Schnittmenge erzeugte Sprache enthält Zeichenfolgen, die sowohl von einem PDA als auch von einem DFA akzeptiert werden . Sollte es nicht eine reguläre Sprache sein, da es von einem DFA akzeptiert wird? Wenn die Schnittmenge regelmäßig ist, bedeutet dies auch, dass sie kontextfrei ist, da alle regulären Sprachen auch kontextfrei sind.

Kann mir jemand erklären, warum die durch eine solche Kreuzung erhaltene Sprache nicht regelmäßig ist?

regular-languages context-free finite-automata formal-grammars sanjeev mk
quelle

Betrachten Sie. * Als die reguläre Sprache und deren Schnittmenge mit einer kontextfreien.

AProgrammer

Es wären die Saiten des kontextfreien. Diese Zeichenfolgen werden jedoch auch von der regulären Sprache generiert, sodass es sich um eine kontextfreie Sprache handelt, die ebenfalls regulär ist.

Sanjeev mk

Die Sprache könnte regelmäßig sein. Aber normalerweise ist es nicht so. Denken Sie noch einmal an das Gegenbeispiel von AProgrammer. Es sollte wahrscheinlich die Antwort sein. Jede kontextfreie Sprache ist eine Teilmenge einer regulären Sprache. Es ist wahr, dass der Schnittpunkt der Sprachen CF und REG vom DFA von REG akzeptiert wird, aber es kommt auch darauf an, was abgelehnt wird.

Karolis Juodelė

cs.stackexchange.com/q/59886/755

@ DW Relevant, aber jemand hat es als Betrug vorgeschlagen, und das ist es nicht. Diese Frage stellt sich die Frage, warum die Kreuzung nicht immer regelmäßig ist. der andere fragt, warum die Kreuzung nicht immer unregelmäßig ist. Die spezielle Anordnung dieser Frage (die sich auf Zeichenfolgen bezieht, die sowohl von einem DFA als auch von einem PDA akzeptiert werden, sodass sie von einem DFA akzeptiert werden. Die Sprache ist also normal, oder?) Bedeutet, dass Antworten auf die andere Frage nicht angezeigt werden. t wirklich gut beantworten.

David Richerby

Antworten:

Wenn kontextfrei ist, gibt es einen PDA , der dies akzeptiert. Wenn regulär ist, gibt es einen DFA , der dies akzeptiert. Die Schnittmenge besteht aus den Wörtern, die durch und erkannt werden . $L$ $\mathscr{P}$ $M$ $\mathscr{F}$ $\mathscr{P}$ $\mathscr{F}$

Jedes Wort, das sich in der Schnittmenge befindet, wird von akzeptiert , aber nicht alle Wörter, die von akzeptiert werden, befinden sich in der Schnittmenge: nur diejenigen, die auch von akzeptiert werden . $\mathscr{F}$ $\mathscr{F}$ $\mathscr{P}$

Der produktübergreifende Beweis besteht aus der Konstruktion eines Automaten der die Mechanik von und und der nur Wörter akzeptiert, für die beide Seiten akzeptieren. Der produktübergreifende Automat ist ein PDA (und daher ist die erkannte Sprache kontextfrei) - intuitiv, da das produktübergreifende mit einem DFA mit Zuständen darin besteht, Kopien von und addieren. Pfeile zwischen den Zuständen in passenden , wo die DFA hat $\mathscr{P} \otimes \mathscr{F}$ $\mathscr{P}$ $\mathscr{F}$ $n$ $n$ $\mathscr{P}$ $(q,a,[q])$ $\mathscr{P}$ $a$ Pfeile. Das Ergebnis ist im Allgemeinen kein endlicher Automat (nicht einmal ein nicht deterministischer), da der Teil auf dem Stapel beruht und diese Abhängigkeit in im Allgemeinen nicht . $\mathscr{P}$ $\mathscr{P} \otimes \mathscr{F}$

Ein triviales Beispiel ist, dass regulär ist, und wenn kontextfrei, aber nicht regulär ist, dann ist kontextfrei, aber nicht regulär. $\mathscr{A}^*$ $L$ $L \cap \mathscr{A}^* = L$

Gilles 'SO - hör auf böse zu sein'
quelle

+1 Ich habe fast eine Antwort gepostet, die Ihrem letzten Satz entspricht. Ehrlich gesagt, scheint der Rest der Antwort unnötig. :)

Patrick87

"Hinzufügen von (q, a, [q]) Pfeilen zwischen übereinstimmenden Zuständen in P, in denen der DFA Pfeile hat". Kann nicht visualisieren, wie das Produkt PDA sein wird.

Uhr