UNIT I
AUTOMATA FUNDAMENTALS
1.1 IntroductIon to AutomAtA theory
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 limits of 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
1.1.1 IntroductIon to FormAl lAnguAges
Formal languages are the system used to train the machines in recognizing certain
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:
r Regular Languages (RL)
r Context free Languages (CFL)
r Context Sensitive Languages (CSL)
,1.2 Theory of Computation
r Recursive Languages
r Recursively Enumerable Languages (RE)
à These languages are recognized by specific automata/machines and grammars.
r Regular grammars (type 3) and finite automata recognize regular
languages.
r Context free grammars (Type 2) and push down automata recognize
context free languages.
r Context sensitive grammars (Type 1) and Linear Bounded Automata
(LBA) recognize context sensitive languages.
r Unrestricted grammars (phrase structure grammar) (Type 0).
r Turing machines recognize recursively enumerable languages.
à Total Turing Machines (TTM) that halt for every input are used to recognize
recursive languages.
1. Formal Language Theory
Formal language theory describes languages as a set of operations over an alphabet.
It is closely linked with automata theory, as automata are used to generate and recognize
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. Computability theory
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. Models of Computation
The computation models that are developed by formal language theory are ,
i) Finite State Automata
ii) Regular expression
,Automata Fundamentals 1.3
iii) Push down Automata
iv) Linear bounded automata
v) Turing machine
à The computational models and the languages understandable by these models are
tabulated below.
Table 1.1 The Computational Models
Machines Grammars/ Languages Category
Finite State Automata
Regular Type 3 Simple
(Regular Expression)
Push Down Automata Context Free Type 2
Linear Bounded Automata Context Sensitive Type 1
Turing Machine Phrase Structure Type 0 Complex
Uncomputable
1.1.2 Basic Mathematical Notation and Techniques
1. Alphabet
An alphabet is a finite, nonempty set of symbols.
Example:
i. ∑ ={0,1}
ii. ∑ ={a,b,c}
2. String
A string over an alphabet is a finite sequence of symbols from that alphabet.
, 1.4 Theory of Computation
Example:
i. 01001 over ∑ ={0,1}
ii. aaabbbbccc over ∑ ={a,b,c}
3. Length of a string
The length of a string is the count of symbols in that string.
Example:
i. |01001| = 5
ii. |aaabbbbccc| =10
iii. |0315| = 8
4. Power of an alphabet
The power of an alphabet ∑k, is the set of all strings over ∑ 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)
The language of an Automata is a set of strings accepted by the automata.
AUTOMATA FUNDAMENTALS
1.1 IntroductIon to AutomAtA theory
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 limits of 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
1.1.1 IntroductIon to FormAl lAnguAges
Formal languages are the system used to train the machines in recognizing certain
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:
r Regular Languages (RL)
r Context free Languages (CFL)
r Context Sensitive Languages (CSL)
,1.2 Theory of Computation
r Recursive Languages
r Recursively Enumerable Languages (RE)
à These languages are recognized by specific automata/machines and grammars.
r Regular grammars (type 3) and finite automata recognize regular
languages.
r Context free grammars (Type 2) and push down automata recognize
context free languages.
r Context sensitive grammars (Type 1) and Linear Bounded Automata
(LBA) recognize context sensitive languages.
r Unrestricted grammars (phrase structure grammar) (Type 0).
r Turing machines recognize recursively enumerable languages.
à Total Turing Machines (TTM) that halt for every input are used to recognize
recursive languages.
1. Formal Language Theory
Formal language theory describes languages as a set of operations over an alphabet.
It is closely linked with automata theory, as automata are used to generate and recognize
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. Computability theory
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. Models of Computation
The computation models that are developed by formal language theory are ,
i) Finite State Automata
ii) Regular expression
,Automata Fundamentals 1.3
iii) Push down Automata
iv) Linear bounded automata
v) Turing machine
à The computational models and the languages understandable by these models are
tabulated below.
Table 1.1 The Computational Models
Machines Grammars/ Languages Category
Finite State Automata
Regular Type 3 Simple
(Regular Expression)
Push Down Automata Context Free Type 2
Linear Bounded Automata Context Sensitive Type 1
Turing Machine Phrase Structure Type 0 Complex
Uncomputable
1.1.2 Basic Mathematical Notation and Techniques
1. Alphabet
An alphabet is a finite, nonempty set of symbols.
Example:
i. ∑ ={0,1}
ii. ∑ ={a,b,c}
2. String
A string over an alphabet is a finite sequence of symbols from that alphabet.
, 1.4 Theory of Computation
Example:
i. 01001 over ∑ ={0,1}
ii. aaabbbbccc over ∑ ={a,b,c}
3. Length of a string
The length of a string is the count of symbols in that string.
Example:
i. |01001| = 5
ii. |aaabbbbccc| =10
iii. |0315| = 8
4. Power of an alphabet
The power of an alphabet ∑k, is the set of all strings over ∑ 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)
The language of an Automata is a set of strings accepted by the automata.
