# Berkeley COMPSCI 172 - Homework (2 pages)

Previewing page*1*of 2 page document

**View the full content.**# Homework

Previewing page *1*
of
actual document.

**View the full content.**View Full Document

## Homework

0 0 78 views

Problems/Exams

- Pages:
- 2
- School:
- University of California, Berkeley
- Course:
- Compsci 172 - Computability and Complexity

**Unformatted text preview: **

CS172 Computability Complexity Spring 2009 Homework 3 Out 12 Feb 2009 Due 19 Feb 2009 Note Questions marked with an asterisk are to be handed in The others are for practice and will not be graded Put your solutions to the problems in the now unique homework box on Soda level 2 by 4pm on the due date The usual remarks about clear answers and the collaboration policy still hold Depending on grading resources we may grade only a random subset of the problems and check off the rest so you are advised to attempt all questions 1 Which of the following languages are regular If the language is regular exhibit a finite automaton or a regular expression for it If not give a careful proof using the pumping lemma a The set of all strings over the alphabet that consist of correctly nested pairs of parentheses E g the string belongs to this language but the strings and do not b The set of all words over the alphabet a b in which the number of occurrences of abb and of bba are the same Note The string abba contains one occurrence of each c The language A w 1k y where y 0 1 contains at least k 1 s for some k 1 Note that 1101010 A for both k 1 its a 1 followed by 101010 and k 2 its a 11 followed by 01010 but 100 6 A because there is no k for which the def applies d The language B w 1k y where y 0 1 contains at most k 1 s for some k 1 e The language C w 1k 0y where y 0 1 contains at least k 1 s for some k 1 f The set of all words over the alphabet a b in which the number of occurrences of aaa and of bbb are the same Note The string bbbaaaabbb contains two occurrences of each g The language 0i 1j i j 0 and i 6 j H INT Why can t you use the pumping lemma in this case It might be helpful to consider the complement of the language 2 More closure Let L be a regular language Show that the following languages are regular a The language min L x L no proper prefix of x is in L b The language L10 consisting of the lexicographically first 10 strings of L c The language 21 L x y s t xy L and x y

View Full Document