THEORY OF
AUTOMATA
Lecture 02
SUPERIOR COLLEGE BHERA
2
▸ In automata, we study about abstract machines, how they works (i.e. respond) to
inputs. To understand working of machines, the first thing that comes is the
input which actually determines the next state of the system.
▸ What kind of input is given, is this input accepted or rejected. Every abstract
machine have different mechanism, as Computer takes mostly from keyboard or
mouse, ATM also has built in keypad, we can’t attach full keyboard with ATM.
▸ Language has an important role in a machine, it is the first step to communicate
with any machine.
3
What is Language?
▸ A language is a collection of sentences of finite
length all constructed from a finite alphabet of
symbols.
▸ Each language has its own set of rules like English
has grammar rules, Urdu also has some rules, even
programming languages defines their own set of
rules.
4
Formation of Language?
▸ Symbols/Letters: Different characters or symbols out of which we
can make languages. Each language has its own characters. It may
be finite or infinite. {a , b, c ,d,1 , 2 , 3 ,# ,9 , ? ,&, M, ), }
▸ Alphabets: A finite, non-empty set of symbols is known as Alphabet.
It is denoted by Greek letter ∑. This is the set over which the strings
are defined.
▹ ∑ = {a, b, c, d}
▹ ∑ = {A,B,C}
▹ ∑ = {0,1,2,3}
▹ ∑ = {0,1,a,b,c,d}
5
Formation of Language?
▸ String: A string is a finite sequence of any symbol selected from the
set of alphabet symbols. It is generally denoted by w.
▹ ‘cabcad’ is a valid string on the alphabet set ∑ = {a, b, c, d}
▹ ∑1 = {0,1} w = 100111
▹ ∑2 = {a,b,c} w2 = abaccab
▸ Length of String: The number of symbols present in the string is
known as the Length of the string. The length of the string is denoted
by |w|. For the string S = 'adadda', the length of the string is |S| = 6.
6
Formation of Language?
▸ Word: Words are the strings that belong to some language. Example
let a language L={aa, ab, ac, ba, bb, bc, cc, ca, cb } ac, ab, cc are
the words of language but cca is not
▸ If ∑ = {a, b}, various strings for a language can be generated {ab,
aa, aaa, bb, bbb, ba, aba.....}.
▸ Make a language which contains only two length strings/words over
alphabets ∑ ={a, b, c} so L={aa, ab, ac, ba, bb, bc, cc, ca, cb }
▸ Make a language that contains all string starts with a ∑ ={a, b} so
L={aa, ab, aaa, aba, abab, abbb,……….}
▸ Make a language that contains all string starts with a and ends with a
∑ ={a, b} so L={aa, aba, aaa, abba, ababa, abaa ,……….}
7
Properties of String?
▸ Empty String: A string with zero occurrences of symbols is known as an
empty string or Null String. It is represented by ε (epsilon) or ʌ.
▸ Power of ∑ : for {a, b}
▹ ∑ 0 = Set of all strings length 0 ={} or ε
▹ ∑ 1 = Set of all strings length 1 ={a, b}
▹ ∑ 2 = Set of all strings length 2 ={aa, ab, ba , bb}
▹ ∑ 3 = Set of all strings length 3 ={aaa, aab, aba , abb, baa, bab, bba, bbb}
▹ .
▹ .
▹ ∑ * = Set of all strings with any length including Null ={ε ,a, b, aa, ab,……….}
▹ ∑ + = Set of all strings with any length but not including Null ={a, b, aa, ab,……….}
8
Properties of String?
▸ Let Σ be an alphabet.
k
▸ Σ = the set of all strings of length k
▸ Kleene Closure= Σ* = Σ0 U Σ1 U Σ2 U …
▸ Positive Closure= Σ+ = Σ1 U Σ2 U Σ3 U …
9
What is Language?
▸ L is said to be a language over alphabet Σ, only if L ⊆ Σ*
▸ this is because Σ* is the set of all strings (of all possible length including 0) over
the given alphabet Σ
▸ Examples:
▹ Let L be the language of all strings consisting of n 0’s followed by n 1’s:
▹ L = {ε, 01, 0011, 000111,…}
▹ Let L be the language of all strings of with equal number of 0’s and 1’s:
▹ L = {ε, 01, 10, 0011, 1100, 0101, 1010, 1001,…}
10
Types of Language?
▸ Formal Languages
▸ Informal Languages
▹ Formal Languages: also known as syntactic languages. These languages
deals only with rules not with meanings. All Programming languages and
machine languages are formal languages.
▹ Informal Languages: also known as semantic languages. These languages
deals not only with rules but meanings also. All spoken languages are
informal languages like Urdu, English, Arabic
11
Defining Languages?
▸ The languages can be defined in different ways , such
as
1. Descriptive definition
2. Recursive definition
3. Regular Expressions(RE)
4. Finite Automaton(FA) etc.
12
Defining Languages?
▸ Descriptive definition:
The language is defined, describing the conditions imposed on
its words.
Examples:
The language L of strings of odd length, defined over Σ={a}, can be written as
▹ L={a, aaa, aaaaa,…..}
The language L of strings that does not start with a, defined over Σ ={a,b,c}, can be written
as
▹ L ={Λ, b, c, ba, bb, bc, ca, cb, cc, …}
The language L of strings ending in 0, defined over Σ ={0,1}, can be written as
▹ L={0,00,10,000,010,100,110,…}
13
Defining Languages?
▸ Descriptive definition:
The language is defined, describing the conditions imposed on
its words.
Examples:
The language EQUAL, of strings with number of a’s equal to number of b’s, defined over
Σ={a,b}, can be written as
▹ {Λ ,ab,ba,aabb,abab,baba,abba,…}
The language EVEN-EVEN, of strings with even number of a’s and even number of b’s,
defined over Σ={a,b}, can be written as
▹ {Λ, aa, bb, aaaa,aabb,abab, abba, baab, baba, bbaa, bbbb,…}
14
Defining Languages?
▸ Descriptive definition:
The language INTEGER, of strings defined over Σ={-,0,1,2,3,4,5,6,7,8,9}, can be written as
INTEGER = {…,-2,-1,0,1,2,…}
The language EVEN, of stings defined over Σ={-,0,1,2,3,4,5,6,7,8,9}, can be written as
EVEN = { …,-4,-2,0,2,4,…}
The language factorial, of strings defined over Σ={0,1,2,3,4,5,6,7,8,9} i.e.
{1,2,6,24,120,…}
15
Defining Languages?
▸ Descriptive definition:
The language PRIME, of strings defined over Σ={a}, as
{ap : p is prime}, can be written as
{aa,aaa,aaaaa,aaaaaaa,aaaaaaaaaaa…}
PALINDROME
The language consisting of Λ and the strings s defined over Σ such that Rev(s)=s.
It is to be denoted that the words of PALINDROME are called palindromes.
Example
For Σ={a,b},
PALINDROME={Λ , a, b, aa, bb, aaa, aba, bab, bbb, ...}
16
Defining Languages?
▸ Recursive definition:
▸ The following three steps are used in recursive definition
▹ Some basic words are specified in the language.
▹ Rules for constructing more words are defined in the language.
▹ No strings except those constructed in above, are allowed to be in the language.
Defining language of INTEGER
Step 1: 1 is in INTEGER.
Step 2: If x is in INTEGER then x+1 and x-1 are also in INTEGER.
Step 3: No strings except those constructed in above, are allowed to be in INTEGER.
Defining language of EVEN
Step 1: 2 is in EVEN.
Step 2: If x is in EVEN then x+2 and x-2 are also in EVEN.
Step 3: No strings except those constructed in above, are allowed to be in EVEN.
17
Defining Languages?
▸ Recursive definition:
▸ The following three steps are used in recursive definition
▹ Some basic words are specified in the language.
▹ Rules for constructing more words are defined in the language.
▹ No strings except those constructed in above, are allowed to be in the language.
Defining the language PALINDROME, defined over Σ = {a,b}
Step 1: a and b are in PALINDROME
Step 2: if x is palindrome, then s(x)Rev(s) and xx will also be palindrome, where s belongs to Σ *
Step 3: No strings except those constructed in above, are allowed to be in palindrome
