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 =
{
ww
∣∣ 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 =
{
0n
4
∣∣ 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. (40 pts.)
{
aibjckd`et
∣∣ i, j, k, `, t ≥ 0 and i+ j + k + t = `}.
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.
Let L =
{
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
https://courses.engr.illinois.edu/cs374/fa2019/hw/hw_01.pdf