Compilers - Problem Set #0

Attempt by: Tuesday, February 5, 2008
Submit by: Thursday, February 7, 2008

  1. Write regular expressions that formally capture each of informally described languages.

      Example: One or more a's followed by two or more b's would be represented as aa*bbb*.

    1. Numbers whose digits are all ones, twos and threes and that have a "31" or "21" appearing somewhere in the number. (Examples: 12991 is not in the language, 3121333 is.)

    2. The word "stupid" misspelled with two or more o's in place of the u. (Example: "stoooooopid" is in the language.)

    3. Binary numbers where the number of ones is a multiple of three. (Examples: 10101 is in the language, 1001 is not, nor is 01000.)

  2. Give a concise English language description for the set of strings that match each of the following regular expressions. In addition, give two five-symbol strings where the first is in the language and the second is not.

    Example: For regular expression b*ab*, you might write "strings of a's and b's with exactly one a." babbb is in the language, aaaaa is not.

    1. colo[u|epsilon]r

    2. a(a|b)*a

    3. 1|1(0|1)*1

  3. From the course text, exercise 2.7a.

  4. From the course text, exercise 2.2. (Show your work!)

  5. Consider the language consisting of strings of some number of a's followed by the same number of b's. For example, the empty string, "ab", "aabb", "aaaaabbbbb" are all in the language while "abb", "ba", "abab", and "aaaabb" are not. Can you write a regular expression for this language? If so, what is it? If not, explain why not and why you think that's significant.