Exercises 01

Review: State Machines from Regular Expressions

Floating point literals

Floating point constants can take many forms: they are signed, may have a fractional part and may have an additional (positive or negative) integer exponent to represent an attached power of 10. Examples of such literals are: 3.1415, -7, 6.02214e23, 0.27183. Additionally, note the following:

  • there are no leading zeros, except a single one before the decimal point
  • the decimal point must always be followed by a fractional part
  • the exponent is never 0 or 1
  1. Construct a regular expression to recognize the floating point literals we just described
  2. Construct a finite state machine for the same problem


  1. Convert the following regular expression to NFA: $a((b|a^*c)x)^*|x^*a$ (ex. 2.4 b from the Tiger book)
  2. …and to DFA.

This page can be helpful.


URLs are what you type, for instance, to access a remote resource from your web browser. They contain the following information (and more):

  • The protocol, for instance http, ftp, https. It is optional.
  • The hostname, which necessarily contains a domain name (, and optionally a (possibly composed) local hostname (, Restrict yourself to the .com, .ch, .uk for the top level domains.
  • Following the hostname is the path of the resource; it is a sequence of file names (or directories) separated by slashes.
  • Finally, parameters can be passed to the requested resource; they are written as a ?, followed by a list of key/value pairs separated by &s

For example:


Construct a context-free grammar to build URLs as we described them. Do not give production rules for identifier types (host names, file names, keys, values). Instead, use symbols hostNameID, fileNameID, keyID, valueID in the grammar.