Post-lecture update to Lecture 2

I’m not sure that I conveyed the narrative of this lecture very well. The lecture was to provide an introduction to regular grammars by viewing them as an alternative (and textual) way of describing the logic encoded in a deterministic finite automaton.

Initially, when talking about grammar production rules such as S -> a B I gave an incorrect description of how to think about this in terms of “strings that end up in a state”. I later corrected that.

To be clear, the idea is to think about for each state X (and not only the DFA’s start state) all the strings that you could accept starting from X. A transition T(S, a) = B in the DFA tells us that one way to accept a string (if we were allowed to start with state S) is to receive an *a* and then accept a string *starting from B. That leads to the grammar production rule S -> a B.

A key claim that we will rely on in Lecture 5 is that any DFA can be converted to a right-regular grammar that generates the language that the DFA accepts. This is the construction:

• The grammar’s alphabet is the same as the DFA’s.
• The grammar will contain one non-terminal symbol for each state in the DFA (and let’s assume the DFA state names are retained).
• For each transition T(X,a)=Y in the DFA:
  • Add a production rule X -> a Y to the grammar.
• For each accepting state X in the DFA:
  • Add a production rule X -> epsilon

Tedious checking that we won’t discuss.