Entscheidbarkeit der Sprachen von Grammatiken und Automaten

16

Beachten Sie, dass dies eine Frage ist, die sich auf das Studium in einem CS-Kurs an einer Universität bezieht. Es handelt sich NICHT um Hausaufgaben. Sie finden sie hier unter Prüfung Herbst 20112.

Hier sind die beiden Fragen, die ich aus einer früheren Prüfung sehe. Sie scheinen verwandt zu sein, der erste:

Lassen

FINITECFG={<G>∣G is a Context Free Grammar with |L(G)|<}

Beweisen Sie, dass eine entscheidbare Sprache ist. FINITECFG

und...

Lassen

FINITETM={<M>∣M is a Turing Machine with |L(M)|<}

Beweisen Sie, dass eine unentscheidbare Sprache ist. FINITETM

Ich bin ein bisschen verloren, wie ich diese Probleme angehen soll, aber ich habe ein paar Einsichten, von denen ich denke, dass sie in die richtige Richtung weisen. Das erste, was mir bewusst ist, ist, dass die Sprache , in derAREX

AREX={<R,w>∣R is a regular expression with wL(R)}

ist eine entscheidbare Sprache (Beweis ist in Michael Sipsers Berechnungstheorie , S. 168). Dieselbe Quelle belegt auch, dass eine kontextfreie Grammatik in einen regulären Ausdruck konvertiert werden kann und umgekehrt. Somit muss auch entscheidbar sein, da es in einen regulären Ausdruck konvertiert werden kann. Dies und die Tatsache , dass ist un -decidable, um dieses Problem zu zusammenzuhängen scheint.ACFGATM

Ich kann mir nur vorstellen, G für (nach der Konvertierung von G in einen regulären Ausdruck) und an Turing-Maschinen zu übergeben . Akzeptiere dann, wenn G dies tut, und lehne ab, wenn G dies nicht tut. Da unentscheidbar ist, wird dies niemals geschehen. Irgendwie habe ich das Gefühl, hier einen Fehler zu machen, bin mir aber nicht sicher, was es ist. Könnte mir bitte jemand dabei helfen?AREXATMATM

BrotherJack
quelle
5
"Eine kontextfreie Grammatik kann in einen regulären Ausdruck konvertiert werden und umgekehrt" Das ist nicht wahr (es sei denn, Sie interpretieren es als "es gibt eine CFG, die in einen regulären Ausdruck konvertiert werden kann" ", aber ich denke nicht, dass Sie das sind gemeint). Reguläre Grammatiken können in reguläre Ausdrücke konvertiert werden. Es gibt keinen Algorithmus zum Konvertieren von CFGs in reguläre Ausdrücke, da die meisten kontextfreien Sprachen (dh alle kontextfreien Sprachen, die nicht auch reguläre Sprachen sind) nicht mit einem regulären Ausdruck beschrieben werden können.
21.

Antworten:

9
  1. Konvertiere G in Chomsky Normal . Auf diese Weise wäre die einzige leere Ableitung das Startsymbol, das nirgendwo anders auftaucht. Wenn es also eine Produktion gibt, die sich möglicherweise selbst erzeugen kann, ist die Grammatik unendlich. Wenn keine solche Produktion existiert, kann jedes Symbol nur eine endliche Menge von Zeichenketten erzeugen, und dann ist die Grammatik endlich. Erstellen Sie also einen gerichteten Graphen, in dem jede Produktion ein Knoten ist und jedes Symbol in einer Produktion eine Kante ist, die auf dieses Symbol abzielt. Wenn der Graph einen gewissen Zyklus hat, ist das CFG unendlich, andernfalls nicht. Daher könnte eine Turing-Maschine für genau das konstruieren, und dann ist entscheidbar. F I N I T E C F GFINITECFGFINITECFG

  2. Angenommen, ist entscheidbar. Nehmen wir an, ist eine Turing-Maschine, die einen String als Eingabe hat und sich selbst als Eingabe für . Wenn true zurückgibt (dh akzeptiert nur eine endliche Sprache), akzeptiert die Eingabe, was zu einem Widerspruch führt, da die Eingabemenge unendlich ist (die Länge der Eingabe ist unbegrenzt, akzeptieren Sie daher alle möglichen Zeichenfolgen als Eingabemittel eine unendliche Menge von Zeichenfolgen akzeptieren). Wenn false zurückgibt (dh die Sprache von ist unendlich), lehnt die Eingabe ab, was bedeutet, dassFINITETMHFINITETMFINITETMHHFINITETMHHHDie Sprache von ist endlich, weil sie keine Eingaben akzeptiert (dh ihre Sprache ist leer), was ebenfalls zu einem Widerspruch führt. Auf diese Weise führt die Annahme, dass existiert, zu Widersprüchen, und diese Annahme basiert auf der Annahme, dass entscheidbar ist. Wir haben also im Widerspruch, dass nicht entscheidbar ist.HFINITETMFINITETM

Dieselbe Quelle belegt auch, dass eine kontextfreie Grammatik in einen regulären Ausdruck konvertiert werden kann und umgekehrt.

Ich bezweifle wirklich, dass Sipser das behaupten würde, Sie haben es wahrscheinlich falsch verstanden oder falsch verstanden. Dies würde bedeuten, dass kontextfreie Grammatiken genau die gleichen Sprachen wie rechtslineare Grammatiken erzeugen. Das ist falsch; Die erzeugten rechtslinearen Grammatiken sind eine geeignete Teilmenge der kontextfreien Grammatiken dp. Die Art und Weise, wie Sie versucht haben, die Fragen in regulären Sprachen zu beantworten, führt Sie jedoch zu nichts.

Wie Sie oben in meinen Beweisen sehen können, handelt es sich bei den beiden Fragen in der Tat um zwei sehr unterschiedliche, nicht miteinander verbundene Fragen. Es kommt einfach vor, dass sie ähnlich formuliert wurden.

Victor Stafusa
quelle
1
Ich habe ein Problem nach dem zweiten Beweis. OK, Sie übergeben H an G, ja? Wenn G true zurückgibt, als H endlich ist, ist dies sinnvoll. Ich erhalte jedoch keine unendliche Anzahl von Eingaben. Auf welche Eingaben beziehen Sie sich?
BrotherJack
1
@BrotherJack Der Eingang des kann beliebig lang sein, seine Länge ist unbegrenzt. Es kann sich um eine Zeichenfolge mit nur einem Symbol handeln oder um eine Eingabe mit einer Länge von einer Million Terabyte. Auf diese Weise sind die möglichen Eingaben für eine unendliche Menge, da wir sie beliebig groß machen können. HH
Victor Stafusa
1
IN ORDNUNG. Das scheint Sinn zu machen. Wäre es richtig, diese Eingabe als "eine mögliche Zeichenfolge in der Eingabesprache H" zu bezeichnen?
BrotherJack
1
@ BruderJack - Ich habe die Antwort bearbeitet, um diesen Punkt klarer zu machen.
Victor Stafusa
1
Hervorragende Erklärung! Vielen Dank für Ihre Zeit.
BrotherJack
2

Eine andere Möglichkeit, zu bestimmen, ist über das .FINITECFG

Das Pump-Lemma besagt, dass jede CFL eine Zahl (die aus der Grammatik berechnet werden kann oder zumindest eine Obergrenze davon kann leicht berechnet werden), so dass jedes das länger als ist, sein kann. gepumpt ".LNxLN

Dies bedeutet , dass wenn endlich ist, alle Worte kürzer als .LLN

Nun müssen nur noch Wörter mit einer Länge zwischen und überprüft werden . Wenn ein solches Wort existiert, ist unendlich. Es ist nicht allzu schwer zu erkennen, dass diese Aussage "genau dann" ist. Wenn Sie also kein Wort in diesem Bereich finden, ist endlich. Die Effizienz ist hier viel schlechter als die Antwort von Victor, aber es lehrt etwas über die Struktur von CFLs.2 N L LN2NLL

Ran G.
quelle