Assignment #1

1. Identify the lexemes that make up the tokens in the following program. Give reasonable attribute values for the tokens.

int max(int i, int j)
/* return maximum of integers i and j */
{
return i > j ? i : j;
}

2. Describe the languages denoted by the following regular expressions:

• 0(0|1)*0
• ((epsilon|0)1*)*
• (0|1)*0(0|1)(0|1)
• 0*10*10*10*
  

3. Write regular definitions for the following languages.

• All strings of letters that contain the five vowels in order.
• All strings of letters in which the letters are in ascendinglexicographical order.
• Comments consisting of a string surrounded by /* and */ without anintervening */ unless it appears inside the quotes " and ".
  

4. Write down the shortest five strings in the following languages (E is empty).

• (nerk | bob)(s | sled)
• a(ab) * | E
• (f | E)(i | E)(s | E)(h | E)

5. Bracket the regular expression aab*|b.
6. Write a regular expression giving all strings of a's and b's with exactly two a's.