Finite Automata and Regular Languages

• Finite Automata represent computers that have a very small amount of memory, encapsulated using states.
• They are computationally equivalent to Regular Languages—all regular languages can be expressed with a Finite Automata, and all Finite Automata can compute Regular Languages

Finite Automaton §

DFA §

• A finite automaton is a five tuple consisting of

  • A finite set of states
  • A finite set of input symbols called the alphabet
  • A transition function
  • An initial state
  • A set of accept states .

• Let be a string over the alphabet .

  The automaton accepts the string if a sequence of states satisfying the following conditions

  2. for
  3. .

• The set of all strings over that is accepted by finite automaton is the language of , and that recognizes , and that .

Transducer §

• A finite transducer is a five tuple consisting of:

  • A finite set of states
  • An alphabet of input symbols
  • An alphabet of output symbols
  • A transition function
  • An initial state .

• The transducer behaves like a regular automaton, except after each transition, it outputs a symbol. (for the Mealy variant). It can be modified to a Moore machine if we have every output be on the state.

• A general state transducer (GST) extends the transducer but allows for more than one output symbol on a transition function

Two-Way DFA §

• A two-way DFA is an tuple where

  • is the finite non-empty set of states.
  • is the alphabet.
  • is the left end marker
  • is the right end marker.
  • is the start state.
  • is the accept state.
  • is the reject state.

• That is, a transition is possible when reaching either end of the input word.

• For all symbols

  That is, once the automaton reaches the accept or reject state, it stays there forever, and the pointer goes tot he right most pointer and cycles there infinitely.

Regular Languages §

• A regular language is a language that is recognized by a finite automaton .
• We may define regular operations

  • A union is defined as

  • A concatenation is defined as

  • A star operator is defined as
• is a regular expression if is built from regular operations or symbols in the alphabet. That is, is:
  • where and are regular expressions
  • where and are regular expressions
  • where is a regular expression.
• Theorem: Closure properties: ¹
  • Sipser 1.45: If and are regular languages, then so is .
  • Sipser 1.47: If and are regular languages, then so is .
  • Sipser 1.49: If is a regular language, then so is .
  • Sipser e1.31: If is a regular language, then so is its reversal

• Sipser 1.54: A language is regular if and only if some regular expression describes it.

Regular Grammars §

• A right linear grammar is a formal grammar in which all production rules in are of the following forms
• A left linear grammar has all production rules of the form

Nondeterminism §

NFA §

• A deterministic machine necessitates that the next state is exactly determined by the input symbol and previous states. Otherwise, the machine is nondeterministic.

  • In an NFA, a state may have zero, one, or many exiting arrows. We also allow a transition with input symbol .
  • Compared to a DFA, an NFA has a transition function defined by

• Every deterministic machine is nondeterministic.

• Sipser 1.39: Every NFA has an equivalent DFA.

• Computation is done in a similar way to DFAs except:

  • If more than one transition is possible, split computation into parallel branches, taking each transition.
  • If no transition is possible, the machine dies.
  • If is encountered, we may transition to the outgoing state or stay in the current state.
  • If any computation branch ends on a final state, the NFA accepts the string.

GNFA §

• A generalized NFA is an NFA where transition arrows may have any regular expressions as labels instead of only members of the alphabet such that:

  • The start state has outgoing transitions to all states and no incoming transitions.
  • The accept state has incoming transitions from all states and no outgoing transitions.
  • Except for the start and accept states, One arrow goes from every state to every other state and also from each state to itself

• GNFAs are used to convert a DFA into a regular expression. This is done as follows ²:

  • Let be a GNFA

  • Let

  • If , return the regular expression in the transition.

  • If , select that is not or .

    Let be the GNFA where

    and for any non-accept state and non-start state we have that

    Where

    Repeat until .

ANFA §

• An all-NFA is a five tuple that accepts if every possible state that could be in after reading input is a state from .
• Sipser e1.38: all-NFAs can recognize the class of regular languages.

Other Theorems §

• Sipser e1.52 Myhill-Nerode Theorem. Let be a language and and are strings. The distinguishing extension is defined as a string such that exactly one of and belongs in . The relation is defined where and are indistinguishable (i.e., no distinguishing extension exists). This relation is an Equivalence Relation.

  is regular if and only if has a finite number of equivalence classes.

  Moreover, the number of equivalence classes, called the index, is also the number of states in the minimal DFA accepting .

  Any minimal DFA acceptor for the language is isomorphic to this one: Let each equivalence class correspond to a state, and the state transitions are for each . The starting state is and the accepting states are .

Nonregular Languages §

• Sipser 1.70: The Pumping Lemma.

  If is a regular language, then there is a number called the pumping length where if is any string in of length at least , then where:

  1. , .
  3. . ³

• The pumping lemma implies that every finite language is regular.

Links §

• Sipser Ch. 1

Footnotes §

1. All these properties can be shown through the construction of finite automata. ↩

2. The intuition is this: if we start at and end at , either we can avoid passing through (expressed as ), or we do, in which case we have to: go , described by , possibly stay at described by then , described by ↩

3. The reason the pumping lemma holds is because, for regular languages, we have a DFA that has as many states as the pumping lemma (i.e., a finite number of states). In such a DFA, by pigeonhole principle, we must have crossed at least one state twice via regular expression . ↩