Introduction to Theoretical Computer Science
Automata theory
(also known as Theory Of Computation) is a theoretical branch of
Computer Science and Mathematics, which mainly deals with the logic of
computation with respect to simple machines, referred to as automata.
Automata enables the
scientists to understand how machines compute the functions and solve problems.
The main motivation behind developing Automata Theory was to develop methods to
describe and analyze the dynamic behavior of discrete systems.
Automata is originated
from the word “Automaton” which is closely related to “Automation”.
Now, let’s understand
the basic terminologies, which are important and frequently used in Theory of
Computation.
What
is Theory of Computation?
• What
is Theory?
èTheory
define as capabilities, limitation of those machine.
·
What is
Computation?
èComputation
is calculation, solving, making decision or any task done by computer or any
machine.
Purpose
of theory of computation-
“Develop formal mathematical models
of computation that reflect real-world computers.”
Basic
Concept:
• Symbol: Symbols
are indivisible objects or entity that cannot be defined. Symbol is the
smallest building block, which can be any alphabet, letter or any picture.
Example:
digit, letter
• Alphabets (Σ): Alphabets
are finite set of symbols.
Example:
Σ = {0, 1} is an alphabet of binary digits
Σ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} is an alphabets
of decimal digits
Σ = {a, b, c}
Σ = {A, B, C, ………,Z}
• String
: String is a finite sequence of
symbols from someone alphabet(Σ). String
is generally denoted as w.
Example
:
00011100 è is a string from the binary alphabet Σ {0, 1}
aabcc
è is a string from the alphabet Σ {a, b, c}
9862
è is a string over alphabet Σ {0,1,2,3,4,5,6,7,8,9}
·
Null string
(ϵ) : A string having no symbol is called Null string
and is denoted by ϵ
·
Length of a
string ( |w| ) : The length of a string is number of symbols in the
string.
Example:
w =
totalmcq |w|=8
w = 001100 |w|=6
w = ϵ
|w|=0
•
Powers of ‘ Σ ‘ or Power of Alphabet:
If Σ is an alphabet, then Σk is the set
of all strings of length k.
Example
:
Let, Σ = {0,1} then
Σ0 = { }
Σ1 = {0, 1}
Σ2 = {00, 01, 10, 11}
Σ3 =Σ2 Σ1
=
{00, 01, 10, 11} {0, 1}
= {000, 001, 010, 100, 011, 101, 110, 111}
Prefix and Proper prefix of a string
•
Prefix of a string is any number of leading symbols of that
string.
Example : x = abc
prefixes of x = { ϵ, a, ab, abc }
•
The prefix
other than the string itself is called as proper prefix.
Example : x = abc
proper prefix of x = { ϵ, a, ab }
Suffix
and Proper suffix of a string:
·
Suffix of a string is
any number of trailing symbols in it.
Example: x = abc
Suffix
of x = { ϵ,
c, bc, abc }
The suffix other than the string itself is called a
proper suffix.
Example
: x = abc
Proper
suffix of x = { ϵ,
c, bc }
•
Language: A language is a set of strings, chosen
from some Σ* or we can say- ‘A language is a subset of Σ* ‘. A
language which can be formed over ‘ Σ ‘ can
be Finite or Infinite.
Example:
L1 = {set of all strings of length 2}
= { aa,
ab, ba, bb} è finite
L2 = {set of all strings which starts
with ‘a’}
= { a, aa, ab, aba,aaa, abb,…………….} è Infinite
• Formal Language :
The word formal refers to the fact that all the
rules for the language are explicitly stated in terms of what strings of symbol
can occur and which are valid sentence.
Example: language over alphabet {a, b} having equal number
of a and b.
Σ* = { ϵ, ab, ba,
abab, baab, aabb,…………….}
If we exclude ϵ, then
Σ+ = { ϵ, ab, ba, abab, baab, aabb,…………….}
Operations on Languages
There are three operations which we can apply on
Languages:
1. Union :
Given language L1 and L2 we define their union to
be the language is
L1 U L2 = { x | xϵ L1 or x ϵ L2 }
2. Concatenation :
Given languages L1 and L2 we
define their concatenation to be the language is
L1L2= {xy | x ϵ L1 and y ϵ L2}
Ex. L1 = { hello } and L2 =
{world} then L1L2 = {helloworld}
3. Kleene Closure (*)
: It
is denoted by L* and is defined as
L* = ∪ Li
i=0
Ex. If ∑ = {a, b}, L* = { ϵ, a, b, aa, ab, ba, bb,………..}
4. Positive
Closure : It is denoted
by L+ is defined as,
∞
L+ = ∪ Li
i=1
Regular Languages: A
language is regular if it can be expressed in terms of regular expression.
Regular Expressions
Regular Expressions are used to denote regular languages. An expression is
regular if:
·
ɸ is a regular expression for
regular language ɸ.
·
ɛ is a regular expression for
regular language {ɛ}.
·
If a ∈ Σ (Σ represents the input alphabet), a is regular expression with
language {a}.
·
If a and b are regular expression, a
+ b is also a regular expression with language {a, b}.
·
If a and b are regular expression,
ab (concatenation of a and b) is also regular.
·
If a is regular expression, a* (0 or
more times a) is also regular.
Ex.1. Define the language such that all words begin and end with
‘a’ and in between any word using ‘b’, using regular expression
è Regular expression is
a
b*a + a
Ex.2. Describe the set of all strings of a’s and b’s ending with
ab.
è In given language we can have zero or
more occurrences of ‘a’ or ‘b’ followed by ‘ab’.
So, (a+b)* for zero more occurrences of
‘a’ or ‘b’ and concatenate ‘ab’ at the end.
Therefore, regular expression is (a+b)*ab
Ex.3. L={ ɛ,11,1111,111111,………}
What is the regular expression of L?
è In given set of strings any string in L
will be either ɛ
or string of even number of 1’s.
So Regular
expression of L is (11)*
Ex.4. Write a regular expression for language contains atleast
one a and atleast one b.
è r = [(a+b)* a (a+b)* b (a+b)*] + [(a+b)*
b (a+b)* a (a+b)*]
Ex.5. Write a regular expression for language must containing
each string of even length over the alphabet {0}
è r = (00)+
Ex. 6.
Describe the language L= {anbn | n ≥ 1}
è ∑ = {a, b}
L = { ab, aabb, aaabbb, ……………….}
The language
contain equal number of a’s followed by equal number of b’s.
Ex. 7. Find
the language of the regular expression (a+b)*
è L = {
ɛ, a, b, ab, ba, aa, bb, aab, aabb,……….}
Ex.
8. Find regular expression of language staring
with aa and ending with bb
over alphabet {a, b}
è r = aa (a+b)* bb
Ex.9.
Find regular expression of that language having string not containing substring
01 over alphabet {0,1}
è r = 1* 0*
Ex.10.
Find regular expression of the language ending with 011 over alphabet
{0,
1}
è r=
(0+1)*011
Ex.11.
Write regular expression for a language consists of string having length
divisible by 3 over { a }
è r = ( aaa )*
Ex.12.
Find regular expression of the language consists of string over {0, 1} whose 3rd
digit from right end is always 1.
=è r = (0+1)*
1(0+1)(0+1)
Ex.13.
Write regular expression for a language consisting of string such that total
number of b’s in each string is divisible by 3 over {a, b}
è L = { ɛ, a,
aa, abbb, bbba, ababab……}
r = (a*ba*ba*ba*)* + a*
Ex.
14. Write regular expression for a language of string with total number of 0’s
are even over {0, 1}
è r = 1* +
(1*01*01*)*
Two regular expressions P and Q are equivalent and written as P = Q if P
and Q represent the same set of strings.
Following are the identities for regular expressions
which are useful for simplification of regular expression
1. ɸ + R = R
2. ɸR = Rɸ = R
3. ɛR = Rɛ = R
4. ɛ* = ɛ and ɸ* = ɛ
5. R + R = R
6. R*R* = R*
7. RR* = R*R = R+
8. (R*)* = R*
9. ɛ + RR* = R* = ɛ + R*R
10.
(PQ)*P = P(QP)*
11.
(P + Q)* = (P*Q*)* = (P* + Q*)
12.
(P + Q)R = PR + QR
13.
R(P + Q) = RP + RQ
In order to find out a regular expression of a
Finite Automaton, we use Arden’s Theorem
along with the properties of regular expressions.
Arden’s
Theorem: Let P and Q be
two regular expressions. If P does not contain null string,
then R = Q + RP has a unique solution that is R = QP*