Beweisen Sie, dass die Menge der regulären Sprachen ist eine echte Teilmenge der Menge der kontextfreien Sprachen

Question

I (Hausaufgaben nicht) wurde auffrischen auf einige rechen Theorie und kam quer durch dieses Problem:

Wie kann man beweisen dass die Menge der regulären Sprachen eine richtige Teilmenge der Menge der kontextfreien Sprachen ist.

Jetzt weiß ich, dass eine Sprache regelmäßig ist, wenn sie von einem endlichen Automaten akzeptiert wird.

Und ich weiß, eine Sprache ist kontextfrei, wenn es von einem Pushdown Automaten akzeptiert wird.

Aber ich bin mir nicht sicher, welche Lösung ist.

Answer 1

Jedes DFA ist äquivalent zu einem PDA, der niemals etwas auf seinen Stack verschiebt, daher sind alle regulären Sprachen ebenfalls kontextfrei. Formaler:

Ein DFA ist definiert als ein 5-Tupel (Σ, S, s0, δ, F) bestehend aus dem Eingabealphabet, Satz von Zuständen, Startzustand, Übergangstabelle und Satz von final (accepting) Zustände.

Ein PDA ist als 7-Tupel definiert, einschließlich aller Elemente eines DFA, plus zwei zusätzliche Parameter: Γ (das Stapelalphabet) und Z (das ursprüngliche Stapelsymbol). Eine PDA-Übergangstabelle unterscheidet sich etwas von einer DFA-Übergangstabelle: jeder Übergang kann sowohl vom Eingangssymbol als auch vom aktuellen Stapelsymbol abhängig sein, und die Übergänge können vom Stapel schieben oder vom Stapel springen.

also durch ein Dummy-Stack-Alphabet aus einem einzigen Symbol bestehend einzuführen, ist es trivial ist (wenn auch etwas ärgerlich und weitschweifiger zu schreiben!), Um die Übergangstabelle DFA (state, input, stack) -> (state, stack) (state, input) -> state zu einer äquivalenten PDA Übergangstabelle abzuzubilden.

Um den Beweis einer richtigen Teilmengenbeziehung zu vervollständigen: Es gibt Sprachen, die kontextfrei sind, aber nicht regulär, so dass die regulären Sprachen eine richtige Teilmenge der kontextfreien Sprachen bilden. Beispiel: Die Sprache der Strings besteht aus ausgeglichenen Klammern.