CSC 341 (Fall 2021)

Reading: Context-free Grammar

Context-free Grammars

Now that we’ve discussed the properties of regular languages in detail, let’s move on to more powerful models of computation. Before we talk about models that capture the full generality of computation as we know it, we’ll take a pit stop to discuss an intermediate step on this path, the context-free languages. The models of the context-free languages add just enough expressiveness to overcome most of the immediate pitfalls we encountered in the languages that we previously showed were irregular.


For next class, please read about the model of computation for context-free languages that we will study: the context-free grammar.

Reading Problem (A CFG)

Give a context-free grammar \(G\) that recognizes language \(A = \{\, w \mid \text{ \( w \in \{\, 0, 1 \,\}^* \) starts and ends with the same symbol} \,\}\).