CS计算机代考程序代写 Slide 1

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: