Context-Free Languages

In this part of the course we focus on studying context-free languages, which are languages generated by context-free grammars or accepted by pushdown automata.

Context-free languages are more powerful than regular languages and are widely used in programming language design and implementation, as well as in natural language processing.

Goals

At the end of this part of the course you should be able to:

• given a language, either use context-free grammars to describe it or to prove that it is not context-free;
• understand the concept of ambiguity in context-free grammars and strategies to eliminate it (when possible);
• convert between context-free grammars and pushdown automata;
• given a context-free grammar, either use it to generate words in the language or to parse words in the language.

References

The main reference for this part of the course is (Sipser 2013, chap. 2).

Sipser, Michael. 2013. Introduction to the Theory of Computation. 3rd ed. Cengage Learning.