CODEWITHSUNDEEP
language-theorycomputation-theory
Robben_Ford_Fan_boy
Robben_Ford_Fan_boy

Reputation: 8720

Prove that the set of regular languages is a proper subset of the set of the context-free languages

I was brushing up (not homework)on some computation-theory and came accross this problem:

How can you prove that the set of regular languages is a proper subset of the set of the context-free languages.

Now I know a language is regular iff it is accepted by a finite automaton.

And I know a language is context-free iff it is accepted by a pushdown automaton.

But I'm not sure of what solution is.

Upvotes: 1

Views: 4026

Answers (1)

Jim Lewis
Jim Lewis

Reputation: 45045

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.

Upvotes: 2

Related Questions