Formal Languages and Logic/Finite state automata

From Wikibooks, open books for an open world
Jump to navigation Jump to search

Definition (deterministic finite state automaton):

A deterministic finite state automaton (DFA for short) is a quintuple , where is a finite set, is a finite alphabet, is a function, , and .

Definition (state):

Let be a deterministic finite state automaton. Then a state of is an element of .

Definition (initial state):

Let be a deterministic finite state automaton. Then the initial state of is .

Definition (transition function):

Let be a deterministic finite state automaton. Then is the transition function.

Definition (accepting state):

Let be a deterministic finite state automaton. Then an accepting state is an element of .

Proposition (every accepting state is a state):

Let be a deterministic finite state automaton. Then every accepting state of is a state.

Proof: This is because .

Definition (generalized transition function):

Let be a deterministic finite state automaton. Then the generalized transition function is the function defined on by induction on word length as thus:

  1. for a singleton word ,
  2. whenever , then

Definition (language accepted by a deterministic finite state automaton):

Let be a finite state automaton. The language accepted by the deterministic finite state automaton by is defined to be

.

Theorem (finite state automata accept precisely regular languages):

Whenever is a finite state automaton, the language accepted by is regular. Whenever is a regular language, there exists a finite state automaton that accepts it.

Proof: Let first be a finite state automaton. Define a Chomsky grammar as follows: , and the productions shall be given by