This section will be about introducing grammars. I will present some intuition behind the idea of grammars and their similarities and differences with FAs. We will formalize this intuition and study a particular type of grammar related to FAs. You can find the notes related to this section here.

What is a grammar?

So far we have seen that FAs accept or recognize languages and that regular expressions denote or describe them. What about generation? Is there a mechanism that generates strings, rather than accepting them? Yes, absolutely! These objects are known as grammars and I introduce them in the following video.

Video on the way! Refer to slides for now.

Now that you have an intuition of what a grammar is supposed to do, I present a formal definition and give an example of a grammar \(G\) generating a language \(L(G) = L\).

Video on the way! Refer to slides for now.

Types of grammars

There are different types of grammars. Their type is determined by the form of their production rules. We study in detail regular and linear grammars here.

Regular grammars

Regular grammars have a strong connection with… regular languages! I present the definition of a regular grammar as will as some examples. You will only see the connection between regular grammars and regular languages in the next section.

Video on the way! Refer to slides for now.

Linear grammars

To prepare you for context-free grammars, I introduce an intermediate type of grammar known as linear grammars. Linear grammars are notoriously sneaky in the sense that they seem just like regular grammars, but have a subtlety that allows them to generate languages that are not regular. To be clear, we have not yet proved that regular grammars generate regular languages and only regular languages, this will come in the next section.

Video on the way! Refer to slides for now.

Regular grammars and regular languages

It turns out that regular grammars can only generate regular languages. Furthermore, all regular languages can be generated by a regular grammar. This means that the family of languages generated by regular grammars \(L_{REG-GRAM}\) is exactly the same as the family of languages accepted by FAs \(L_{FA}\). To prove this, we can show that any FA can be converted to a regular grammar and that any regular grammar can be converted to FA. In the following videos, I show conversion algorithms for right-linear grammars (and therefore not all regular grammars). I ask you to create conversion algorithms for left-linear grammars in the exercises.

Videos on the way! Refer to slides for now.

Exercises

Exercise. Provide a solution to the question on slide 8 in the tutorial slides.

Exercise. Provide a solution to the question on slide 14 in the tutorial slides.

Exercise (Slide 15). Are all linear grammars also regular? Are all regular grammars also linear?

Exercise. In the slides, we provide an algorithm to convert an NFA to a RLG and another to convert a RLG to an NFA. Provide two algorithms that do the same thing but this time for left-linear grammars. That is, 1. construct an algorithm \(A_1\) that converts an NFA \(N\) to a LLG grammar \(G\) and 2. an algorithm \(A_2\) that converts a LLG \(G\) to an NFA \(N\). In both 1. and 2., \(L(N) = L(G)\).