Formal languages and automata theory

Designed by K.Geeta Asst.Professor Dept. of CSE RGUKT Basar

Why do we study it?

Designed by K.Geeta Asst.Professor Dept. of CSE RGUKT Basar

 Why do we study it?

• This subject gives us the theory behind the work  that has
been carried out in the field of computer science.
• It allows us to think systematically about what machine do
without going into hardware details I.e how  machine 
works  and process data without entering into its hardware
concept.
• It gives theoretical machine design.
• It is an area of computer science that deals with the study
of abstract machines as well as the computation problem
that can be solving using them.

Designed by K.Geeta Asst.Professor Dept. of CSE RGUKT Basar

Designed by K.Geeta Asst.Professor Dept. of CSE RGUKT Basar
 • Regular expressions (REs) are used
in many systems.

• E.g., UNIX, Linux, OS X,... a.*b.

Regular • E.g., Document Type Definitions

describe
Expressions?
XML tags with a RE format like person

(name, addr, child*).

Designed by K.Geeta Asst.Professor Dept. of CSE RGUKT Basar
 Context-free grammars (CFGs) are
used to describe the syntax of every
Why modern programming language.

Context- Every modern complier uses CFG

Free concepts to parse programs

Grammars? And Document Type Definitions are

really CFG’s.

Designed by K.Geeta Asst.Professor Dept. of CSE RGUKT Basar

 Course Objectives:

1 2 3 4 5 6 7
Develop a formal Design finite Prove that a given Design context free Prove equivalence of Identify the Distinguish between
notation for strings, automata to accept language is regular grammars to languages accepted hierarchy of formal computability and
languages and a set of strings of a and apply the generate strings by Push Down languages, non-computability
machines. language. closure properties of from a context free Automata and grammars and and Decidability and
languages. language and languages generated machines. undecidability.
convert them into by context free
normal forms. grammars.

Designed by K.Geeta Asst.Professor Dept. of CSE RGUKT Basar

Course outcomes

1 2 3 4 5 6 7
Write a formal Design finite For a given language Design context free Determine Write the hierarchy Distinguish between
notation for strings, automata to accept determine whether grammars to equivalence of of formal languages, computability and
languages and a set of strings of a the given language generate strings of languages accepted grammars and non-computability
machines. language. is regular or not. context free by Push down machines. and Decidability and
language. Automata and undecidability.
languages
generated by
context free
grammars.

Designed by K.Geeta Asst.Professor Dept. of CSE RGUKT Basar

 Alphabet 
• Symbol:
• Is an abstract entity.

• It cannot be  formerly defined as points in geometry..

• Exmaples: Letters ,digits,special symbols like $,#,@,etc
• Alphabet:
• A finite colection of symbols denoted by Σ.

Designed by K.Geeta Asst.Professor Dept. of CSE RGUKT Basar

String ,Language

• String 
• Set of symbols from alphabet.
• Example: 001,110,111 strings from binary alphabet.
• English alpha bet={ a,b,c,…..}
• Strings :abc,aaa,gf
• Language:
• :is set of words.
• An empty string denoted by ε
• length is =0
Designed by K.Geeta Asst.Professor Dept. of CSE RGUKT Basar
Examples:Σ={0,1}
• L1={set of strings of length 2}
• L1={00,01,10,11}
• L2={set of all strings of length 3 over Σ}
• L2={000,001,010,011,100,101,110,111}
• L3={set of all strings beginning with 1}
• L3={1,10,100,11,110,101,111,…..}

Designed by K.Geeta Asst.Professor Dept. of CSE RGUKT Basar

How many strings on alphabet Σ of length n
are possible ?
• |Σ|n

Designed by K.Geeta Asst.Professor Dept. of CSE RGUKT Basar

Gammar
• Grammar is basically defined as set of 4 tuple(V,T,P,S)
• Where
• V is set of Non terminals
• T is set of terminals
• P is set of productions(rule) which relate the non terminals
and terminals 
• S is starting symbol with which strings in grammar are
derived..

Designed by K.Geeta Asst.Professor Dept. of CSE RGUKT Basar

Designed by K.Geeta Asst.Professor Dept. of CSE RGUKT Basar

• G(S,a,S->aS->aS,S)
• V:S
• T:a
• P:S->a
• S->aS
• S:S
• Language acceptance:
• Start with start symbol and at every step replace the
Language acceptance: nonterminal by right hand side of the rule.Continue this
untill string of terminals is derived.

• The string of terminals gives language accepted by the

grammar.
• S->a
• S->aS
• S->a.........{a}
• S->aS
• ->aa......{aa}
• S->aS
• ->aaS
• ->aaa...{aaa}
• {a,aa,aaa,....}=a
Designed by K.Geeta Asst.Professor Dept. of CSE RGUKT Basar
 Types of Grammar-Chomsky Hierarchy

• Type-0 grammar-Unrestricted Grammar:

• These grammars include all formal grammars.
• In URG all productions are of the form α->β where α and β may have any number of
terminals and non terminals.
• aA->abCB
• bC->d
• B->f
• -Generate all languages that can be reconized by a Turing machine.These languages are
also known as recursively enumerable  languages.

Designed by K.Geeta Asst.Professor Dept. of CSE RGUKT Basar

 Type-1 Grammar-Context sensitive
Grammar(CSG)

• These grammars define context sensitive languages

• In CSG   all productions are of the form α->β where |α|≤|β|,α and β may
have any number of terminals and non terminals.
• These grammars can have rules of the form αAβ->αŸβ where A as
nonterminal and α ,Ÿ,β  are strings of terminals and non terminals. We can
replace A by Ÿ where A lies between α and β.Hence the name context
sensitive grammar.
• These languages can be recognized  by  a Linear Bound automata.

Designed by K.Geeta Asst.Professor Dept. of CSE RGUKT Basar

 These grammars define context free languages.
Type –2 These are defined by rules of the form α->β
Grammar- Where|α|=1 and is nonterminal.
Context Free Β is a string of terminals and nonterminals.
Grammar(CF --recognized by Pushdown automaton.
G) S->aS|Sa|a

Designed by K.Geeta Asst.Professor Dept. of CSE RGUKT Basar

Designed by K.Geeta Asst.Professor Dept. of CSE RGUKT Basar

Type-3
grammar-
Regular • -generate regular languages.

Grammar
• -A->aA|a
• A->Aa|a
• -recognized by finite automaton
Finite automata
• -is mathematical model of a digital computer.
• -are used as string or language acceptors.
• -used in pattern matching tools like LEX and text editors.

Designed by K.Geeta Asst.Professor Dept. of CSE RGUKT Basar

Finite automata

• An automaton can be represented by a 5-tuple (Q, ∑, δ, q 0, 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.QXΣ->Q.
• q0 is the initial state from where any input is processed (q0 ∈ Q).
• F is a set of final state/states of Q (F ⊆ Q).

Designed by K.Geeta Asst.Professor Dept. of CSE RGUKT Basar

Finite automata Model

a b c d a a a a a B

Input tape

reading
head 

Finite control
Designed by K.Geeta Asst.Professor Dept. of CSE RGUKT Basar
Lexical analyser behavior can be shown as FA.Consider the lexical
analyser that matches words like "to","this","the"

Designed by K.Geeta Asst.Professor Dept. of CSE RGUKT Basar

Give the language defined by the following
FA

Designed by K.Geeta Asst.Professor Dept. of CSE RGUKT Basar

Finite automata can be represented by 

A)Transitio B)Transition
n diagram table
Designed by K.Geeta Asst.Professor Dept. of CSE RGUKT Basar
Designed by K.Geeta Asst.Professor Dept. of CSE RGUKT Basar

Transitio • Contains 

n
• Set of states as circles
• Start state q0 with arrow
• Final state by double circle

diagram • A finite set of transitions that show how to

go from state to another.
• Transition table
• Tabular representation where rows correspond to state and column
correspond to input.
• Start state is given by 
• Final state by *

Designed by K.Geeta Asst.Professor Dept. of CSE RGUKT Basar

Example
• M={{q0,q1,q2},{a,b},δ,q0,{q2}}
• δ(
•δ

Designed by K.Geeta Asst.Professor Dept. of CSE RGUKT Basar

Example

• M={{q0,q1,q2},{a,b},δ,q0,{q2}}
• δ(q0,a)=q1,        δ(q0,b)=q2,
• δ(q1,a)=q2,       δ(q1,b)=q0, Δ/Σ a b
• δ(q2,a)=q2,       δ(q2,b)=q2
q0 q1 q2
q1 q2 q0
q2 q2 q2

Designed by K.Geeta Asst.Professor Dept. of CSE RGUKT Basar

Designed by K.Geeta Asst.Professor Dept. of CSE RGUKT Basar
Finite automata  is of two types
• Deterministic Finite automata(DFA)
• Non Deterministic Finite automata(NFA)

Designed by K.Geeta Asst.Professor Dept. of CSE RGUKT Basar

DFA
• A DFA is a collection of 5-tuples same as we described in the definition of FA.
• Q: finite set of states  
• ∑: finite set of the input symbol  
• q0: initial state   
• F: final state  
• δ: Transition function  
• Transition function can be defined as:
• δ: Q x ∑→Q  
• There will be uniq transition  in any state on an input symbol.

Designed by K.Geeta Asst.Professor Dept. of CSE RGUKT Basar

NFA
• A NFA is a collection of 5-tuples same as we described in the definition of FA.
• M=(Q,Σ,δ,q0,F)
• Q: finite set of states  
• ∑: finite set of the input symbol  
• q0: initial state   
• F: final state  
• δ: Transition function  
• Transition function can be defined as:
• δ: Q x ∑→2Q  
• There can be more than one transition  in any state on an input symbol.
Designed by K.Geeta Asst.Professor Dept. of CSE RGUKT Basar