Chapter 1: Introduction

Automata Theory:
It is the mathematical study of computing machines and their capacity.

This automaton consists of states and transitions. The State

is represented by circles, and the Transitions is
represented by arrows.

Automata is the kind of machine which takes some string

as input and this input goes through a finite number of
states and may enter in the final state.

Applications of Theory of Computation

● Deterministic Finite Automata (DFA) is used in Compiler Design where the first step is
lexer (lexical analysis)
● Models in Theory of Computation are used to model real life Computing Machines and
Problems.
● Models in Theory of Computation can be used to find limitation of Computing Machines
like Halting Problem.
● Super Recursive Algorithms in Theory of Computation present the future of Computing
Devices.
● Other real life applications of DFA:
○ Traffic Lights
○ Video Games
○ CPU Controllers
○ Protocol Analysis
○ Regular Expression Matching
○ Vending Machines
○ Speech Recognition
○ Natural Language Processing
● DFAs for simple Artificial Intelligence applications.
● All Algorithms are designed using Turing Machine.

basic terminologies that are important and frequently used in automata:

Symbols: which can be any letter, alphabet or any picture, simply anything. Ex- 1, a, b, #
Alphabets (Σ): finite, non-empty set of symbols. It is denoted by ∑.
Ex- ∑={a,b}
∑ = {A, B, C, …., Z}

FLAT by S. Shekhar | 1
∑ = {0, 1, ....., 9} is alphabet of decimal digit
∑ = {0, 1} is alphabet of binary digit
String (W): a finite sequence of symbols from some alphabet. A string is generally denoted as w
and the length of a string is denoted as |w|.
Ex- w = 010, then |w| = 3 means length of string is 3.
|abbb| = 4, |ababab| = 6.
NOTE: Empty string is the string with zero occurrence of symbols, represented as ε.
Q. Number of Strings (of length 2) that can be generated over the alphabet ∑ = {a, b}.
Ans: aa, ab, ba, bb
𝑛
Conclusion: For alphabet {a, b} with length n, number of strings can be generated = 2 .

Language: A language is a collection of appropriate string. A language which is formed over Σ

can be Finite or Infinite.
(OR)
*
A language is a subset of ∑ .

Types of Languages
1. Empty Languages
The Language that does not contain any string even empty string is called as empty language and
is denoted by ф.

2. Non Empty Languages

The Language that contain at least one string is called as non empty language .
3. Finite Languages
The Language which contains finite number of strings and length of each string is finite is called
as finite language . Ex- L = { 0 n 1n |1<=n<=1}
4. Infinite Languages
The Language which contains infinite number of strings and length of each string is finite is called
as infinite language . Ex- L={0n 1n |n>=1}
Ex-
L1 = {Set of string of length 2} = {aa, bb, ba, bb} Finite Language

FLAT by S. Shekhar | 2
L2 = {Set of all strings starts with 'a'} = {a, aa, aaa, abb, abbb, ababb} Infinite Language
L3 = { } Empty language (can be represented as ε) Finite Language
L4 = {0,1} Finite Language
*
L5 = {ε, 0, 1, 00, 01, 10, 11, 000, …..} Complete Language(∑ ) where ∑ = {0, 1}, Infinite
Language
L6 = { 0n 1m |m>=1,n>=1} also can be written as {0+ 1+}
*
NOTE: ∑ is a universal language.

Power of an alphabet
0
∑ = set of all strings of length = 0 ε
1
∑ = set of all strings of length = 1 0,1
2
∑ = set of all strings of length = 2 00.01,10,11
* 0 1 2 3 4
∑ = ∑ 𝑈 ∑ 𝑈 ∑ 𝑈 ∑ 𝑈 ∑ 𝑈 ................... = set of all strings of any length formed by ∑

* *
Ex- Let ∑= {0, 1}, ∑ = {0, 1} = {ε, 0, 1, 00, 01, 10, 11, 000, …..}
*
𝑎 = ϵ,a,aa,aaa,…….. Kleen Closure- { All possible strings including empty string }
+
𝑎 = a,aa,aaa,…….. Positive Closure- Kleene Closure - ϵ (empty string)

Grammar
Set of rules used to describe strings of a language, known as grammar.
Grammar formally defined as collection of 4 tuples {N,T,P,S}
N: set of Non-Terminals or variables
T: set of terminals
P: set of production rules
S: Start symbol

● For every language grammar exists.

● Every grammar generates one language.
● For one language many number of grammars can be constructed.
● One grammar produces one language only.

FLAT by S. Shekhar | 3
Derivation: The process of generating strings from the given grammar.
Parse Tree or Derivation Tree: tree representation of derivation.
● For regular language, there exist a grammar known as Regular grammar.
● For Context Free language, there exist a grammar known as Context Free grammar.
● For Context Sensitive language, there exist a grammar known as Context Sensitive
grammar.
● For Recursive Enumerable language(REL), there exist a grammar known as Recursive
Enumerable grammar or Unrestricted Grammar.
Ex- S → aSb / ab

Q. Identify language generated by following grammar:

1. S → aS / ε

Classwork-
2. S → aS / bS / ε
3. S → aS / bS / a / b
4. S → aSb / ε

Chomsky hierarchy of languages

FLAT by S. Shekhar | 4
Type 0 Grammar:
Type 0 grammar is known as Unrestricted grammar. There is no restriction on the grammar rules
of these types of languages. These languages can be efficiently modeled by Turing machines.
Ex-
bAa → aa
S→s

Type 1 Grammar:
Type 1 grammar is known as Context Sensitive Grammar. The context sensitive grammar is used
to represent context sensitive language. The context sensitive grammar follows the following rules:
● The context sensitive grammar may have more than one symbol on the left hand side of
their production rules.
● The number of symbols on the left-hand side must not exceed the number of symbols on the
right-hand side.
● The rule of the form A → ε is not allowed unless A is a start symbol. It does not occur on
the right-hand side of any rule.
Ex=-
S → AT
T → xy
A→a

Type 2 Grammar:
is known as Context Free Grammar. Context free languages are the languages which can be
represented by the context free grammar (CFG). Type 2 should be type 1. The production rule is of
the form A → α Where A is any single non-terminal and is any combination of terminals and
non-terminals.
Ex:
A → aBb
A→b
B→a

Type 3 grammar:
generate regular languages. These languages are exactly all languages that can be accepted by a
finite-state automaton. Type 3 is the most restricted form of grammar.
Type 3 should be in the given form only :
V → VT / T (left-regular grammar)
(or)
V → TV / T (right-regular grammar)

—--------------------------------------------------------------------
FLAT by S. Shekhar | 5