COMP 330  Assignment 3

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