This section will be about context-free grammars and languages. It will also feature the notion of ambiguous context-free grammars. I will present the definition of context-free grammars and languages. I will also discuss what it means for them to be ambiguous. Lots of exercises about creating CFGs to generate languages can be found at the end of this section. You can find the notes related to this section here.

What is a context-free grammar?

In the previous section, we said that grammars are these language generators which produce the strings contained in a language. We said that the type of a grammar depends on what form its production rules can take. For linear grammars, we saw that this was any rule of the form \(V \rightarrow T^* \cdot (V \cup \{\lambda\}) \cdot T^*\) (slight abuse of notation here). We will see in the next video that context-free grammars are, in some sense, a “looser” version of linear grammars. This loosening of restrictions allows context-free grammars to generate many of the languages we previously saw were not regular such as \(a^nb^n\) and \(\{w w^R\}\). However, as we’ll discuss later on, CFGs still have some limitations in what they can generate. I encourage you to think of what languages can’t be generated by CFGs after finishing this section.

Video on the way! Refer to slides for now.

Derivation order and ambiguity

You might have noticed that there are grammars \(G\) that can generate the same string \(w\) in multiple different ways. This notion of having multiple ways of generating strings is formalized by introducing the concepts of derivation order and ambiguity. Another closely related concept is that of parse trees.

Videos on the way! Refer to slides for now.

Exercises

Exercise. Which of the following string(s) can be generated by the following grammar \(G = (\{S, A, B\}, \{a, b\}, S, P)\), where \(P\) is \begin{align*} S & \rightarrow AaaB|aaB \\ A & \rightarrow AB \\ B & \rightarrow aba|S \\ \end{align*}
  • \(aabb\)
  • \(aaba\)
  • \(aaaba\)
  • \(baba\)

Exercise. Give a grammar \(G\) that generates the language \(L = \{a^nb^kc^l : l = 2k + n, k,l,n \geq 0\}\). Is this language context-free?

Exercise. Give a context-free grammar \(G\) that generates the language \(L = \{a^nb^m : m - n = 1\}\).

Exercise. Give a context-free grammar \(G\) that generates the language \(L = \{uv^Rwvu : u,v,w \in \{a,b\}^*, |u| = 2, |w| = 3 \}\).

Exercise. Give a context-free grammar \(G\) that generates the language \(L = \{uawb : u,w \in \{a,b\}^*, |u| = |w| \}\).

Exercise. Provide a solution to the exercise on slide 12 of the tutorial slides.

Exercise. We did not discuss the notion of ambiguity in the "Intro to Grammars" section. There might be a good reason for that. Can regular grammars be ambiguous? Prove your claim. (Check out the previous section if you've forgotten or don't know what a regular grammar is.)

Exercise. Provide a solution to the exercise on slide 15 of the tutorial slides.