Problem Set 3—Non-Regular Languages

Purpose

This problem set develops your understanding of how to prove that a language is not regular. It concentrates on using the pumping lemma, but provides a slight chance to use closure properties as well.

Background

This problem set is based on material in section 1.4 of our textbook. We discussed or will discusse this material in class between February 8 and 12.

Activity

Solve each of the following problems.

Problem 1

Exercise 1.29b in our textbook (show that {www | w∈{a,b}*} is not regular).

Problem 2

Problem 1.35 in our textbook (show that strings made from 2-row “tiles” and satisfying the rule that the top row of the tiles is the reverse of the bottom row is not regular; see textbook for details).

Problem 3

Problem 1.46c in our textbook (show that the language containing all and only the strings over {0,1} that are not palindromes is not regular).

Problem 4

Problem 1.47 in our textbook (show that a language whose strings are sequences of 1s separated by # signs, and having the property that no two sequences of 1s are the same length, is not regular; see textbook for details).

Problem 5

The pumping lemma says that in any regular language, strings of length p or more are pumpable within the first p symbols. Is it also true that they are pumpable within the last p symbols? State this claim in a formal manner similar to the pumping lemma, and either prove or disprove it.

Follow-Up

I will grade this exercise in a face-to-face meeting with you. During this meeting I will look at your solution, ask you any questions I have about it, answer questions you have, etc. Please bring a written solution to the exercise to your meeting, as that will speed the process along.

Sign up for a meeting via Google calendar. If you worked in a group on this exercise, the whole group should schedule a single meeting with me. Please make the meeting 15 minutes long, and schedule it to finish before the end of the “Grade By” date above.