Assignment 3

This assignment focuses on DFAs. The file dfa_test.ml in the ocaml folder can help write tests for your answers.

1. Suppose we consider the alphabet 0, 1 and the corresponding strings are then binary numbers, which we see highest-order bit first. Consider the language \(L = \{w \mid \textrm{the number }w\textrm{ is divisible by } 5\}\). Draw a DFA with \(5\) states that recognizes this language.

2. Consider the alphabet consisting of the characters a and b, and the language \(L\) containing exactly the strings that consist of \(0\) or more as followed by \(0\) or more bs. Draw the DFA that recognizes this language, explaining what the different states “represent” (\(3\) states are sufficient).

3. Consider the alphabet consisting of the characters a, b and c, and the language \(L\) containing exactly the strings that contain a aa and a bb (in either order and potentially far from each other). Draw the DFA that recognizes this language, explaining what the different states “represent” (\(7\) states are sufficient).

4. Consider the alphabet consisting of all 10 decimal digits, and the three symbols +, -, .. The language \(L\) consists of all valid numbers, according to the following rules:

   • The first character may be a sign + or -.
   • A sign cannot appear anywhere else in the number.
   • After the possible sign, a number follows (the integer part).
   • It may be 0 alone, or it may be a non-zero digit, followed by zero or more digits.
   • After the “integer part”, there may be a dot, ..
   • Following the dot, there may be any number of digits.
   • It is also possible that the number starts with (a possible sign then) a dot, followed by at least one digit.

   For example here are some valid numbers: -0., +.0, .230, 143, 0.21, -110.. And some invalid numbers: +0+, -., 011, 1.23.1.

   Find a DFA that recognizes this language (\(7\) states are sufficient). You can use something like 1-9 to indicate a range of “inputs” that should all take you to the same state.