Compilers Principles, Techniques, & Tools (purple dragon book) second edition exercise answers

Exercises for Section 3.8


Suppose we have two tokens: (1) the keyword if, and (2) id­entifiers, which are strings of letters other than if. Show:

  1. The NFA for these tokens, and
  2. The DFA for these tokens.


  1. NFA

    3 8 1-nfa

    NOTE: this NFA has potential conflict, we can decide the matched lexeme by 1. take the longest 2. take the first listed.

  2. DFA

    3 8 1-dfa


Repeat Exercise 3.8.1 for tokens consisting of (1) the keyword while, (2) the keyword when, and (3) identifiers consisting of strings of letters and digits, beginning with a letter.


  1. NFA

    3 8 2-nfa

  2. DFA

    bother to paint

3.8.3 !

Suppose we were to revise the definition of a DFA to allow zero or one transition out of each state on each input symbol (rather than exactly one such transition, as in the standard DFA definition). Some regular expressions would then have smaller "DFA's" than they do under the standard definition of a DFA. Give an example of one such regular expression.


Take the language defined by regular expression "ab" as the example, assume that the set of input symbols is {a, b}

Standard DFA

3 8 3-1

Revised DFA

3 8 3-2

Obviously, the revised DFA is smaller than the standard DFA.

3.8.4 !!

Design an algorithm to recognize Lex-lookahead patterns of the form rl/r2, where rl and r2 are regular expressions. Show how your algo­rithm works on the following inputs:

  1. (abcd|abc)/d
  2. (a|ab)/ba
  3. aa*/a*