# 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: .