Exercise 1

Let $\Sigma$ = {a, b} be an alphabet and n be a positive integer. For two words m and v we say that

v is a factor of m if there exist two words u and w such that

m  =  u v w, (1)

v is a factor of m of order n if there exist at least n couples (u₁, w₁), ... (u_n, w_n) pairwise different such that

m  =  u₁ v w₁  =   ^...   =  u_n v w_n. (2)

We consider the language L(bb, n) over $\Sigma$ consisting of the words m for which the word bb is a factor of order n but not a factor of order n + 1. For each of the languages L(bb, 0), L(bb, 1) and L(bb, 2).

(1.1)

Construct a deterministic finite automaton that recognizes this language. (Your answer can be in the form of a transition table).

(1.2)

Give a regular expression for this language.

(1.2)

Write a lex input file that accepts this language.