Problem 1. Write regular expressions for the following languages over the alphabet {0,1}:

a) The set of all strings in which the last pair of consecutive 1’s is followed by at least one pair of consecutive 0’s

A= (0* + 10+)*

B= (0* + 10+)*1

This is the same as A but allows the string to end with a 1. (allows the string 1)

My final answer:

A + B + (0 + 1)*00(A + B)

b) The set of all strings of length at least 5 in which the last 5 digits do not contain the substring 000.

I was going to start off using things like (0+1)*(0+1)1(0+1)1(0+1) as this alone will capture many of the possible endings. This idea quickly gives diminishing returns and many of the possible endings are better off listed as is. So after your comment in class and in the interest of clarity I simply list them all. First the legal endings containing one 0 then the legal endings containing two 0’s and finally the few legal endings containing three 0’s and the one legal ending containing four 0’s.

My final answer:

(0+1)*(11111 + 11110 + 11101 + 11011 + 10111 + 01111 + 11100 + 11001 + 10011 + 00111 + 01110 + 11010 + 10110 + 10101 + 01101 + 01011 + 00110 + 01100 + 10010 + 10100 + 01001 + 01010 + 00101 + 00100 )

c) The set of all strings in which the substring 011 appears at most three times.

A = 1*(0* + 10+)*

B = 1*(0* + 10)*1

This is the same as A but allows the string to end with 1.

My final answer:

A1*(A + B) + A1*A1*(A + B) + A1*A1*A1*(A + B)

Problem 2. Develop a pumping lemma for strings that are not in the language. In a deterministic finite automaton where all transitions are specified, arbitrary long strings that get rejected must be rejected through a path that includes one or more loops, so that a lemma similar to the pumping lemma can be proved. What do you think the use of such a lemma would be.

The lemma would be just like the pumping lemma except it would take strings not in the language and try to pump them to be in the language..

If I can take a string not in the language and pump it to make it be in the language the language is not regular.

For example:

{0^i 1^j | i <= j i,j in the natural numbers}

Let w = 0^n+1 1^n

This is clearly not in the language.

W =xyz xy is a string of all 0’s

Pump down y

For all possible lengths of y 0<|y| <=n

I can pump down y and make this string be in the language.

A language is said to be regular in that any repeating pattern in the language (this is not to say that a repeating pattern must exist) must be able to be repeated any number of times. If by manipulating the number of times the pattern is repeated I can make a string not in the language be in the language the language is not regular.

Problem 3. Use the pumping lemma to show that the following languages are not regular.

a) { ww_ry such that |w| > 0 and |y| > 0 , w, y in {0,1}* }

I will use the extended pumping lemma.

I will pick z1 = (10)^n z2 = (01)^n z3 = 1

Clearly z = z1 z2 z3 = (10)^n (01)^n 1 is in the language.

z2 = uvw’ ( I use w’ prime to distinguish it from the w in the definition of the problem)

Pump down v by 1

z = z1^n z2^n-|v| z3 (spaces were added for clarity)

Although v could be many different things I will use the fact that in the chosen z the "mirror image split" was between the only two consecutive 0’s and that |y| = |z3| = 1 must be greater then 0.

By pumping down v I have reduced the cardinality of z2. By definition of the language the cardinality of z1 and z2 must be equal. The only way to restore the equality of z1 and z2 ( |y| >0 ) is to move the "mirror image split" to the left of its previous location. To do so would push the substring 00 to the right of the "split" and this substring 00 does not exist in z1. Also, there are no consecutive 0’s or 1’s to the left of the original split and one of these is needed for the "split" to occur.

There is no division of z1^n z2^n-|v| z3 into ww_ry such that |w| > 0 and |y| >0 w, y, in {0,1}* as such it is not in the language

QED

b) {x | x in{0,1}* and |x| is a Fibonacci number }

Definitions:

F(n) is Fibonacci number at n.. Example: F(3) = 3 F(7) = 21

Fibonacci numbers are a strictly increasing series.

F(n) >= n

Let w = 1^F(n) 0^F(n+1)

w is in the language since |w| = F(n+2) by definition of Fibonacci numbers.

F(n) + F(n+1) = F(n+2)

w= xyz xy is made up of 1’s

pump y

If |y| < F(n) then pump down y by 1. Remember |y| cannot = 0

( F(n) - |y| ) + F(n+1) is less then F(n+2) and greater then F(n+1)

thus the string is not in the language.

If |y| = F(n) pump y up by 1.

Remember

F(n+2) =F(n+1) + F(n)

So F(n) + F(n) < F(n+2)

F(n+3) = F(n+1) + F(n+2)

So F(n+3) > F(n+1) + F(n) + F(n)

( F(n) + |y| ) + F(n+1) is greater then F(n+2) and less then F(n+3)

thus the string is not in the language.

QED