CSC 341: January 29, 2007

Instructor's notes for the class session

Definition 1.5 and the accompanying notation: $(Q, \Sigma, \delta: Q \times \Sigma \rightarrow Q, q_0 \in Q, F \subseteq Q)$

Designing finite automata: Using states to "remember" information obtained so far in the scanning of the input. Examples: Problems 1.34, 1.37, 1.32.

Closure properties: The class of regular languages is closed under complementation, under union, and under intersection.

Note added later: I subsequently refactored the DFA compiler, so in addition to the DrScheme module at the end of the link above, you'll also need two others, a collection of miscellaneous utilities and a basic set of constructors, selectors, and type predicates for DFAs.

Do some exercises from the end of chapter 1.

Describe a deterministic finite automaton that recognizes $\emptyset$ .
Describe a deterministic finite automaton that recognizes $\{\varepsilon\}$ .
Describe a deterministic finite automaton with the alphabet $\{\texttt{a}, \texttt{b}, \texttt{c}\}$ that accepts a string if, and only if, its component letters are in alphabetical order.
Prove that every finite language is regular.
Prove that, for every regular language $L$ , $\{w \mid w \textrm{\ is\ an\ initial\ substring\ of\ some\ member\ of\ } L\}$ is regular.

The DFA must accept nothing, so it starts in a reject state, and has one transition leading back to the reject state for all inputs.
This DFA must accept only the empty string. The DFA begins in an accept state, but reading any input causes it to transition to a reject state. The DFA remains in the reject state for any further input.
From the start state (which is also an accept state), the DFA reads the first character, and follows a transition to states x, y, and z on inputs "a", "b", and "c", respectively. Also, x, y and z are all accept states. x has three transitions: reading an "a" causes the DFA to remain in x, a "b" sends it to y, and a "c" sends it to z. On y, a transition on "a" leads to the reject state, a transition on "b" keeps the machine in y, and a transition on "c" sends the machine to z. If, on z, the machine reads a "c", it remains in z, otherwise it goes to a reject state.
If a language is finite, you can simply design a DFA that is tailored to recognize each individual string in the language.
Because $L$ is regular, there exists an NFA that recognizes $L$ . If we make every state in this NFA an accept state, then the new NFA will recognize the set of all initial substrings of members of $L$ .