COMP 330  Assignment 3


Rate this product

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 [∞
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.
|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.
Question 3[20 points] Show that the language
F = {a
|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
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
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∗
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.
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
. Show that such automata can recognize non-regular

Open chat
Need help?
Can we help you?