CSci 301 Lecture Notes

Week One, Tuesday: Finite Automata

Controllers

Rear Swinging Door Opener:

This is a one-way door. People enter from the front.

            |          input signal
            | Neither  Front   Rear    Both
------------|---------------------------------------
     Closed | Closed   Open    Closed  Closed
     Open   | Closed   Open    Open    Open

State diagram for the swinging door controller.

Sliding Door Opener:

This is a two-way door. People can enter and exit.

            |          input signal
            | Neither  Front   Rear    Both
------------|---------------------------------------
     Closed | Closed   Open    Open    Open
     Open   | Closed   Open    Open    Open

State diagram for the swinging door controller.

Abstract Finite Automata

We want to abstract the idea of finite automata away from any specific applications. By divorcing state diagrams from controllers, we develop a purely mathematical concept.

A finite automaton can be represented by a state diagram that has a set of states, one a start state (input arrow), and zero, one, or several accept (final) states. Transitions from one state to another are represented by directed edges. The input is a string, and the output is either accept or reject.

Formal Definition

A finite automaton is a 5-tuple (Q, S, d, q₀, F), where

Q is a finite set called the states.
S (capital Sigma) is a finite set called the alphabet.
d (lowercase delta) is a mapping from Q x S to Q called the transition function.
q₀ is the start state, an element of Q.
F is a subset of Q called the set of accept states.

The transition function, delta, is described by a table:

        | 0    1
--------|-----------
     q1 | q1   q2
     q2 | q3   q2
     q3 | q2   q2

Although not necessary, a finite automaton might have a graphical representation:

State diagram for M1.

The graphical representation can help us visualize how the machine "moves" on its input.

Let A be the set of all strings that machine M accepts. Then A is the language of the machine M: L(M) = A. M recognizes A, or M accepts A. The term "recognize" is preferred to avoid confusion with the acceptance of a string by M. A machine (usually) accepts many strings, but recognizes only one language. What language does a machine recognize if it accepts no strings?

L(M1) = A = {w| w contains at least one 1 and an even number of 0s follow the last 1}

or M1 recognizes A.

Examples

State diagram for M5.

M5 accepts strings over {0, 1, 2, <Reset>} that sum to 0 modulo 3 or strings ending in <Reset>.

Formal Definition of Computation

Let M be a finite automaton. M accepts an input word w if there exists a sequence of states (r₀, r₁, ... , r_n) that satisfies the three conditions:

r₀ = q₀
d((r_i, w_i+1) = r_i+1 for i = 0, ... , n-1
r_n is an element of F

This definition says (informally) that there exists a sequence of states such that the input will cause a series of transitions through those states ending in an accept state.

M recongizes A if A = {w| M accepts w}. A language is regular if some finite automaton recognizes it.

Regular Operations

By definition:

Union of two languages: pull a word out of either set, A or B. This lumps all the strings into one language.

Concatenation: stick a word from A together with a word from B in all possible ways to get the strings in the new language.

Star: Concatenate any word from A as many times as you like. A* always includes epsilon (the empty string) as an element.

Theorems:

Regular languages are closed under union.

Regular languages are closed under concatenation.

Email: Richard dot J dot Wagner at gmail dot com