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 ﬁnal, 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:
Automaton |
Recognizable language |
Nondeterministic/Deterministic Finite state machine (FSM) |
regular languages |
Deterministic pushdown automaton (DPDA) |
deterministic context-free languages |
Pushdown automaton (PDA) |
context-free languages |
Linear bounded automaton (LBA) |
context-sensitive languages |
Turing machine |
recursively enumerable languages |
Deterministic Büchi automaton |
ω-limit languages |
Nondeterministic Büchi automaton |
ω-regular languages |
Rabin automaton, Streett automaton, Parity automaton, Muller automaton |
ω-regular languages |