Previous    Next

## EXERCISES

• 2.1 Write regular expressions for each of the following.

1. Strings over the alphabet {a, b, c} where the first a precedes the first b.

2. Strings over the alphabet {a, b, c} with an even number of a's.
3. Binary numbers that are multiples of four.
4. Binary numbers that are greater than 101001.
5. Strings over the alphabet {a, b, c} that don't contain the contiguous substring baa.
6. The language of nonnegative integer constants in C, where numbers beginning with 0 are octal constants and other numbers are decimal constants.
7. Binary numbers n such that there exists an integer solution of an+bn = cn.
• 2.2 For each of the following, explain why you're not surprised that there is no regular expression defining it.
1. Strings of a's and b's where there are more a's than b's.

2. Strings of a's and b's that are palindromes (the same forward as backward).
3. Syntactically correct Java programs.
• 2.3 Explain in informal English what each of these finite-state automata recognizes.

• 2.4 Convert these regular expressions to nondeterministic finite automata.
1. (if|then|else)

2. a((b|a*c)x)*jx*a
• 2.5 Convert these NFAs to deterministic finite automata.

• 2.6 Find two equivalent states in the following automaton, and merge them to produce a smaller automaton that recognizes the same language. Repeat until there are no longer equivalent states.

Actually, the general algorithm for minimizing finite automata works in reverse. First, find all pairs of inequivalent ststes. States X, Y are inequivalent if X is final and Y is not or (by iteration) if and and X′, Y′ are inequivalent. After this iteration ceases to find new pairs of inequivalent states, then X; Y are equivalent if they are not inequivalent. See Hopcroft and Ullman [1979], Theorem 3.10.

• *2.7 Any DFA that accepts at least one string can be converted to a regular expression. Convert the DFA of Exercise 2.3c to a regular expression. Hint: First, pretend state 1 is the start state. Then write a regular expression for excursions to state 2 and back, and a similar one for excursions to state 0 and back. Or look in Hopcroft and Ullman [1979], Theorem 2.4, for the algorithm.
• *2.8 Suppose this DFA were used by Lex to find tokens in an input file.
1. How many characters past the end of a token might Lex have to examine before matching the token?

2. Given your answer k to part (a), show an input file containing at least two tokens such that the first call to Lex will examine k characters past the end of the first token before returning the first token. If the answer to part (a) is zero, then show an input file containing at least two tokens, and indicate the endpoint of each token.
• 2.9 An interpreted DFA-based lexical analyzer uses two tables, edges indexed by state and input symbol, yielding a state number, and final indexed by state, returning 0 or an action-number. Starting with this lexical specification,
```(aba)+ (action 1);
(a(b*)a) (action 2);
(a|b) (action 3);
```

generate the edges and final tables for a lexical analyzer.

Then show each step of the lexer on the string abaabbaba. Be sure to show the values of the important internal variables of the recognizer. There will be repeated calls to the lexer to get successive tokens.

• **2.10 Lex has a lookahead operator / so that the regular expression abc/def matches abc only when followed by def (but def is not part of the matched string, and will be part of the next token(s)). Aho et al. [1986] describe, and Lex [Lesk 1975] uses, an incorrect algorithm for implementing lookahead (it fails on (a|ab)/ba with input aba, matching ab where it should match a). Flex [Paxson 1995] uses a better mechanism that works correctly for (a|ab)/ba but fails (with a warning message) on zx*/xy*.