Unit-1 TOC (Theory of Computation)

Theory of Computation
UNIT – I
Theory of Computation 1
Vision of the Department
• To become renowned Centre of excellence in computer science
and engineering and make competent engineers & professionals
with high ethical values prepared for lifelong learning.

Mission of the Department
• M1- To impart outcome based education for emerging
technologies in the field of computer science and engineering.
• M2 - To provide opportunities for interaction between academia
and industry.
• M3 - To provide platform for lifelong learning by accepting the
change in technologies
• M4 - To develop aptitude of fulfilling social responsibilities.
Course Objectives
CO1: Examine Finite Automata and Regular Expression.
CO2: Classify regular sets of Regular Grammars.

CO3: Categorize Context Free Language and Design Pushdown
automata.
CO4: Design Turing machine, compare Chomsky hierarchy
languages and analyze Linear bounded automata.
CO PO Mapping
Course

Semester
Objectiv PO1
PO
PO4
PO PO PO
PO8 PO9
P O 10 P O 11 P O 12
es P O2 3 5 6 7

CO1 H L M H M L L M L L L L

CO2
H M H H L L M M H M L M

CO3
IV H M H H L L M L M M M L

CO4
L M L H M L H M L L H H
Introduction
TOC is an accumulation of mathematicians work to make a
model for a machine that can do thinking and calculations.
The concept of a machine at early 1900 was a device that
does physical work.
Scientists effort started with a machine that can do specific
calculations like encrypting text using specific set of steps.
Alan Turing believed he could invent a generic machine
that can solve more than one type of problems.
History
It started before World War II, Germans army used
Enigma encryption.
Alan Turing and many mathematicians tried to break the
Enigma encryption.
Their efforts resulted in emergence of a mechanical
device that was dedicated for deciphering Enigma
encrypted messages.
As a result many German submarines were attacked and
destroyed.
Introduction
Von Newman, Alan Turing and many others continued working
on creating a model for a generic machine that can solve
different types of problems.
The accumulation of their work resulted in emergence of a
collection of theorems called theory of computation.
TOC emerged to give answers for
“What are the fundamental capabilities and limitations of
computing machines?”
Most powerful and modern super computers can NOT solve
some problems!!
No matter how much processors get fast , no matter how
much memory can be installed; the unsolved problems
remain unsolved!
We might need life time of the universe to find prime
factors of a 500-digits number!
Why we still need TOC?
Technologies become obsolete but basic theories remain
forever.
TOC provides tools for solving computational problems like
regular expressions for string parsing and pattern matching.
Studying different types of grammars like CFG would help
in many other areas like compilers design and natural
language processing.
Branches of TOC
Branches of TOC
TC consists of:
1. Automata theory: mathematical models for
computational problems such as pattern recognition and
other problems.
2. Computability theory: computational models and algorithms
for general purpose.
3. Complexity theory: classifying problems according to their
difficulty.
Mathematical Notations
and
Terminology
Sets-[1]
A set is a group of elements
represented as a unit.
For example
S ={a, b, c} a set of 3
elements
 Elements included in curly brackets { }

a  a belongs to S
S  f does NOT belong to
f S Theory of Computation 13
Sets-[2]
If S ={a, b, c}
and
T = {a, b}
Then
T  S
T is a subset of S
T S ={a, b}
 intersects S ={a, b}
T
Venn diagram for S and T

T  S ={a, b, c}
T Union S ={a, b, c}Theory of Computation 14
Sequences and Tuples
A sequence is a list of elements in some
order. (2, 4, 6, 8, ….) parentheses
A finite sequence of K-elements is called k-
tuple.
(2, 4) 2-tuple or pair
(2, 4, 6) 3-tuple
A Cartesian product of S and P (S x P)
is a set of 2-tuples/pairs (i, j)
where i  S and j  P
Example for Cartesian Product
Example (1)
If N ={1,2,…} set of integers; O ={+, -}
N x O ={(1,+), (1,-), (2,+), (2,-), …..}
Meaningless?
Example (2)
N x O x N={(1,+,1), (1,-,1), (2,+,1),
(2,-,2), …..}
Does this make sense?
Continue Cartesian Product
Example (3)
If A ={a, b,…, z} set of English alphabets;
A x A ={(a, a), (a, b), ..,(d, g), (d, h), …(z,
z)} These are all pairs of set A.
Example (4)
If U={0,1,2,3…,9} set of digits then U x U x
U
={(1,1,1), (1,1,2),...,(7,4,1), ….., (9,9,9)}
Continue Cartesian Product
Example (5)
If U={0, 1, 2, 3…, 9} set of digits then
U x… x U ={(1,..,1), (1,..,2),...,(7,..,1), ...,
(9,..,9)}
n
Can be written as Un
Relations and functions
A relation is more general than a function.
Both maps a set of elements called domain
to another set called co-domain.
In case of functions the co-domain can be
called range.
R : D C
A relation has no restrictions.
f : D R
A function can not map one element to two
differnet elements in the range.
Surjective Bijective
function
 T Sfunction
P1 T
P2
s1 t1
t1
P3 s
t2 t2
P4 2
Pn t3 s
Many planes fly at t
Only 3one plane lands on
the same time one runway at a time
3
What is the use of functions in TC?
Helps to describe
the
transition function that D R
transfer the computing s1 s2
device from one state to
another. s2
Any computing
s3
device must have
s3
clear states. shal
t
Graph
Is asvisual
1
representation of a set
and a relation of this set
over itself.
G = (V, E) 2 4
V ={1, 2, 3, 4, 5}
E = {(i, j) and (j, i)| i, j
belongs to V}
E is a set of pairs ={(1, 3),
(3, 1) …(5, 4), (4, 5)} 5 3
Graphs Construct
Is there a formal language
1
to describe a graph?
G =(V, E)
Where : 2 4
V is a set of n vertices
={i| i < n-1}
E is a set of edges. Each edge 5 3
is a pair of elements in V
={(i, j), (j, i)|i, jV}
or={(i, j) |i, j  V }
Definitions
 Alphabet) : a finite set of letters, denoted

Letter: an element of an alphabet 
Word: a finite sequence of letters from
the alphabet 
 (empty string): a word without letters.
Language  * Kleene ‘s Star: the set of
all words on 
Strings and languages
A string w1 over an alphabet Σ is a finite
sequence of symbols from that
alphabet.
1. Σ: is a set of symbols
i.e. {a, b, c, …, z} English letters;
{0,1, 2,…,9,.} digits of Arabic numbers
{AM, PM}different clocking system
{1, 2, …, 12}hours of a clock;
Strings -2
2.1 String: is a sequence of Σ (sigma) symbols
Σ Σ to the Example Description
power?
{a, b, c, …, z} apple English
string
{0,1, 2,…,9,.} 35 the oldest
age for girls
{AM, PM} PM clocking

system
{1, 2, …, 12} 1
Σ or Σ
2
12 a specific
hour in the
day 26
Strings - 3
2. Empty String is Λ (Lamda) is of length zero
0
Σ =Λ
3. Reverse(xyz) =zyx
4. Palindrome is a string whose
reverse is identical to itself.
If Σ = {a, b} then
PALINDROME ={Λ and all strings x such
that reverse(x) = x }
radar, level, reviver, racecar,
madam, pop and noon.
Strings - 4
2.5 Kleene star * or Kleene closure
is similar to cross product of a set/string over itself.
*
If Σ = {x}, then Σ = {Λ x xx xxx ….}
+
If Σ = {x}, then Σ = {x xx xxx ….}
If S = {w1 , w2 , w3 } then
*
S ={Λ, w , w , w , w w , w w , w w , ….}
1 2 3 1 1 1 2 1 3
+
S ={w 1 , w2 , w3 , w1 w1 , w1 w2 , w1 w3 , ….}
Note1: if w =Λ, then Λ S +
3

Note2: S =
*
**
S Theory of Computation 28
Finite Automata FA
It started as a simple automatic device with no memory.
We still need it to study how to model a device and
model its capability.
Its goal is to act as a recognizer for specific a
language/pattern.
Any problem can be presented in form of a decidable
problem that can be answered by Yes/No.
A problem can be concatenated to one of its
possible solutions and can be seen as a string that
matches a pattern.
Hence FA (machine with limited memory) can solve any
problem. Theory of Computation 29
Deterministic Finite Automata DFA
FA = “a 5-tuple “ (Q, Σ, , q0, F)
1. Q: {q0, q1, q2, …} is set of states.
2. Σ: {a, b, …} set of alphabet.
3. (delta): represents the set of transitions that
FA can take between its states.
: Q x Σ→Q
Q x Σ to Q, this function:
 Takes a state and input symbol as arguments.
 Returns a single state.
4. q0  Q is the start state.
5. F  Q is the set of final/accepting states.

Transition function
 : Q x Σ→Q
 Maps from domain of (state, letter) to range of states.
(q0, a)
q1
(q0, b)
(q2, b) q2
(q1, b)
q3
Theory of Computation 31 3
1
Renaming function to λ (Lamda)
 Lets name it Conditional consumption instead of
transition
 λ: Q x Q → Σ
 Maps from domain of (states, states) to range of
letters.
Allows more than one link (q0, q1) a Σ
from domain to
codomain
Not recommended (q2, q3)
b
(q1, q3)
Dr. Hussien M. Sharaf Theory of Computation c 32 3

2
How does FA work?
1. Starts from a start state.
2. Loop
Reads a letters from the input
3. Until input string finishes
4. If the current state is a final state then
Input string is accepted.
5. Else
Input string is NOT accepted.
 But how can FA be designed and represented?
Representation of FA: Graph
States= nodes
Starting state denoted by –
Final state(s) denoted by +
Transition function =directed arrows
connecting states.
Build an FA for RE “a*b(a+b)*”
a a,b
- +
S1 2
b S
Representation of FA: Table
“-” sign for
start state a b input symbols
-s1 s1 s2
Final states +s2
Indicated s2 s2
by “+”
Rows = states
Example1.1
Build an FA that accepts only
Saab
1 S2 S3 S4
b
- a a
+
a b
b a a,b S1 S2 S5
b
S2 S3 S5
S5 S3 S5 S4
a,b S4 S5 S5
Example1.2
Build an FA that accepts only
Saab
1 S2 S3 S4
b
- a a
+
a b
S1 S2 ?
S2 S3 ?
S3 ? ?
S4 ? ?
Ex2
(a+b)*
a, b
FA accepting nothing
1. FA with no final states b
-
a a,b
2. FA with disconnected graph. Start state does not
have a path to the final state.
- +
a b
a,b
Ex3
All words with even count of
letters.
((a+b)(a+b))*
a, b
1±
2
a, b
Ex4.1
All words that start with
“a”
a(a+b)*
a,b b
b 2 2
1- 1-
a 3+ a 3+ a,b
a,b
Does not accept all inputs
Ex4.2
All words that start with
“a”
a(a+b)*
a,b
b 2
1-
a a,b
3+
Special accept state for string “a”, might give

better performance in hardware
implementation
Ex5
All words that start with triple
letter
(aaa+bbb)(a+b)*
a a a
2 3
1- 6+ a,b
4 5
b b b
Ex6 +
a
a,b a,b
-
a,b
b
5
{aa, ba, baba, aaaa, bbba, abba,

aaabaa, …}
All words with even count of letters and
ends with “a”. (a+b)a ((a+b)a
(b(a+b)a)* )* Theory of Computation 44
Ex7
a,b
{aa, ba, baba, aaaa, ab, bb, bababa, aaba, …}

All words with even count of letters having “a”
in an even position from the start, where the first
letter is letter number one. (a+b)a((a+b)a)*
Ex8
Consider the following FA:
•Whenever aa exists, the first
“a” must take us to state 4
or state 2.
•Either way, the next a takes us

to state 4. Similar situation with
“bb”.
In summary: this FA accepts strings that have a
double letter in them.
(a + b)*(aa + bb)(a + b)*
Ex9
Consider the following FA:
•Accepts all words with b as the
third letter and reject all other
words.
•A word that has fewer than

three letters fails.
RE1: (aab + abb + bab +
bbb)(a + b)*
OR :(a + b)(a + b)(b)(a + b)* = (a + b)2 b (a + b)*
Notice that this last formula is not strictly speaking
a regular expression, since it uses the symbol “2”
Have you see any memory?
Ex10
All strings that end in ab.
Do we need a memory to remember the last two letters?
a
a b
b
b
a
…
…
- b
+
a
b
b
…
…
b
b
Ex11
Even-Even :
All the words that end in
state 3 have an even number
of b's but an odd number of
a's.
All words that end in state
4 have an odd number of
a's and an odd number of
b's.
Any EVEN-EVEN words
must end in state 1 and be
accepted.
Automaton
temporary memory
Automaton
input memory
CPU
output memory
Program memory
Finite Automaton
Input
String
Output
Finite String
Automaton
Different Kinds of Automata
Automata are distinguished by the temporary
memory:
• Finite Automata: no temporary memory
• Pushdown Automata: stack
• Turing Machines: random access
memory
Power of Automata
Finite Pushdown Turing

Automata Machine
Automata
Non Deterministic Finite Automata NFA
There is a fixed number of states but we can

be in multiple states at one
• time.
•NFA = “a 5-tuple “ (Q, Σ, , q0, F)
• Q A finite set of states
• Σ A finite input alphabet union {Λ}
• q 0 The initial/starting state, q is in Q
0
• F A set of final/accepting states, which is a

subset of Q
• δ A transition function, which is a total
function from Q x Σ to 2 , this function:
Q
NFA
A finite automaton is deterministic if
 It has no edges/transitions labeled
with epsilon/lamda.
 For each state and for each symbol in the
alphabet, there is exactly one edge labeled with
that symbol.
NFA
 NFA travels all possible paths, and so it remains in many states at once.
As long as at least one of the paths results in an accepting state, the NFA
accepts the input.
Alphabet = {a}
q1
q2
q0
q Theory of Computation 56
NFA
Alphabet = {a
}
Two choices
q1 q2
q0
q3
NFA
Alphabet = {a
}
Two choices
q1 q2 No transition
q0
q3 No transition
NFA
An NFA accepts a string:
if there is a computation of the NFA
that accepts the string
i.e., all the input string is processed and
the automaton is in an accepting state
NFA Acceptance Example 1
q1 q2
q0
q3
NFA
q1 q2
q0
q3
NFA
q1 q2 “accept”
q0
q3 “reject”
NFA
aa is accepted by the NFA:
“accept”
q1 q2 q1 q2
q0 q0
q3 “reject”
q3
because this
computation this computation
is ignored
accepts aa
NFA
An NFA rejects a string:
if there is no computation of the NFA
that accepts the string.
For each computation:

• All the input is consumed and the
automaton is in a non final state
OR
• The input cannot be consumed
(indecidable input)Theory of Computation 64
37
NFA
is rejected by the NFA:
“reject”
q1 q2 q1 q2
q0 q0
q3 “reject”
q3
All possible computations lead to rejection

NFA
is rejected by the NFA:
“reject”
q1 q2 q1 q2
q0 q0
q3 “reject”
q3
All possible computations lead to rejection

Deterministic and
Nondeterministic Automata
Deterministic Finite Automata (DFA)
One transition per input per state
No -moves
Nondeterministic Finite Automata (NFA)
Can have multiple transitions for one input in a given
state
Can have -moves
Assignment 4
Proof that NFA and DFA are equivalent.
 Constructive type of proofs might be the most
appropriate.
 Be formal and simple. Don’t exceed 2-3 slides.
 You might study the proof from “Sipser” book
or “Models Of Computation”.
 Your answer might be delivered in form of
slides
 You will present your slides in 5-7 minutes.
Regular Expressions
A RE is a language for describing simple
languages and patterns.
Algorithm for using RE
1. Define a pattern: S1StudentnameS2
2. Loop
Find next pattern
Store StudentName into DB or encrypt StudentName
Until no match
REs are used in applications that involve file
parsing and text matching.
Many Implementations have been made for RE.
6
9
RE by C++ Boost library
//Pattern matching in a String
// Created by Flavio Castelli <[email protected]>
// distrubuted under GPL v2 license
#include <boost/regex.hpp>
#include <string> Please check
int main() [http://flavio.castelli.name/regexp-with-boost]
{ boost::regex
("bg|olug",boost::regex_constants::icase|
pattern
boost::regex_constants::perl);
std::string stringa ("Searching for BsLug");
if (boost::regex_search (stringa, pattern,

boost::regex_constants::format_perl))
printf ("found\n");
else printf("not found\n");
return 0; }
7
0
RE by C++ Boost library
//Substitution
// Created by Flavio Castelli <[email protected]>
// distrubuted under GPL v2 license
#include <boost/regex.hpp>
#include <string> int main() Please check [http://flavi
o.castelli.name/regexp-with-boost]
{boost::regex pattern
("bok",boost::regex_constants::icase|
boost::regex_constants::perl);
std::string stringa ("Searching for bok");
std::string replace (“book");
std::string newString;
newString = boost::regex_replace (stringa,
pattern, replace);
printf("The new string is:
|%s|\n",newString.c_str());
return 0; }
7
1
RE by C++ STL needs extra feature pack
#include <regex>
#include <iostream>
#include <string>
bool
is_email_valid(const
std::string& email) {
// define a regular expression
const std::tr1::regex pattern("(\\w+)(\\.|_)?(\\
w*)@(\\w+)(\\.(\\w+))+");
// try to match the string with the regular expression
return std::tr1::regex_match(email, pattern); }
Please check
http://www.codeguru.com/cpp/cpp/cpp_mfc/stl/article.php/c15339
72
RE by C++ STL
#include <regex>
#include <iostream>
#include <string>
bool
is_email_valid(const
std::string& email) {
// define a regular expression
const std::tr1::regex pattern("(\\w+)(\\.|_)?(\\
w*)@(\\w+)(\\.(\\w+))+");
// try to match the string with the regular expression
return std::tr1::regex_match(email, pattern);
}
Please check 73
RE by C++ STL
std::string str("abc + (inside brackets)dfsd");
std::smatch m;
std::regex_search(str, m, std::regex(“b"));
if (m[0].matched)
std::cout << "Found " << m.str(0) << '\n';
else
std::cout << "Not found\n“;
Please check
74
Other code samples
Other samples can be check at:
Boost Library
1. http://stackoverflow.com/questions/5804453/c-regular-expressions-
with-boost-regex
2. http://www.codeproject.com/KB/string/regex .aspx
3. http://www.boost.org/doc/libs/1_43_0/more/getting_started/window
s.html#build-from-the-visual-studio-ide
STL Library
4. http://www.codeproject.com/KB/recipes/rexsearch.aspx
5. http://www.codeguru.com/cpp/cpp/cpp_mfc/stl/article.php/c15339
[recommended]
3. http://www.microsoft.com/download/en/confirmation.aspx?id=6922
[feature pack VS2008 Pack]

4. http://channel9.msdn.com/Shows/Going+Deep/C9-Lectures-
Stephan-T-Lavavej-Standard-Template-Library-STL-8-of-n [Video] 75
RE Rules -1
1.Let ∑ ={x}, Then L = ∑*
In RE, we write x*
2.Let ∑ ={x, y}, Then L = ∑*
In RE, we write (x+y)*
3. Kleene’s star “*” means any combination of letters
of length zero or more.
76
RE Rules -2
Given an alphabet ∑, the set of regular expressions is defined
by the following rules.
1. For every letter in ∑, the letter written in bold is a
regular expression. Λ is a regular expression.
2. If r1 and r2 are regular expressions, then so are:
1. (r1)
2. r1 r2
3. r1+r2
4. r1*
NOTE: r1+ is not a RE
3. Nothing else is a regular expression.
77
RE-1
Example 1
∑ ={a, b}
- Formally describe all words with a followed by
any number of b’s
L = a b* = ab*
- Give examples for words in L
{a ab abb abbb …..}
78
RE-2
Example 2
∑ ={a, b}
- Formally describe the language that contains
nothing or words starts with a where any a must be
followed by one or more b’s
L = (abb*)* OR (b+ab)*
{Λ ab abb abababb …..}
79
RE-3
Example
∑ ={a, b}
- Formally describe all words with a followed by one
or more b’s
L = a b+ = abb*
{ab abb abbb …..}
80
RE-4
Example
∑ ={a, b, c}
- Formally describe all words that start with an a
followed by any number of b’s and then end with c.
L = a b* c
{ac abc abbc abbbc …..}
81
RE-5
Example
∑ ={a, b}
- Formally describe all words where a’s if any come
before b’s if any.
L = a* b *
{Λ a b aa ab bb aaa abb abbb bbb…..}
NOTE: a* b* ≠ (ab)*
because first language does not contain abab but second

language has.
Once single b is detected then no a‘s can be added
82
RE-6
Example
∑ ={a}
-Formally describe all words where count of a is odd.
L = a(aa)* OR (aa)*a
{a aaa aaaaa …..}
83
RE-7.1
Example
∑ ={a, b, c}
- Formally describe all words where single a or
c comes in the start then odd number of b’s.
L = (a+c)b(bb)*
{ab cb abbb cbbb …..}
84
RE-7.2
Example
∑ ={a, b, c}
- Formally describe all words where single a or c
comes in the start then odd number of b’s in case of
a and zero or even number of b’s in case of c .
L = ab(bb)* +c(bb)*
{ab c abbb cbb abbbbb …..}
85
RE-8
Example
∑ ={a, b, c}
- Formally describe all words where one or more a
or one or more c comes in the start then one or
more b’s.
L = (a+c) + b+= (aa*+cc*) bb*
{ab cb aabb cbbb …..}
86
RE-9
Example
∑ ={a, b}
-Formally describe all words with length three.
L = (a+b) 3 =(a+b) (a+b) (a+b)

- List all words in L
{aaa aab aba baa abb bab bba bbb}
-What is the count of words of length 4?
16 = 24
-What is the count of words of length 44?
244
87
88
RE-10.1
Example
∑ ={a, b}, What does L describe?
- L = (a+b)* a(a+b) *
Any string of a's and b's

Any string of a's and b's
Single
a
- Give examples for
words in L
{a ab aab bab abb
…..}
89
RE-10.2
abbaab can parsed in 3 ways
a abb a abba a
bbaab ab b
abb a abba a b
Λ a bbaab
ab
90
RE-11
Example Page 38 Cohen
∑ ={a, b}
- Formally describe all words with at least two a's.
1) L = b*ab*a(a + b)*
Start with a jungle of b's (or no b's) until we find
the first a, then more b's (or no b's), then the
second a, then we finish up with anything.
{abbbabb aaaaa bbbabbbbabab…..}
91
RE-12
Example
∑ ={a, b}
- Formally describe all words with exactly two a's.
1) L = b*ab*ab*
{aab, baba, and bbbabbbab …..}
To make the word aab, we let the first and
second b* become Λ and the last becomes b
92
RE-13.1
Example
∑ ={a, b}
- Formally describe all words with least one a and least
one b.
1) L = (a + b)*a(a + b)* b(a + b)*
= (anything) a(anything) b(anything)
But (a+b)*a(a+b)*b(a+b)* expresses all words except
words of the form some b’s (at least one) followed by
some a’s (at least one). bb*aa*
93
RE-13.2
2) L =(a+b)*a(a+b)*b(a+b)* + bb*aa*
Thus: (a+b)*a(a+b)*b(a+b)* + (a+b)*b(a+b)*a(a+b)*
= (a+b)*a(a+b)*b(a+b)* + bb*aa*
Notice that it is necessary to write bb*aa* because
b*a* will admit words we do not want, such as
aaa.
Does this imply that

(a+b)*b(a+b)*a(a+b)*= bb*aa*??
False Left side includes the word aba, which the
expression on the right side does not.
94
95
Regular Languages
A language that can be defined by a RE is called a
regular language.
1. If L1 and L2 are regular languages then
L1 + L2 , L1 L2 and L1* are also regular languages.

(L
2. If L is a regular language then L’
complement) is also a regular language.
L’ : is the language that is not accepted by r where r
is the RE that accepts language L.
Note: (L’)’ =L and (r’)’ =r
96
Regular Languages (cont.)
3. If L1 and L2 are regular languages then
L1 ∩ L2 is also a regular language.
L1 =words starting with a
r1 =a(a+b)*
L2 =words ending with a
r2 = (a+b)*a
L3 =L1 ∩ L2 = a(a+b)*a
L3 = words that start and end with a.
97
Assignment 3
1. Proof that: If L1 and L2 are regular languages then
L1 + L2 , L1 L2 and L1* are also regular languages.
2. State which type of proofs you have used.
98
How powerful is RE?
RE can not express some languages such
as plaindrome strings an bn .
How can we prove that a language L is not regular?
Prove that there is no FA or RE that accepts L
Solution: use a Lemma called pumping Lemma.
It depends on pumping a string into a template. If the
string could not fit into the template then the string
is not an RE.
99
What is Pumping Lemma?
Formal Definition ”The pumping lemma for regular languages is a lemma that
makes use of a property shared by all regular languages RL. The property specifies
that any string w that belongs to a Regular Language L can be broken into xyz ”
Formal Statement” Let L be a RL, then there exists some constant

integer n≥ 1 (that depends on L) such that any string w in L with |w|≥ n
(where n is a “pumping length”) can be written as
w = xyz with substrings x, y and z, such that
1. y ≠ε; OR |y| ≥ 1; OR y is not empty
2. |xy|≤ n,
3. For every i ≥ 0, any xyiz ∈ L
Example 1
Use pumping Lemma to prove that L|a|(odd) is a RL. Any
word w of L|a|(odd) have count of a is odd.
L = {a, aaa, aaaaa, …}
Solution
w = xyz, where
1. y = aa
2. |xy|<= n where x is a , z is ε, where n=3
3.For every i ≥ 0, any xyiz ∈ L
Therefore a(aa)i ∈ L
Note that Point#3 covers the
word with length 1 ”a”
Example 1 (cont.)
Use pumping Lemma to prove that L|a|(odd) is a RL. Any
word w of L|a|(odd) have count of a is odd.
L = {a, aaa, aaaaa, …}
Can you find another solution?
How to prove that a given
language L in not regular ?
Assume the opposite: L is regular
The pumping lemma should hold for L
Use the pumping lemma to obtain a contradiction
Therefore, L is not regular
Example 2
prove that the language anbn is not regular
From the pumping lemma we can write
w = am bm in form of xyz that satisfies the
three conditions of the pumping Lemma
m m
w xyz  
abm m a...aa...aa...ab...b
x k
z
y
Thus: y  a , 1 k
k
Example 2
Solution
Is there any valid n?
w = xyz, where
1. y = a
2. |xy|<= n where x
is a j, y is ak for
any j, a..a(a)
Therefore k k bm ∈ L m m
3. For every i ≥ 0,
any x yi z ∈ Lw  
a...aa...aa...ab...b
x k
z
y
xyz  ambm
Example 2
From the Pumping Lemma:
1. Since i could be zero then xz ∈ L
[Rule3]
2. y ≠ ε
[Rule1]
3. In case i =0, x must have same the length
as z which is indicated by m
4. In cases i=k where k >=1, |xy| must be
equal m but since |x| is m then the
formula becomes m+k=m
Example 2
Thus: • m+k m
•Isxy k
z a...aa...aa...aa...ab...b
there such k
L
integer where m+k=m x ……. y
?
y
CONTRADICTION!!!
m+k≠m
Therefore: Our assumption that L is a regular
language is not true
Conclusion: L is not a regular language

Unit-1 TOC (Theory of Computation)

Uploaded by

Copyright:

Available Formats

Unit-1 TOC (Theory of Computation)

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Unit-1 TOC (Theory of Computation)

Uploaded by

Copyright:

Available Formats

Theory of Computation

CO2: Classify regular sets of Regular Grammars.

 Elements included in curly brackets { }

Venn diagram for S and T

{AM, PM} PM clocking

5. F  Q is the set of final/accepting states.

Dr. Hussien M. Sharaf Theory of Computation c 32 3

Special accept state for string “a”, might give

{aa, ba, baba, aaaa, bbba, abba,

{aa, ba, baba, aaaa, ab, bb, bababa, aaba, …}

•Either way, the next a takes us

•A word that has fewer than

Finite Pushdown Turing

There is a fixed number of states but we can

• F A set of final/accepting states, which is a

For each computation:

All possible computations lead to rejection

All possible computations lead to rejection

if (boost::regex_search (stringa, pattern,

[feature pack VS2008 Pack]

because first language does not contain abab but second

L = (a+b) 3 =(a+b) (a+b) (a+b)

Any string of a's and b's

Does this imply that

L1 + L2 , L1 L2 and L1* are also regular languages.

Formal Statement” Let L be a RL, then there exists some constant

You might also like