On this page you will find corrected exercises on the optimization of automata, the determination and the minimization.

Determinization

Exercise 1

Determine the following automata:

corrected exercises on automata optimization, determinization and minimization.

Exercise 2

We consider the alphabet A made up of the letters of the alphabet of the French language and the language L = { w ∈ A* / w ends in man}. find a automaton determinist which generates L.

Let x represent all the letters that are not {a, m, n}. The automaton must recognize the words [az; AZ]*man. Let us build an indeterministic automaton with the algorithm of Thompson (here we notice that epsilons transitions are not useful). The automaton is as follows:

corrected exercises on automata optimization, determinization and minimization

After determinization we obtain the following automaton:

corrected exercises on automata optimization, determinization and minimization

Exercise 3

Let L be the language accepted by the automaton A below:

corrected exercises on automata optimization, determinization and minimization

Find a grammar regular generating L. Find a regular expression denoting L. Find a deterministic automaton accepting L.

Here are the grammar productions obtained directly from the automaton: P → aP, P → aQ, Q → bP, Q → R, R → bR, R → cQ, R → bP, R → epsilon. The non-terminals (therefore the nodes of the automaton) of the grammar are {P, Q, R}, the initial symbol is P.

By denoting with Xp, Xq, Xr the languages accepted from the states P, Q and R respectively, the system of equations for these languages is:

Be careful, a recursion of a non-terminal will result in a star, and a distribution with non-terminals will cause a concatenation!

corrected exercises on automata optimization, determinization and minimization

We determine the automaton:

corrected exercises on automata optimization, determinization and minimization

Exercise 4

We consider the regular grammar G = (Γ, Σ, S, Π) with Γ = {S, P, R}, Σ = {a, b} and Π = {S → P, P → baR, P → aS, R → bb, R → aP}. Find a regular expression for this language. Build an automaton A accepting the language defined by grammar G. Explicitly give A in the form (Q, Σ, q0, F, ∆). Find a deterministic automaton accepting this language.

We use the same letters S, P and R for the languages accepted from the states S, P and R. These languages satisfy the system of equations:

corrected exercises on automata optimization, determinization and minimization

The first equation gives S = P, by substituting the expressions for S and R in the second equation we get P = aP + ba (aP + bb) which is equivalent to P = (a + baa) P + babb. Here, P acts as a starting state because there is only a transition between S and P.

We solve this last equation: P = (a + baa) ∗ babb, hence L (A) = S = P = (a + baa) ∗ babb.

Start from the Thompson automaton to arrive at:

corrected exercises on automata optimization, determinization and minimization

By determining the automaton A we obtain B (for more convenience, it is sometimes useful to put a trash state taking the interactions without arrival nodes):

corrected exercises on automata optimization, determinization and minimization

Exercise 5

Build a deterministic finite automaton corresponding to each automaton below, and compute a regular expression for the accepted language using the associated grammar:

corrected exercises on automata optimization, determinization and minimization

Exercise 6

A blind bartender plays the following game with a customer: he has a tray in front of him with four glasses arranged in a square. Each of these glasses may or may not be turned, without the bartender knowing. The purpose of the latter is to arrange so that all the glasses are turned in the same direction. To do this, he can each turn choose one of the following three actions: $

  • spin one of the glasses
  • turn two neighboring glasses
  • turn two opposing glasses

but to add to the difficulty, the customer can turn the tray any number of quarter turns between each of the bartender's actions. The game ends as soon as one of the two winning positions is reached.

Show that we can restrict the number of different configurations to four, then represent the possible actions of the game by a non-deterministic automaton.

Determine this automaton and deduce a winning strategy for the bar.

Only four configurations are possible:

-the four glasses are all in the same direction (configuration q0)

- three glasses are in one direction and the fourth in the other direction (configuration q1)

-two neighboring glasses are in one direction and the other two in the other direction (configuration q2)

-two opposing glasses are in one direction and the other two in the other direction (configuration q3).

We denote by the letter:

-has changing the orientation of one of the four glasses

-b changing the orientation of two neighboring glasses

-c changing the orientation of two opposing glasses.

The game can then be represented by the following non-deterministic automaton:

corrected exercises on automata optimization, determinization and minimization

Its determinization leads to the following automaton:

corrected exercises on automata optimization, determinization and minimization

We see that the recognized word cbcacbc leads to a winning position for the bartender.

Minimization

Exercise 7

We consider the following automaton A = ({a, b}, {1, 2, 3}, ∆, {1}, {1}):

corrected exercises on automata optimization, determinization and minimization

Give the table describing ∆. Is the word baabab accepted by the automaton A (check by unwinding the grammar that you will have previously written)? Give the minimal deterministic finite automaton which recognizes the same language as A.

∆ = {(1, a, 2), (1, b, 1), (1, b, 3), (2, a, 1), (2, a, 3), (3, b, 1) }

baabab is not accepted by the machine. We can add a well, denoted #, to the automaton to make it complete. The reading tree is then the following:

corrected exercises on automata optimization, determinization and minimization

No leaf corresponds to a final state, note that all the leaves end up in the well.

The deterministic automaton:

corrected exercises on automata optimization, determinization and minimization

The states {1} and {1,3} have the same rules. We therefore find the minimal automaton:

corrected exercises on automata optimization, determinization and minimization

Exercise 8

Among the following regular expressions and automata tell which are the automata and regular expressions that represent the same language:

corrected exercises on automata optimization, determinization and minimization

We want to compare the four languages. We calculate the minimal automaton of each language. It will then suffice to compare these automata. Indeed the minimal automaton is a canonical object dependent only on the language, two languages are therefore equal if they have the same minimal automaton (modulo renaming of states).

1 - Rational Expression (ab ∗ a + b (a + b)) ∗. We start by building an automaton by a method of your choice:

corrected exercises on automata optimization, determinization and minimization

We now want to build the minimal language automaton. To do this, we must first determine and then minimize the above automaton. Luckily, we already have a deterministic automaton, so we can go directly to the minimization algorithm which gives us the following result:

corrected exercises on automata optimization, determinization and minimization

2 - Rational Expression (ab + b (a + b)) ∗. We start by building an automaton using Glushkov's method:

corrected exercises on automata optimization, determinization and minimization

Likewise, the automaton is already deterministic. After minimization we have the following automaton:

corrected exercises on automata optimization, determinization and minimization

3 - To minimize A3, we must first determine it. Here is the result of the determinization algorithm:

corrected exercises on automata optimization, determinization and minimization

And after minimization:

corrected exercises on automata optimization, determinization and minimization

4 - The automaton is already deterministic, after minimization we obtain:

corrected exercises on automata optimization, determinization and minimization

Now that we have built the minimal automaton for each of the four languages, we can compare them. We note that modulo renaming of states the languages of A3 and (ab + b (a + b)) ∗ have the same minimal automaton and are therefore equal. The same goes for the languages of A4 and (ab ∗ a + b (a + b)) ∗.

Exercise 9

Let Σ = {a, b}, we consider two following languages: L, the language formed of all the words of Σ ∗ containing aba; M, the language defined by the regular expression (b + aa ∗ bb) ∗ (ε + aa ∗ + aa ∗ b).

 Give a non-deterministic automaton recognizing L. Determine the minimal automaton A recognizing L.

Give a non-deterministic automaton with ε -transitions recognizing M. Determine the minimal automaton B recognizing M.

By comparing the two automata obtained A and B deduce that L = complementary (M). In terms of an automaton, the complement of an A automaton amounts to turning the incoming states into terminal states and vice versa.

After determining the language or grammar of L, we train the automaton for Glushkov's method:

corrected exercises on automata optimization, determinization and minimization

Then we determine it:

corrected exercises on automata optimization, determinization and minimization

We rename the states in order by A, B, C, D, E, F to avoid ambiguities. Then we minimize:

corrected exercises on automata optimization, determinization and minimization

Likewise for the automaton recognizing M:

corrected exercises on automata optimization, determinization and minimization

We have determinism (we will notice that we form a trash state):

corrected exercises on automata optimization, determinization and minimization

We rename the states in order by K, L, M, N to avoid ambiguities. The automaton is already minimal.

We see that the only difference between deterministic automata A and B is that the final states of one are non-final in the other. From which we can deduce that their languages are complementary.

To share
en_GBEN