# Homework 01

**Due Wednesday, 30th September, 10:15am**. Hand it in to Giuliano Losa before the beginning of the exercise session.

## Problem 1

Write a regular expression for the language of nonnegative integer constants in the C programming language, where numbers beginning with O are octal constants and other numbers are decimal constants.

Comments:

As the statement of the problem was misleading (0 instead of 0), only the solutions that could not fall into any interpretation are deemed wrong.

5 points

## Problem 2

Convert the following regular expression to nondeterministic finite automata: a((b|a*c)x)*|x*a

5 points

## Problem 3

Show that any deterministic finite automaton for regular expression (a|b)*a(a|b)(a|b)…(a|b) where (a|b) appears n-1 times at the end must have at least 2^{n} states.

Possible solution:

Let be a deterministic automaton for the given regular
expression. Let's prove that by contradiction :

Suppose . We are going to exhibit two strings such that
only one is in the language but both lead the automaton in the same
state.

Consider the set of strings.
Notice that .

Consider the set of states in which the automaton is
after processing each of those strings. Since we have
. But , so there has to be at least 2
strings that lead to the same state: .

Now consider a position at which and differ:
because , .

Suppose (the other case is symmetric), and consider
inputs and . We have ,
, , and by construction.
Thus is in the language of the regular expression and is
not. But because the automaton is in the same state for both strings
after having consumed characters and because it is deterministic,
it will be in the same state for both strings after consuming all
the input. It will thus either accept or reject .
This is in contradition with our assumption that is an automaton
for the given regular expression, Thus our supposition is false: .

Comments:

The last part of the argument doesn't apply to a NFA: for a word in the language, not all the possible paths have to end in an accepting state.

Some tried to prove it by induction, but it is difficult to construct a minimal automaton recognizing the language from the minimal automaton of the previous step. Those who tried didn't consider the issue of minimality of the automaton. They just proved that one can construct an automaton with states.

Others said that the NFA has n states and that determinization always gives states. That is wrong, is just the maximum number of states you can get.

10 points : 5 for a correct intuition, 10 for writing a correct proof.