CSci 301 Lecture Notes

Week Two, Tuesday: Regular Expressions

Example 1.14 Revisited

This is the NFA presented in example 1.14:


A four-state NFA with transition function table.

If we feed in the string "1100" it accepts. If we feed in the string "0011" it rejects. It will reject any string with a zero in the third place from the end, such as "1011". This is because the transition table, unlike that of a DFA, switches the NFA to a set of states. This can include the empty set, as shown for q4. Whenever a state transition is to the empty set, there is no further movement of the NFA. This is not explicitly discussed in the text, but can be inferred from subsequent examples.

Formal Definition of a Regular Expression

An expression R is regular if R is:

  1. a for some a in the alphabet,
  2. epsilon,
  3. {}
  4. R1 union R2 where R1 and R2 are regular expressions,
  5. R1 concatenated with R2,
  6. R1*.

Example 1.27.

Equivalence with Finite Automata

A regular language is one that is recognized by some finite automaton.

Theorem 1.28: A language is regular if and only if some regular expression describes it.

Proof --->
Lemma 1.29

Convert R into an NFA:

  1. R = a (proof by construction)
  2. R = epsilon (proof by construction)
  3. R = {} (proof by construction)
  4. R = R1 union R2 (proof by previous construction)
  5. R = R1 concatenated with R2 (proof by previous construction)
  6. R = R1* (proof by previous construction)

Examples 1.30 and 1.31.

Proof <---
Lemma 1.32

Definition 1.33: Generalized nondeterministic finite automaton.

For example, consider this DFA:


A three-state DFA that recognizes (0(00*1)*1)*.

First we convert it to an equivalent GNFA by adding new start and accept states:


A five-state equivalent GNFA.

Next we "rip out" a state and condense its function into a regular expression:


State q3 removed.

Then we rip out another state:


State q2 removed.

Finally, we rip out the last state and replace the whole machine with the regular expression that the original DFA recognized:


State q1 removed.

Email: Richard dot J dot Wagner at gmail dot com

notes02a.htm, this hand crafted HTML file created August 31, 1998.
Last updated May 14, 2011, by Rick Wagner. Copyright © 1998-2011, all rights reserved.