Slide 1
Regular and Nonregular Languages
Chapter 8
Languages: Regular or Not?
a*b* is regular.
{anbn: n 0} is not.
{w {a, b}* : every a is immediately followed by b} is regular.
{w {a, b}* : every a has a matching b somewhere} is not
● Showing that a language is regular.
● Showing that a language is not regular.
How Many Regular Languages?
Theorem 8.1: There is a countably infinite number of regular languages.
Proof:
● Upper bound: number of FSMs (or regular exp.)
● Lower bound on number of regular languages:
{a},{aa},{aaa},{aaaa},{aaaaa},{aaaaaa},…
There are many more nonregular languages than there are regular ones.
Showing that a Language is Regular
Every finite language is regular.
L = L1 L2, where:
L1 = {anbn, n 0}, and
L2 = {bnan, n 0}
L =
L = {w {0 – 9}*: w is the social security number of the
current US president}.
Showing That L is Regular
Construct an FSM for L.
Construct a regular grammar for L.
Construct a regular expression for L.
Show that the number of equivalence classes of L is finite.
Use closure theorems.
Closure Properties of Regular Languages
● Union
● Concatenation
● Kleene star
● Complement
● Intersection
● Difference
● Reverse
Closure of Regular Languages
Under Complement ()
Construct a DFSM for L
Complete the DFSM
Flip accepting states to get a DFSM for L
Closure of Regular Languages
Under Intersection
Write this in terms of operations we have already proved closure for:
● Union
● Concatenation
● Kleene star
● Complementation
L1 L2 =
(L1 L2)
L1 L2
*
L(M1) L(M2) = (L(M1) L(M2)).
Closure of Regular Languages
Under Difference
L1 – L2 =
L1 L2
*
L(M1) – L(M2) = L(M1) L(M2).
Use operations – Example
L1 = {w {a, b}* : w contains an even number of a’s and an odd number of b’s}, and
L2 = {w {a, b}* : all a’s come in runs of three}
Let L = {w {a, b}* : w contains an even number of a’s and an odd number of b’s and all a’s come in runs of three}.
L = L1 L2, where:
Don’t Try to Use Closure Backwards
One Closure Theorem:
If L1 and L2 are regular, then so is
L = L1 L2
But if L is regular, what can we say about L1 and L2?
L = L1 L2
Don’t Try to Use Closure Backwards
One Closure Theorem:
If L1 and L2 are regular, then so is
L = L1 L2
But if L is regular, what can we say about L1 and L2?
L = L1 L2
ab = ab (a b)* (they are regular)
Don’t Try to Use Closure Backwards
One Closure Theorem:
If L1 and L2 are regular, then so is
L = L1 L2
But if L is regular, what can we say about L1 and L2?
L = L1 L2
ab = ab (a b)* (they are regular)
ab = ab {anbn, n 0} (they may not be regular)
Showing that a Language is Not Regular
Every regular language can be accepted by some FSM.
It can only use a finite amount of memory to record essential properties.
Example:
{anbn, n 0} is not regular
Showing that a Language is Not Regular
The only way to generate/accept an infinite language with a finite description is to use:
Kleene star (in regular expressions), or
cycles (in automata).
This forces some kind of simple repetitive cycle within the strings.
Fact: If a DFSM M = (K, , , s, A) accepts a string of length |K| or greater, then that string will force M to visit some state more than once (thus traversing at least one loop).
The Pumping Theorem for Regular Languages
Theorem 8.6 (Pumping Theorem) If L is regular, then there exists k 1 such that any w L with |w| k can be written as w = xyz, for some x,y,z *, such that
|xy| k,
y ,
q 0, xyqz L
x
y
z
Proof: choose k = |K|;
a state must be used twice
Example
L= {anbn: n 0} is not regular
k is the number from the Pumping Theorem.
Choose w to be akbk (“long enough”).
1 2
a a a a a … a a a a a b b b b … b b b b b b
x y z
Pumping Theorem implies xyqz L, for any q.
But then we can “pump” more a’s than b’s, a contradiction.
Therefore, L is not regular.
Using the Pumping Theorem
If L is regular, then every “long” string in L is pumpable.
To show that L is not regular, we find one that isn’t.
To use the Pumping Theorem to show that a language L is not regular, we must:
1. Choose a string w where |w| k. Since we do not know
what k is, we must state w in terms of k.
2. Consider all possibilities for y
3. In each case choose an q such that xyqz is not in L.
Bal = {w {), (}* :the parens are balanced}
PalEven = {wwR : w {a, b}*}
L= {anbm: n > m}
L = {an: n is prime}
L = {w = an: n is prime}
Let w = aj, where j = a prime number greater than k+1:
a a a a a a a a a a a a a
x y z
|x| + |z| is prime.
|x| + |y| + |z| is prime.
|x| + 2|y| + |z| is prime.
|x| + 3|y| + |z| is prime, and so forth.
We have xyqz L, for any q. Choose q = |x| + |z|. Then:
|x| + |z| +q|y| = |x| + |z| + (|x| + |z|)|y|
= (|x| + |z|)(1 + |y|)
But (|x| + |z|)(1 + |y|) is NOT a prime, a contradiction.
Using the Pumping Theorem Effectively
● To choose w:
● Choose a w that is in the part of L that makes it not
regular.
● Choose a w that is only barely in L.
● Choose a w with as homogeneous as possible an
initial region of length at least k.
● To choose q:
● Try letting q be either 0 or 2.
● If that doesn’t work, analyze L to see if there is some
other specific value that will work.
Using the Closure Properties
The two most useful ones are closure under:
Intersection
Complement
How to use? Assume a language L is regular and then:
Show the intersection with a know regular language is NOT regular.
Show that the complement is not regular.
Using the Closure Properties
L = {w {a, b}*: #a(w) = #b(w)}
If L were regular, then:
L = L _______
would also be regular. But it isn’t.
L = {aibj: i, j 0 and i j}
Try to use the Pumping Theorem by letting w = ak+1bk:
L = {aibj: i, j 0 and i j}
Try to use the Pumping Theorem by letting w = akbk+k!.
Then y = ap for some nonzero p.
Let q = (k!/p) + 1 (i.e., pump in (k!/p) times).
Note that (k!/p) must be an integer because p < k.
The number of a’s in the new string is k + (k!/p)p = k + k!.
So the new string is ak+k!bk+k!, which has equal numbers of a’s and b’s and so is not in L.
L = {aibj: i, j 0 and i j}
An easier way:
If L is regular then so is L. Is it?
L = {aibj: i, j 0 and i j}
An easier way:
If L is regular then so is L. Is it?
L = AnBn {out of order}
If L is regular, then so is L = L a*b*
= ___________
L = {aibjck: i, j, k ≥ 0 and (i 1 or j = k)}
Every string in L of length at least 1 is pumpable.
If i = 0: y = b or y = c
If i = 1 or i > 2: y = a
If i = 2: y = aa
Pumping theorem cannot be used to prove that L is not regular.
L = {aibjck: i, j, k ≥ 0 and (i 1 or j = k)}
But the closure theorems help. Suppose we guarantee that i = 1. If L is regular, then so is:
L = L ab*c*.
L = {abjck : j, k ≥ 0 and j = k}
Use Pumping Theorem to show that L is not regular: