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

Question

Ich war auffrischen (nicht Hausaufgaben) auf einigen rechen Theorie und kam quer durch dieses Problem:

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

Jetzt weiß ich, eine Sprache, regelmäßig ist genau dann, wenn es von einem endlichen Automaten akzeptiert wird.

Und ich eine Sprache kennen, ist kontextfrei iff es von einem Keller akzeptiert Automat.

Aber ich bin nicht sicher, was Lösung ist.

Answer 1

Any DFA is equivalent to a PDA which happens to never push anything onto its stack, therefore all regular languages are also context-free. More formally:

A DFA is defined as a 5-tuple (Σ,S,s0,δ,F) consisting of the input alphabet, set of states, start state, transition table, and set of final (accepting) states.

A PDA is defined as a 7-tuple, including all the elements of a DFA, plus two additional parameters: Γ (the stack alphabet), and Z (the initial stack symbol). A PDA transition table is somewhat different from a DFA transition table: each transition can depend on both the input symbol and current stack symbol, and the transitions may push or pop from the stack.

So by introducing a dummy stack alphabet consisting of a single symbol, it's trivial (though somewhat annoying and long-winded to write out!) to map the DFA transition table (state, input) -> state to an equivalent PDA transition table (state, input, stack) -> (state, stack).

To complete the proof of a proper subset relationship: there exist languages which are context-free, but not regular, so the regular languages form a proper subset of the context-free languages. Example: the language of strings consisting of balanced parentheses.