On the proof of a theorem by chomsky—hopcroft—ullman

Abstract

In the present note we give a proof of the theorem expressing the fact that the push-down automata accept exactly the context-free languages. The formulation of the proof (which follows the outline of the classical proof by Hopcroft and Ullman) aims at displaying some of the peculiarities of the situation. An example of the use of the constructive proof is given.

Keywords:

• Push-down automata
• context-free language

C.R. Categories:

• 5.22
• 5.23