COMP 330 Winter 2021
Assignment 3
Due Date: 18th February 2021
Prakash Panangaden
4th February 2021
There are 5 questions for credit and some extra questions at the end. There are three ques-
tions which are a accessible to everyone but perhaps harder than the usual questions. There
is one for your spiritual growth. All the regular questions are excellent practice for the mid-
term. The extra questions will not help you prepare for the mid-term. Please submit the
homework through myCourses by 5pm on the due date.
Question 1[20 points] Are the following statements true or false? Prove your answer in
each case, but the proof need only be a simple example or a couple of lines of explanation.
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.
{anb2n|n > 0}
Question 3[20 points] Show that the language
F = {aibjck|i, j, k ≥ 0 and if i = 1 then j = k}
1
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 over the alphabet {a, b}, such that
w has an even number of a’s and an odd number of b’s and does not contain the substring
ab. By this last statement I mean that one can never have an a followed by a b.
1. Give a DFA with only five states, including any dead states, that recognizes D.
2. Give a regular expression for this language.
Question 5[20 points] Consider the language L = {anbm|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; we used the notation RL in the notes but it means the same thing
as ≡L. Since this language is not regular ≡L cannot have finitely many equivalence classes.
Exhibit explicitly, infinitely many distinct equivalence classes of ≡L.
Please turn over for the spiritual growth question.
2
Extra Question 1[0 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.
Extra Question 2[0 points] In assignment 1 we had a 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.”
Extra Question 3[0 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.
Spiritual Growth Question[0 points] Consider a probabilistic variant of a finite automa-
ton. 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