Section notes: Week 4

CS 164, Fall 2005

Class Exercises

What's wrong with the following regular expressions?

• [0-9]*\.[0-9]*
• \(?###(\)|\-)###-#### where # represents a digit ([0-9])
• /\*.*\*/
• Any regular expression for nested comments

Consider a language which includes the keywords if, then, in, the, and is.

• Write a DFA to recognize and classify these keywords.
• Extend your DFA so that it recognizes identifiers (any sequence of letters) as well as the keywords

Consider the regular expression (0 | 1 (0 1* 0)* 1)*.

• Write an NFA to recognize this expression (at the board).
• Should the following strings be accepted?
  1. 100001
  2. 100101
  3. 101001
  4. 110110
  5. 100111
• (Hard): What characterizes the numbers in this language?

We've seen how to process a string character-by-character in order to produce a Lisp integer. What about more interesting numeric tokens?

• Write a Lisp function to convert a dollar quantity into an integer. Your function should accept tokens of the form \$[0-9]*\.[0-9][0-9].
• Write a Lisp function to read a length in SI units and convert it into meters. Your function should accept tokens of the form [0-9]+[mck]?m.
• Write a Lisp function which will read a C integer constant of the form (0[0-7]*)|([1-9][0-9]*). Constants starting with zero are octal.
• Write a Lisp function to evaluate simple numerical expressions that satisfy the following grammar (digits, +, and - are the terminal symbols.

  S -> S + I | S - I 
  I -> 0 | N R
  R -> D R | epsilon
  N -> 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
  D -> 0 | N

Nickle rational numbers can be written as int.fixed{repeat}. For example, the fraction 4/3 would be written as 1.{3}. The integer part is not optional, so 1/3 is written 0.{3}, not .{3}.

• Write a regular expression for Nickle rational numbers.
• Write an LL(1) grammar for Nickle rational numbers.
• Write a regular expression to recognize any Nickle number string which represents 1/3.
• Write a regular expression to recognize any Nickle number string which represents p/3 for some integer p.

If you ask a calculator to show a rational number, it will print only a finite number of digits; typically, you would round in the last digit, so that 0.{6} might display as 0.66667. You could also chop in the last digit, just discarding the rest of the number, so that 0.{6} would display as 0.66666.

• Write a regular expression to recognize correctly rounded decimal approximations of p/6 for any integer p.
• Build a finite state machine to recognize whether a finite decimal number is a truncated approximation of p/7 for some integer 0 < p < 7.
• Build a (nondeterministic) finite automaton to recognize whether a finite decimal number is a truncated approximation of p/7 for 0 < p < 7.
• Convert the NFA from the previous exercise into a DFA.

Extra Exercises

You have probably seen this old trick for testing whether an integer is a multiple of 3: if the sum of the digits is a multiple of 3, then so is the integer. You can use a similar trick to recognize repeating decimals of the form p/11 (how?).

• Write a finite state machine which recognizes integer multiples of 3.
• Write a DFA which recognizes whether a finite decimal number is a truncated approximation of p/11 for some p.
• Write an NFA which recognizes whether a finite decimal number is a truncated approximation of p/11 or of p/9 for some integer p.
• Write a DFA which recognizes whether a finite decimal number is a truncated approximation of p/11 or p/9 for some p. Your DFA should have three types of accept states: one for numbers which are truncated approximations to p/9 for some p, but not of p/11; one for numbers which approximate p/11, but not p/9; and one for numbers which could approximate either one.

I pose these left-over questions as challenges. We probably won't get to these questions, but I pose them as challenges. Come explain an answer to one to me in office hours to get out of a quiz next week.

• We asked before for a state machine to recognize integer multiples of 3; can you describe more generally how to produce a state machine to recognize multiples of q for an arbitrary integer q?
• Write a Lisp function to read a Nickle rational number string and produce a Lisp rational number.
• Write a Lisp function to print a Lisp rational number as a Nickle rational number string.
• How long can the repeating part of a Nickle string for p/q be? Assume we use the shortest possible string -- no writing 0.{333}.

Question for next time

What's the muddiest point for you so far in the course?