UNIT - I
AUTOMATA FUNDAMENTALS
1.1 INTRODUCTIONTOAUTOMATATHEORY
Automata theory is the study of abstract machines and the computational problems can
be solved using these machines. Abstract machines are called automata. The name comes from
the
Greek word (Αυτόματα).
It means doing something by itself. An automaton can be a finite representation of a formal
language that may be an infinite set. Automata are used as theoretical models for computing
machines, and are used for proofs about computability.The automata theory is essential for, ☞
The study of the limit so computation
☞ Designing and checking the behaviour of digital circuits.
☞ Pattern searching in Websites
☞ Verifying systems of all types that have a finite number of distinct states, such as
Communications protocols or protocols for secure exchange information
INTRODUCTIONTOFORMALLANGUAGES
Formallanguagesarethesystemusedtotrainthemachinesinrecognizingcertain commands
or instructions. These languages are the abstraction of natural languages, since they are expended
by the machines. Formal languages are of five types.They are:
❒ RegularLanguages (RL)
❒ ContextfreeLanguages(CFL)
❒ ContextSensitiveLanguages(CSL)
TheoryofComputation
❒ Recursive Languages
❒ RecursivelyEnumerableLanguages(RE)
, ➠ Theselanguagesarerecognizedbyspecificautomata/machinesandgrammars.
❒ Regular grammars(type3)and finite automata recognize regular languages.
❒ Contextfreegrammars(Type2)andpushdownautomatarecognize context
free languages.
❒ Contextsensitivegrammars(Type1)andLinearBoundedAutomata (LBA)
recognize context sensitive languages.
❒ Unrestrictedgrammars(phrasestructuregrammar)(Type0).
❒ Turingmachinesrecognizerecursivelyenumerablelanguages.
➠ TotalTuringMachines(TTM)thathaltforeveryinputareusedtorecognize recursive
languages.
1. FormalLanguageTheory
Formallanguagetheorydescribeslanguagesasasetofoperationsoveranalphabet.
Itiscloselylinkedwithautomatatheory,asautomataareusedtogenerateandrecognize formal
languages.Automata are used as models for computation; formal languages are the
preferred mode of specification for any problem that must be computed.
2. Computabilitytheory
Computability theory deals primarily with the question of the extent to which a
problem is solvable on a computer. It is closely related to the branch of mathematical
logic called recursion theory.
3. ModelsofComputation
Thecomputation modelsthat aredeveloped byformal languagetheory are ,
i) FiniteStateAutomata
ii) Regular expression iii)
PushdownAutomata iv)
Linear bounded automata
,AutomataFundamentals
v) Turingmachine
➠ Thecomputationalmodelsandthelanguagesunderstandablebythesemodelsare
tabulated below.
Table1.1TheComputationalModels
Machines Grammars/ Languages Category
FiniteStateAutomata
Regular Type3 Simple
(Regular Expression)
PushDownAutomata Context Free Type2
LinearBoundedAutomata Context Sensitive Type1
TuringMachine Phrase Structure Type0 Complex
Uncomputable
1.1.2 BasicMathematicalNotationandTechniques
1. Alphabet
Analphabetisafinite,nonemptysetof symbols.
Example:
i. ∑ ={0,1}
ii. ∑ ={a,b,c}
2. String
Astringoveranalphabetisafinitesequenceofsymbolsfromthat alphabet.
TheoryofComputation
Example:
, i. 01001 over ∑ ={0,1} ii.
aaabbbbccc over ∑ ={a,b,c}
3. Lengthofastring
Thelengthof astring isthecount ofsymbolsinthat string.
Example:
i. |01001|=5 ii.
|aaabbbbccc|=10
iii. |0315|= 8
4. Powerofanalphabet
Thepower ofan alphabet∑k, isthe set ofall stringsover ∑with length k.
Examples:
0,1
2
00,01,10,11
3
000,001,010,011,100,101,110,111
..
*
e,0,1,00,01,10,11,000,001,010,011,100,101,110,111
0 1 2
= .......................
0
=
0,1,00,01,10,11,000,001,010,011,100,101,110,111
1 2 3
= .......................
5. Language(L)
Thelanguageof anAutomata isa setof stringsaccepted bythe automata.
AUTOMATA FUNDAMENTALS
1.1 INTRODUCTIONTOAUTOMATATHEORY
Automata theory is the study of abstract machines and the computational problems can
be solved using these machines. Abstract machines are called automata. The name comes from
the
Greek word (Αυτόματα).
It means doing something by itself. An automaton can be a finite representation of a formal
language that may be an infinite set. Automata are used as theoretical models for computing
machines, and are used for proofs about computability.The automata theory is essential for, ☞
The study of the limit so computation
☞ Designing and checking the behaviour of digital circuits.
☞ Pattern searching in Websites
☞ Verifying systems of all types that have a finite number of distinct states, such as
Communications protocols or protocols for secure exchange information
INTRODUCTIONTOFORMALLANGUAGES
Formallanguagesarethesystemusedtotrainthemachinesinrecognizingcertain commands
or instructions. These languages are the abstraction of natural languages, since they are expended
by the machines. Formal languages are of five types.They are:
❒ RegularLanguages (RL)
❒ ContextfreeLanguages(CFL)
❒ ContextSensitiveLanguages(CSL)
TheoryofComputation
❒ Recursive Languages
❒ RecursivelyEnumerableLanguages(RE)
, ➠ Theselanguagesarerecognizedbyspecificautomata/machinesandgrammars.
❒ Regular grammars(type3)and finite automata recognize regular languages.
❒ Contextfreegrammars(Type2)andpushdownautomatarecognize context
free languages.
❒ Contextsensitivegrammars(Type1)andLinearBoundedAutomata (LBA)
recognize context sensitive languages.
❒ Unrestrictedgrammars(phrasestructuregrammar)(Type0).
❒ Turingmachinesrecognizerecursivelyenumerablelanguages.
➠ TotalTuringMachines(TTM)thathaltforeveryinputareusedtorecognize recursive
languages.
1. FormalLanguageTheory
Formallanguagetheorydescribeslanguagesasasetofoperationsoveranalphabet.
Itiscloselylinkedwithautomatatheory,asautomataareusedtogenerateandrecognize formal
languages.Automata are used as models for computation; formal languages are the
preferred mode of specification for any problem that must be computed.
2. Computabilitytheory
Computability theory deals primarily with the question of the extent to which a
problem is solvable on a computer. It is closely related to the branch of mathematical
logic called recursion theory.
3. ModelsofComputation
Thecomputation modelsthat aredeveloped byformal languagetheory are ,
i) FiniteStateAutomata
ii) Regular expression iii)
PushdownAutomata iv)
Linear bounded automata
,AutomataFundamentals
v) Turingmachine
➠ Thecomputationalmodelsandthelanguagesunderstandablebythesemodelsare
tabulated below.
Table1.1TheComputationalModels
Machines Grammars/ Languages Category
FiniteStateAutomata
Regular Type3 Simple
(Regular Expression)
PushDownAutomata Context Free Type2
LinearBoundedAutomata Context Sensitive Type1
TuringMachine Phrase Structure Type0 Complex
Uncomputable
1.1.2 BasicMathematicalNotationandTechniques
1. Alphabet
Analphabetisafinite,nonemptysetof symbols.
Example:
i. ∑ ={0,1}
ii. ∑ ={a,b,c}
2. String
Astringoveranalphabetisafinitesequenceofsymbolsfromthat alphabet.
TheoryofComputation
Example:
, i. 01001 over ∑ ={0,1} ii.
aaabbbbccc over ∑ ={a,b,c}
3. Lengthofastring
Thelengthof astring isthecount ofsymbolsinthat string.
Example:
i. |01001|=5 ii.
|aaabbbbccc|=10
iii. |0315|= 8
4. Powerofanalphabet
Thepower ofan alphabet∑k, isthe set ofall stringsover ∑with length k.
Examples:
0,1
2
00,01,10,11
3
000,001,010,011,100,101,110,111
..
*
e,0,1,00,01,10,11,000,001,010,011,100,101,110,111
0 1 2
= .......................
0
=
0,1,00,01,10,11,000,001,010,011,100,101,110,111
1 2 3
= .......................
5. Language(L)
Thelanguageof anAutomata isa setof stringsaccepted bythe automata.
