On this page you will find corrected exercises on: optimization of automata, determinization and minimization.
Determinization
Exercise 1
Determine the following automata:
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 with man}. Find a deterministic automaton 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 Thompson algorithm (here we notice that the epsilons transitions are not useful). The automaton is as follows:
After determinization we obtain the following automaton:
Exercise 3
Let L be the language accepted by the automaton A below:
Find a regular grammar 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!
We determine the automaton:
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:
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:
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):
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:
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:
Its determinization leads to the following automaton:
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}):
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:
No leaf corresponds to a final state, note that all the leaves end up in the well.
The deterministic automaton:
The states {1} and {1,3} have the same rules. We therefore find the minimal automaton:
Exercise 8
Among the following regular expressions and automata tell which are the automata and regular expressions that represent the same language:
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:
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:
2 - Rational Expression (ab + b (a + b)) ∗. We start by building an automaton using Glushkov's method:
Likewise, the automaton is already deterministic. After minimization we have the following automaton:
3 - To minimize A3, we must first determine it. Here is the result of the determinization algorithm:
And after minimization:
4 - The automaton is already deterministic, after minimization we obtain:
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:
Then we determine it:
We rename the states in order by A, B, C, D, E, F to avoid ambiguities. Then we minimize:
Likewise for the automaton recognizing M:
We have determinism (we will notice that we form a trash state):
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.
EN 
FR 
ES