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.

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 2n 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: .

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.