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 Ai is regular. [5] i=1
• 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≥0andifi=1thenj=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 ̸= 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∈Land|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 . Show that such automata can 3
recognize non-regular languages.
3