HW 4 Due on Wednesday, February 13, 2019 at 10am CS/ECE 374: Algorithms & Models of Computation, Spring 2019 Version: 1.01
Submission instructions as in previous homeworks. 10 (100 pts.) Aberrant.
10.A. (25 pts.) Prove that the following language is not regular by providing a fooling set. You need to prove an infinite fooling set and also prove that it is a valid fooling set. For Σ = {a, b}, the language is
L = w w w ∈ Σ + .
10.B. (25 pts.) Same as (A) for the following language. Recall that a run in a string is a maximal non-empty substring of identical symbols. Let L be the set of all strings in Σ∗ that contains two distinct runs of equal length. A few examples about L:
• L contains any string of the form bia+b+ai.
• L contains any string of the form bia+bi.
• L does not contain the strings abbaaa, abbaaabbbb.
10.C. (25 pts.) Suppose you are given two languages L,L′ that are not regular but such that L′ \ L is regular. Prove that L ∪ L′ is not regular. (Hint: Use closure properties of regular languages.)
10.D. (15 pts.) Provide a counter-example for the following claim:
Claim: Consider two languages L and L′. If L is not regular, L′ is regular, and L ∪ L′ is
regular, then L ∩ L′ is regular.
10.E. (10 pts.) (Slightly harder1) Same as (A) for L = 0n4 n ≥ 3.
11 (100 pts.) Grammar it.
Describe a context free grammar for the following languages. Clearly explain how they work
and the role of each non-terminal. Unclear grammars will receive little to no credit.
11.A. (40pts.)aibjckdleti,j,k,l,t≥0andi+j+k+t=l.
11.B. (60 pts.) (Harder.) L = {z ∈ {a,b,c}∗ | there is a suffix y of z s.t. #a(y) > #b(y)}. (Hint: First solve for the case that z has no cs.)
12 (100 pts.) As easy as 1,2,3,6. LetL=aibjck k=i+j.
12.A. (20 pts.) Prove that L is context free by describing a grammar for L.
12.B. (80 pts.) Prove that your grammar is correct. (See extra problems for an example of how
this is done.)
1Feel free to use IDK.
1