Chapter 1

Preliminaries

Formal Languages and Automata

Introduction
 A formal language is an abstraction of the general
characteristics of programming languages. A formal language
consists of a set of symbols and some rules of formation by
which these symbols can be combined into entities called
sentences. A formal language is the set of all sentences
permitted by the rules of formation.
 They are used to represent both a computation problems
and recognition problems.
1.1 Basic notions of words and languages
Definitions
Alphabet Σ: nonempty (finite) set of symbols, like Σ = (a,b)
 Word w: a sequence of symbols, like (a, b, a) = aba.
 Σ∗ (resp. Σ+): the set of all infinite words.
 Σ+ : is the set of all nonempty words over Σ (Σ+ = Σ∗ \{€})

 Language L: a set of words, L ⊆ Σ∗.

 length of a word |w|: number of symbols of a word w
(example: jabbacaj = 6)
 Empty word : the word of length 0. (Ø)
Substrings
 A substring of a string S is another string S’ that occurs in
string S.
Prefix, suffix, infix
Given words w, v € Σ∗:
 prefix: w is a prefix of v iff there exists a word u € Σ∗ with
v = wu.
 Suffix/postfix: w is a suffix of v iff there exists a word u €
Σ∗ with v = uw.
 infix: w is an infix of v iff there exist words u1,u2 € Σ∗
with v = u1wu2
Q1. Write the expression A+B*C in terms of prefix and suffix expression?
Q2. Write a simple program that checks and convert the prefix, suffix and
infix of an expression?
Basic concepts of Automata theory
 The automata theory has a basic fundamental unit called set.
Set is used to represent mathematical models.
Set
 Set defined as a collection of objects. These objects are called
elements of the set.
 The Set can be represented using 3 methods
 Listing method
 Describing method
 Recursion method
Listing method
 The elements are listed in the set.
 Example – set of elements less than 3. then,
 A= {0,1,2}
Describing property
 The property of elements of a set define the set.
 Example – set of vowels.
A= {a, e, i, o, u}
Recursive method
 It occurs to define the elements of the set.
 Example – A= {x| x is square of n} where n<10
 A= {0, 1, 4, 9, …, 81}
Set Properties
 Subset
 The subset A is called subset of set B if every element of
set A is present in set B but reverse is not true. It is
denoted by A B.
 Empty Set
 The set having no elements in it is called empty set. It’s
denoted by A={} and it can be written as Ø (phi)
 Power set
 It’s the set of all the subsets of its element.
 eg:- A={1,2}, then power set is
 Q={Ø, {1}, {2}, {1,2}} 2Q = 22 = 4 elements
Operations on Set
 Let’s see some of the basic set operations
1. A  B is Union Operation. If A={1,2,3} & B=
{1,2,4}, then A  B = {1,2,3,4}
i.e. Combination of both sets
2. A o B is Intersection Operation.
If A= {1,2,3} & B= {1,2,4}, then A o B= {1,2}
i.e. Collection of common elements from both the sets
3. A – B is the difference operation. If A={1,2,3} &
B={2,3,4}, then A – B = {1}
i.e. elements which are there in set A but not in set B
Cardinality of Sets
 In mathematics, the cardinality of a set is a measure of the
"number of elements of the set".
 The cardinality of a set is nothing but the number of
members in the set.
 Example, the set A = {2, 4, 6} contains 3 elements, and
therefore A has a cardinality of 3.
 Let A be a set.
 If A =  (the empty set), then the cardinality of A is 0.
 If A has exactly n elements, n a natural number, then the
cardinality of A is n. The set A is a finite set.
 Otherwise, A is an infinite set.
 n(A∪B)=n(A)+n(B) - n(A∩B) Cardinality of intersection set
Notation
• The cardinality of a set A is denoted by | A |.
a.If A =  , then | A |= 0.
b.If A has exactly n elements, then | A | = n.
c.If A is an infinite set, then | A | = .
DEFINITION:
Let A and B be sets. Then, |A| = |B| if and only if there is a one-
to-one correspondence between the elements of A and the elements
of B.
Examples:
A = {1, 2, 3, 4, 5} & B = {a, e, i, o, u}
1 a, 2 e, 3 i, 4 o, 5 u; |B| = 5
Exercise.
Among the voters at the board meeting, there are 20 females, 32
Democrats, and 17 female Democrats. How many voters are either
female or Democrat?
Disjoint sets
 In mathematics, two sets are said to be disjoint if they have
no element in common.
 Disjoint sets are sets whose intersection is the empty set.
 Example:- A= {1, 2, 3} and B= {4,5,6}, then
Set A and Set B are disjoint sets.
Graphs
 Graph is a set of points with lines connecting some points.
The points are called nodes or vertices, and the lines are
called edges.
 A graph is denoted by G= (V,E) consisting of finite set of
vertices/nodes V and set of edges. Edges are nothing but pair
of vertices.
Directed Graphs
 It’s a collection of vertices and edges where the directions are
mentioned along the edges.
 Directed graph or (digraph) is a graph that is a set of
vertices connected by edges, where the edges have a
direction associated with them.

Note
• No more than one edge is allowed between any two nodes
• The number of edges at a particular node is called the degree
of that node.
Directed Graphs Continue
Trees
 Tree is a collection of vertices and edges with the following
properties.
 There is one vertex, called root which has no
predecessors.
 From this root node all the successors are ordered.
 A tree is an undirected graph in which any two vertices
are connected by exactly one path.
 The only and basic difference between graphs and trees is
that graphs do not have special node called root node.
Binary trees
 A binary tree is a data structure in which each node has at the
most two children which are called left child and right
child.
 Binary Tree is a special data structure used for data storage
purposes.
 A binary tree has a special condition that each node can have
a maximum of two children.
 A binary tree has the benefits of both an ordered array and a
linked list as search is as quick as in a sorted array and
insertion or deletion operation are as fast as in linked list.
 Leaf is a node having no children.
Binary trees
Advantages of trees
Trees are so useful and frequently used, because they have some
very serious advantages:-
 Trees reflect structural relationships in the data
 Trees are used to represent hierarchies
 Trees provide an efficient insertion and searching
 Trees are very flexible data, allowing to move sub trees
around with minimum effort
Introduction to defining languages
 Alphabet: an alphabet is a collection of symbols.
Example – S= {0,1}, here 0 & 1 are alphabets denoted by S
 String: String is a finite collection of symbols from
alphabets.
Example – if Σ= {a,b} then various strings can be formed
from Σ are {ab, aa, aaa, bb, bbb, ba, aba, . . . }. In this case,
infinite set of strings can be generated.
 Language: it’s a collection of appropriate strings. The
language is defined using an input set.
 Operations on strings
 Operations that carried out on strings are
Concatenation: two strings are combined together to
form a single string. Example:- x={good} & y= {morning}
then the concatenated strings will be xy={goodmorning}
Transpose: it’s also called reverse operation. Let’s see
some examples.
Example1. (ba)t = a(b)
2. (010111)T = (1110101)
 Palindrome: it’s a property of a string in which strings
can be read same from left to right as well as from right to
left. Example :- the string “madam” is palindrome
Operation on languages
 Language is a collection of strings. So, lets see some basic
operations :-
If L1 and L2 are two languages,
i. Union of two languages is denoted as L1 Y L2
ii. Concatenation of languages is denoted as L1L2
iii. intersection of two languages is denoted as L1 I L2
iv.Difference of two languages is denoted by L1 - L2
Exercise
Consider the string X= 110 and Y= 0110, then find
a. xy
b. yx
c. x2
Kleen Closures
 It’s also called star closures.
 It’s a set of strings of any length (including null String).
Example
let Σ= {0,1}, obtain Σ* = Σ0 Y Σ1 Y Σ2 Y Σ3 . . .
 Therefore, the kleen closure will be
Σ = {, 0,1,00, 11, 01, 10, 010, 000, 111, 0101 …. }
• This shows, it’s a set of string of any length.
 The positive closure Σ+ can be defined as Σ1 Y Σ2 Y Σ3 . . . Which
means it consists of all strings of any length except a null
string.
Σ* = Σ+ + 
Concatenation
Definition
• The concatenation of two words w = a1a2 . . . an and
v = b1b2 . . . bm with n, m ≥ 0 is
w ◦ v = a1 . . . Anb1 . . . bm
Sometimes we write uv instead of u ◦ v.
• In general,
w◦Ø=Ø◦w=w neutral element
u ◦ (v ◦ w) = (u ◦ v) ◦ w associativity
Concatenation
 Examples
If L1 = (0,1, 01) and L2 = (1, 00) then
L1*L2 = (01, 11, 011, 000, 100, 0100)

For L1 = (b, ba, bab) and L2 = (Ø, b, bb, abb) we have

L1*L2 =(b, ba, bb, bab, bbb, babb, baabb, babbb, bababb)

Reading Assignment
 Associative Property
 Commutative Property
 Distributive Property
Exponents and reversals

• Exponents
 wn: w concatenated n-times with itself.
 wn = w.w.w . . .

• Reversals
 The reversal of a word w is denoted wR (example:
(abcd)R = dcba.
 A word w with w = wR is called a palindrome.
Example- (madam, mum, otto, . . . )
Introduction to formal Proofs
 Mathematical induction is a mathematical
proof technique used to prove a given statement set. Most
commonly, it is used to establish statements for the set of
all Natural Numbers.
 Formal proofs are proofs in which we try to prove that
statement B is true because of statement A is true. The
statement A is called hypothesis and statement B is called
Conclusion.
 Formal proof can be using a deductive proof and
inductive proof.
 continue
 Deductive proof consists of sequence of statements given
with logical reasoning in order to proof the 1st or initial
statement.The initial statement is called hypothesis.
 Inductive proof is a recursive kind of proof which consists
of sequence of parameterized statements that use the
statement itself with lower values of its parameter.
 Question
 Differentiate Deductive and inductive proofs with example?
Inductive proofs
 They are special type of proofs used to proof recursively
defined objects.
 The inductive proof can be carried out using two steps
1. Basis of induction – shows lowest possible value
2. Inductive step – shows further possibilities
 Examples
 Prove that 1+2+3+ … +n = n(n+1)/2 is true ?
(Using inductive proofs)
Exercises
 Using induction, prove each of the following for all natural
numbers.
1. 1+4+7+…+ (3n-2) = n(3n-1)/2 for n>0
2. ½ + ¼ + 1/8 + … + 1/2n = (2n – 1)/2n