Skip to main content
replaced http://cs.stackexchange.com/ with https://cs.stackexchange.com/
Source Link

The usual proof is one with detour.

  1. Show that pushdown-automata accept exactly the context-free languages, the set of languages accepted by context-free grammars. (found in any text book on the matter)
  2. Note that Turing machines accept all recursive languages (by definition).
  3. Show that the context free languages are a proper subset of the recursive languages, for instance via Pumping LemmaPumping Lemma -- which is easily proven on with context-free grammars -- and $\{ww \mid w\in \{a,b\}^*\}$.

The usual proof is one with detour.

  1. Show that pushdown-automata accept exactly the context-free languages, the set of languages accepted by context-free grammars. (found in any text book on the matter)
  2. Note that Turing machines accept all recursive languages (by definition).
  3. Show that the context free languages are a proper subset of the recursive languages, for instance via Pumping Lemma -- which is easily proven on with context-free grammars -- and $\{ww \mid w\in \{a,b\}^*\}$.

The usual proof is one with detour.

  1. Show that pushdown-automata accept exactly the context-free languages, the set of languages accepted by context-free grammars. (found in any text book on the matter)
  2. Note that Turing machines accept all recursive languages (by definition).
  3. Show that the context free languages are a proper subset of the recursive languages, for instance via Pumping Lemma -- which is easily proven on with context-free grammars -- and $\{ww \mid w\in \{a,b\}^*\}$.
Source Link
Raphael
  • 72.9k
  • 30
  • 181
  • 393

The usual proof is one with detour.

  1. Show that pushdown-automata accept exactly the context-free languages, the set of languages accepted by context-free grammars. (found in any text book on the matter)
  2. Note that Turing machines accept all recursive languages (by definition).
  3. Show that the context free languages are a proper subset of the recursive languages, for instance via Pumping Lemma -- which is easily proven on with context-free grammars -- and $\{ww \mid w\in \{a,b\}^*\}$.