Regular Languages

Purpose

In this unit, we define and then study our first major language class, regular languages. This important class of languages and the results we derive play an important role in applications such as compilers, spelling checkers, and web browsers. Some of the tools we develop to study these languages such as finite automata play an important role in the modeling of a wide variety of systems such as digital logic controllers, vending machines, and biological processes.

Topics

Two Definitions of Regular Languages
Proof of Equivalence of Two Definitions
Properties of Regular Languages (1/28/97)
An Equivalence Class Characterization of Regular Languages (2/1/97)
The Pumping Lemma for Regular Languages (2/2/97)
Decision Problems and algorithms for Regular Languages (2/4/97)

Definition of Regular languages.

We will focus on two main definitions of the language class regular languages:
- A language L is regular if there exists an FSA M such that L(M) = L.
- A language L is regular if there exists a regular expression r such that L_r = L.

Equivalence of these two definitions.

Our first major theoretical result in this class is that these two definitions are equivalent.
- Stated another way, we can think of the above two definitions as defining two distinct language classes, one corresponding to regular expressions and one corresponding to FSAs.
- We will show that these two language classes are, in fact, identical.

How we prove this result
- What we need to do to.
  - Task 1: We need to show that the set of languages that can be described by a regular expression is a subset of the set of languages that can be recognized by an FSA.
  - Task 2: We need to show that the set of languages that can be recognized by an FSA is a subset of the set of languages that can be described by a regular expression.
    - Thus, these two sets are equal and the result follows.
    - To prove each of these two tasks, we utilize the generic element proof technique.
- High Level Overview (click on text links for details).
  - The following is a high level outline of the generic element proof for task 1.
    - Let L be an arbitrary regular language.
    - This means there exists a regular expression r such that L = L_r.
    - We show how r can be transformed into a finite state automaton M such that L(M) = L_r.
      - To accomplish this transformation, we introduce a third model of computation, the nondeterministic finite state automata (NFA) (chapter 5).
      - Task 1a: We will show that any regular expression r can be transformed into an NFA N such that L(N) = L_r (chapter 6).
      - Task 1b: We will then show that any NFA N can be transformed into an FSA M such that L(N) = L(M) (chapter 5).
    - By transitivity of =, L = L(M).
    - Thus, by definition of the language class LFSA, L is an element of LFSA.
  - The following is a high level outline of the generic element proof for task 2.
    - Let L be an arbitrary language in LFSA.
    - This means there exists an FSA M such that L(M) = L.
    - We show how M can be transformed into a regular expression r such that L(M) = L_r (chapter 6, you will not be responsible for the details of this transformation on any exam, but you will recreate this proof for your proof portfolios).
    - By transitivity of =, L = L_r.
    - Thus, by definition of the language class regular, L is a regular language.

Table of Contents (up one level)