In eduladder you can Ask,Answer,Listen,Earn and Download Questions and Question papers.

Watch related videos of your favorite subject.

Connect with students from different parts of the world.

Apply or Post Jobs, Courses ,Internships and Volunteering opportunity. For FREE

See Our team

Wondering how we keep quality?

Got unsolved questions? Ask Questions

GATE
GMAT
CBSE
NCERT
Career
Interview
Railway
UPSC
NID
NIFT-UG
NIFT-PG
PHP
AJAX
JavaScript
Node Js
Shell Script
Research

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. FQ) 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 }