Finite state machine

Determinization of finite state machine

Finite state machine with epsilon transitions

Closure properties of finite state machines

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: (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 (epfl.ch, google.com) and optionally a (possibly composed) local hostname (lara.epfl.ch, news.bbc.co.uk). 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:

• epfl.ch
• https://mail.google.com/mail/?shva=1&key=value

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.