Transcript COSC 3340: Introduction to Theory of Computation

COSC 3340: Introduction to Theory of
Computation
University of Houston
Dr. Verma
Lecture 7
1
Lecture 7
UofH - COSC 3340 - Dr. Verma
Are all languages regular?


Ans: No.
How do we know this?
–

Let C(DFA) = {M | M is a DFA}.
–

C(DFA) is a countable set. Why?
Let AL = { L | L is a subset of *}.
–
2
Ans: Cardinality arguments.
AL is uncountable.
Lecture 7
UofH - COSC 3340 - Dr. Verma
Cardinality

Def: A set is countable if it is
(i) finite or
(ii) countably infinite.

Def: A set S is countable infinite if there is a bijection
from N to S.
–

Def: A set that is not countable is uncountable.
–
3
Note: Instead of N to S we can also say S to N.
N = {0, 1, 2, 3, ...} -- the set of natural numbers.
Or, any infinite set with no bijection from N to itself.
Lecture 7
UofH - COSC 3340 - Dr. Verma
Examples
1. The set of chairs in this classroom is finite.
2. The set of even numbers is countably
infinite.
3. The set of all subsets of N is uncountable.
–
4
Notation: 2N
Lecture 7
UofH - COSC 3340 - Dr. Verma
Exercises

What is the cardinality of?
1. Z - the set of integers.
2. N X N = {(a,b) | a, b in N}.
3. R - the set of real numbers.
5
Lecture 7
UofH - COSC 3340 - Dr. Verma
Pumping Lemma



6
First technique to show that specific given
languages are not regular.
Cardinality arguments show existence of
languages that are not regular.
There is a big difference between the two!
Lecture 7
UofH - COSC 3340 - Dr. Verma
Statement of Pumping Lemma
If A is a regular language, then there is a
number p (the pumping length) where, if s is
any string in A of length at least p, then s may
be divided into three pieces, s = xyz,
satisfying the following conditions:
1. for each i  0, xyiz  A,
2. |y| > 0, and
3. |xy|  p.
7
Lecture 7
UofH - COSC 3340 - Dr. Verma
Proof of pumping lemma

Idea: If a string w of length m is accepted by
a DFA with n states, and n < m, then there is
a cycle (repeated state) on the directed path
from s to a final state labeled w.
–
–
8
Recall: directed path is denoted by *(s,w).
Uses: Pigeon-hole principle
Lecture 7
UofH - COSC 3340 - Dr. Verma
Pigeon-hole principle
4 pigeons
3 pigeonholes
9
Lecture 7
UofH - COSC 3340 - Dr. Verma
Pigeon-hole principle (contd.)
A pigeonhole must
have two pigeons
10
Lecture 7
UofH - COSC 3340 - Dr. Verma
Pigeon-hole principle (contd.)
nm
n
...........
m pigeonholes
...........
11
Lecture 7
UofH - COSC 3340 - Dr. Verma
Details of Proof of Pumping Lemma.
Consider L - any infinite regular language.
1. L regular  there is a DFA M with L(M) = L.
2. Let DFA have p states (say).
3. Let w in L be of length more than p.


Why does w exist?
Ans: because L is infinite.
4. *(s,w) = f (some final state) must be
*(s, w = xyz) = *(q,yz) = *(q,z) = f
5. So xynz in L for n = 0, 1, 2, 3, ....
since *(s, xynz) = *(q, ynz) = *(q, y{n-1}z) = ... = *(q,z) = f.
12
Lecture 7
UofH - COSC 3340 - Dr. Verma
Describing the pumping lemma
Take an infinite regular language L
DFA that accepts L
m
states
13
Lecture 7
UofH - COSC 3340 - Dr. Verma
Describing the pumping lemma
(contd.)
Take string
with
w
w L
There is a walk with label:
w
.........
14
Lecture 7
UofH - COSC 3340 - Dr. Verma
Describing the pumping lemma
(contd.)
If string
w
has length
| w|  m
number
of states
Then, from the pigeonhole principle:
A state q is repeated in the walk
......
15
Lecture 7
q
w
......
UofH - COSC 3340 - Dr. Verma
Describing the pumping lemma
(contd.)
y
Write
w x y z
......
x
16
Lecture 7
q
......
z
UofH - COSC 3340 - Dr. Verma
Describing the pumping lemma
(contd.)
x y|  m
length | y |  1
Observations : length |
number
of states
y
......
x
17
Lecture 7
q
......
z
UofH - COSC 3340 - Dr. Verma
Describing the pumping lemma
(contd.)
Observation: The string
x z is accepted
y
......
x
18
Lecture 7
q
......
z
UofH - COSC 3340 - Dr. Verma
Describing the pumping lemma
(contd.)
Observation: The string x
is accepted
yyz
y
......
x
19
Lecture 7
q
......
z
UofH - COSC 3340 - Dr. Verma
Describing the pumping lemma
(contd.)
Observation: The string x
is accepted
yyyz
y
......
x
20
Lecture 7
q
......
z
UofH - COSC 3340 - Dr. Verma
Describing the pumping lemma
(contd.)
In General: The string x
is accepted
i
y z i  0, 1, 2, ...
y
......
x
21
Lecture 7
q
......
z
UofH - COSC 3340 - Dr. Verma
Some Applications of Pumping Lemma
The following languages are not regular.
1. {anbn | n  0 }.
2. {w = wR | w in {a,b}* } (language of palindromes).
3. {wwR | w in {a,b}*}.
4. {a{n2} | n  0}.
22
Lecture 7
UofH - COSC 3340 - Dr. Verma
Tips of the trade -- Do not forget!
Closure properties can be used effectively for:
(1) shortening cumbersome Pumping lemma
arguments.

Example: {w in {a, b}* | w has equal a's and b's}.
(2) for showing that certain languages are regular.

23
Example: {w in {a, b}* | w begins with a and w contains a b}.
Lecture 7
UofH - COSC 3340 - Dr. Verma
References

Pigeonhole Principle & Pumping Lema Description
–
www.cs.rpi.edu/courses/fall00/modcomp3/class8.ppt

24
Author: Costas Busch, Rensselaer Polytechnic Institute, NY
Lecture 7
UofH - COSC 3340 - Dr. Verma