COMP 330

Assignment 3

There are 5 questions for credit and one for your spiritual growth. All the regular questions

are excellent practice for the mid-term. The alternate questions will not help you prepare

for the mid-term. Please submit the homework through myCourses.

Question 1[20 points] Are the following statements true or false? Prove your answer in

each case. We have some fixed alphabet Σ with at least two letters. In the following A and

B stand for languages, i.e. subsets of Σ∗

.

• If A is regular and A ⊆ B then B must be regular. [3]

• If A and AB are both regular then B must be regular. [7]

• If {Ai

|i ∈ N} is an infinite family of regular sets then [∞

i=1

Ai

is regular. [5]

• If A is not regular it cannot have a regular subset. [5]

Question 2[20 points]

Show that the following language is not regular using the pumping lemma.

{a

n

ba2n

|n 0}

Alternate Question 2[20 points]

If L is a language over an alphabet with strictly more than one letter we define CY C(L) =

{uv|u, v ∈ Σ

∗

, vu ∈ L} . Show that if L is regular then CY C(L) is also regular; [12]. Give

an example of a non-regular language such that CY C(L) is regular.

1

Question 3[20 points] Show that the language

F = {a

i

b

j

c

k

|i, j, k ≥ 0 and if i = 1 then j = k}

is not regular. Show, however, that it satisfies the statement of the pumping lemma as I

proved it in class, i.e. there is a p such that all three conditions for the pumping lemma are

met. Explain why this does not contradict the pumping lemma.

Question 4[20 points] Let D be the language of words w such that w has an even number

of a’s and an odd number of b’s and does not contain the substring ab.

1. Give a DFA with only five states, including any dead states, that recognizes D.

2. Give a regular expression for this language.

Alternate Question 4[20 points] In assignment 1 we had an alternate question that asked

you to prove that if a language is regular then the lefthalf of the language is also regular.

Similarly, if I define the middle thirds of a regular language by

mid(L) = {y ∈ Σ

∗

|∃x, z ∈ Σ

∗

s.t. xyz ∈ L and |x| = |y| = |z|}

then mid(L) is also regular. I am not asking you to prove this; it is too easy after you have

done left-half. What if I delete the “middle” and keep the outer portions? More precisely

define,

outer(L) = {xz|∃y ∈ Σ

∗

, xyz ∈ L, and |x| = |y| = |z|}

then is it true that outer(L) is regular if L is regular? Give a proof if your answer is “yes”

and a counter-example, with a proof that it is not regular, if your answer is “no.”

Question 5[20 points] Consider the language L = {a

n

b

m|n 6= m}; as we have seen this is

not regular. Recall the definition of the equivalence ≡L which we used in the proof of the

Myhill-Nerode theorem. Since this language is not regular ≡L cannot have finitely many

equivalence classes. Exhibit explicitly, infinitely many distinct equivalence classes of ≡L.

Alternate Question 5[20 points] Consider regular expressions as an algebraic structure

with operations of · and + and constants of ∅ and ε. Now consider equations of the form

X = A · X + B

where A and B are regular expressions. Show that this always has a solution given by A∗

·B.

Show,in addition, that if A does not contain the empty word this is the unique solution.

Please turn over for the spiritual growth question.

2

Question 6[0 points] Consider a probabilistic variant of a finite automaton. Come up with

a formalization of what this might mean. Suppose that you have a reasonable definition

and now you define acceptance to mean that your word causes the machine to reach an

accept state with probability at least 2

3

. Show that such automata can recognize non-regular

languages.

3