Unit-2 of Mathematical Foundations or the Theory of Computation introduces Context-Free (CF) Languages and their processors, Pushdown Automata (PDA). PDA are more powerful than Finite Automata (FA). Basically, PDA are created by adding a stack (or pushdown store)to a Non-deterministic FA. Every CF language is defined by a CF Grammar (CFG). Every regular language is CF; but every CFL is not regular. CFLs are a subset of recursively enumerable languages. The relationship of CF languages with other languages is shown in the Chomsky Hierarchy

The notes on Mathematical Foundations or the Theory of Computation presented in this unit and others are mainly based on Hopcroft, J., Motwani, R. & Ullman, J. (2007), Introduction to Automata Theory, Languages, and Computation, 3rd Edition, Addison Wesley and Daniel Cohen, (1997), Introduction to Computer Theory, 2nd Edition, John Wiley & Sons, and Sipser, M. (2012) Introduction to the Theory of Computation, Cengage Learning, 3rd edition. Revealing examples are taken from these sources in order to explain mathematical models of computation.     Please click here to go back to the Mathematical Foundations home page .