Introduction To Automata Theory And Formal Languages

Introduction: Automata are the main modeling tools in Computer Science. Whenever we want to design a program, a protocol or an information system, or even just describe what it is intended to do, its characteristics, and its behavior, we use these special kinds of diagrams.  Automata are systems consisting of states, some of them designated as initial or final, and (usually) labeled transitions.

Formal definition

Automaton

An automaton is represented formally by a 5-tuple (Q,Σ,δ,q0,F), where:

Q is a finite set of states.

Σ is a finite set of symbols, called the alphabet of the automaton.

δ is the transition function, that is, δ: Q × Σ → Q.

q0 is the start state, that is, the state of the automaton before any input has been processed, where q0∈ Q.

F is a set of states of Q (i.e. F⊆Q) called accept states.

Input word

An automaton reads a finite string of symbols a1,a2,...., an , where ai∈Σ, which is called an input word. The set of all words is denoted by Σ*.

Run

A run of the automaton on an input word w = a1,a2,...., an ∈Σ*, is a sequence of states q0,q1,q2,...., qn, where qi ∈ Q such that q0 is the start state and qi = δ(qi-1,ai) for 0 < i ≤ n. In words, at first the automaton is at the start state q0, and then the automaton read symbols of the input word in sequence. When the automaton reads symbol ai it jumps to state qi = δ(qi-1,ai). qn is said to be the final state of the run.

Accepting word

A word w ∈Σ* is accepted by the automaton if qn∈ F.

Recognized language

An automaton can recognize a formal language. The language L ⊆Σ* recognized by an automaton is the set of all the words that are accepted by the automaton.

Recognizable languages

The recognizable languages are the set of languages that are recognized by some automaton. For the above definition of automata the recognizable languages are regular languages. For different definitions of automata, the recognizable languages are different.

Classes of automata: