 The Eduladder is a community of students, teachers, and programmers just interested to make you pass any exams. So we help you to solve your academic and programming questions fast.
Watch related videos of your favorite subject.
Connect with students from different parts of the world.
See Our team
Wondering how we keep quality?
Got unsolved questions?

You are here:Open notes-->VTU-->FLATFORMAL-LANGUAGES-AND-AUTOMATA-THEORY-UNIT--1-10cs56

# FLAT(FORMAL LANGUAGES AND AUTOMATA THEORY) UNIT -1 [10cs56] Hugo(English movie about one robot which can draw images based on howdini)

1.1:Introduction to finite automata
In this chapter we are going to study a class of machines called finite automata. Finite
automata are computing devices that accept/recognize regular languages and are used to
model operations of many systems we find in practice. Their operations can be simulated by
a very simple computer program. A kind of systems finite automnata can model and a
computer program to simulate their operations are discussed.

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 reads 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.
1.2:concepts of automata theory
Automata theory is a subject matter that studies properties of various types of automata. For
example, the following questions are studied about a given type of automata.
� Which class of formal languages is recognizable by some type of automata?
(Recognizable languages)
� Are certain automata closed under union, intersection, or complementation of formal
languages? (Closure properties)
� How much is a type of automata expressive in terms of recognizing class of formal
languages? And, their relative expressive power? (Language Hierarchy)
Automata theory also studies if there exist any effective algorithm or not to solve problems
similar to the following list.
� Does an automaton accept any input word? (emptiness checking)
� Is it possible to transform a given non-deterministic automaton into deterministic
automaton without changing the recognizable language? (Determinization)
� For a given formal language, what is the smallest automaton that recognizes it?
(Minimization).

Classes of automata
The following is an incomplete list of types of automata.
-----------------------------------------------------------------------------------------------------
Automata                                                                        Recognizable language
Deterministic finite automata(DFA)                                    regular languages

Nondeterministic finite automata(NFA)                              regular languages

Nondeterministic finite automata with ε-transitions (FND-ε
or ε-NFA)                                                                        regular languages
Pushdown automata (PDA)                                               context-free languages

Linear bounded automata (LBA)                                        context-sensitive language

Turing machines                                                              recursively enumerable
languages
Timed automata                                                               ω-limit languages

Deterministic B�chi automata                                            ω-regular languages

Nondeterministic B�chi automata                                         "

Nondeterministic/Deterministic Rabin automata                    "

Nondeterministic/Deterministic Streett automata                   "

Nondeterministic/Deterministic parity automata                      "

Nondeterministic/Deterministic Muller automata                    "

-----------------------------------------------------------------------------------------------------

.1.3:Deterministic finite automata
. Definition: A DFA is 5-tuple or quintuple M = (Q, Σ, δ, q0, A) where
Q is non-empty, finite set of states.
Σ is non-empty, finite set of input alphabets.
δ is transition function, which is a mapping from Q x Σ to Q.
q0 􀀀 Q is the start state.
A 􀀀 Q is set of accepting or final states.
Note: For each input symbol a, from a given state there is exactly one transition (there can be
no transitions from a state also) and we are sure (or can determine) to which state the
machine enters. So, the machine is called Deterministic machine. Since it has finite number
of states the machine is called Deterministic finite machine or Deterministic Finite
Automaton or Finite State Machine (FSM).
The language accepted by DFA is
L(M) = { w | w 􀀀 Σ* and δ*(q0, w) 􀀀 A }
The non-acceptance of the string w by an FA or DFA can be defined in formal notation as:
L(M) = { w | w 􀀀 Σ* and δ*(q0, w) 􀀀 A }

## Tool box

Edit this note | Upvote | Down vote | Questions

### Watch more videos from this user Here

Learn how to upload a video over here