CSE 237, Homework 4: Proving Languages Non-regular
due 2/22/06 in class

 

1.Please start each problem on a new sheet.

2. Do not turn in problems whose answer is in the textbook.

Problem 1.

Prove that every NFA can be converted to an equivalent one that has a single accept state.
This is problem 1.11 in the textbook, and the solution is provided. 

Problem 2. Pumping lemma

Apply the pumping lemma to prove that the following languages are not regular.

    a. {0i 1j: i <= j}
    b. {wcccw : w is some string over {a,b,c} }

Hint: make sure to study the examples in the book first.

Problem 3. Applying closure properties

Apply the closure properties of regular languages (RLs) to prove that the following languages are not regular.

    a. {w: w is a string over {a, b} where the number of a's and b's is not equal}

    Hint: use the fact that RLs are closed under complement.

    b. {w : w is a string over {a,b} which has three times as many a's as b's}.

    Hint: make use of the fact that {a3nbn: n >= 0} is not regular.

Problem 4.

In this problem, we will find examples to show that the converse of closure rules for RLs is not true. 

a. Prove that, if a language is not regular, then its complement is also not regular.
Hint: think of one of the closure rules.

b. Use the result in part (a) to show that when both languages are not regular, their union may still be regular. 
Hint: what is the union of a language and its complement?

c. How about when one language is regular and the other is not?  Find an example of two such languages, so the result of a concatenation is regular.
Hint: think of the language in Problem 2a. 

Note: While we only ask in both parts (b) and (c) for an example for only one operation,  it should be possible to come up with examples for all all four binary operations under which RLs are closed, as well as for star (why not for complement?).