Corrected exercises on the theory of languages, automata and grammars. The exercises are followed by a correction.
Recognized words
Exercise 1
Give all the words of sizes 0, 1, 2, 3, and 4 of the following regular languages: (a + ba)* ; a (aa + b (ab) ∗To)∗To. For that, you can make a possibility tree for each of the languages.
Words of lengths 0: epsilon; Words of lengths 1: a; Words of lengths 2: aa, ba; Words of lengths 3: aaa, aba, baa; Words of lengths 4: aaaa, aaba, abaa, baba, baaa.
Words of lengths 0: none; Words of lengths 1: none; Words of lengths 2: aa; Words of lengths 3: none; Words of lengths 4: aaaa, abaa.
Exercise 2
Give all the words of length 0, 1, 2, 3 and 4 recognized by the following PLCs. It is possible to answer this question in a systematic way by using the matrices. To do this, we represent the automaton (which we can see as a graph) by the adjacency matrix. Thus, the coefficient of index i, j of the matrix Mk corresponds to the words of length k recognized by the PLC, if the initial state was state i and the final state, state j. If we want to obtain the words of length k recognized by our automaton, it suffices to multiply the matrix by itself.
For the automaton A1, it suffices to evaluate (1,3) and (1,4) of the following matrices:
Words of lengths 0: none; Words of lengths 1: b; Words of lengths 2: ab + aa + ba; Words of lengths 3: aba + abb + aaa + baa; Words of lengths 4: abaa + abab + abba + abbb + aaaa + baaa.
For the automaton A1, it suffices to evaluate (1,1) and (1,2) of the following matrices:
Words of length 0: M0 1.1 + M0 1.2 =; Words of length 1: M1 1,1 + M1 1,2 = a; Words of length 2: M2 1,1 + M2 1,2 = aa + bb; Words of length 3: M3 1,1 + M3 1,2 = aaa + bba + abb; Words of length 4: M4 1,1 + M4 1,2 = aaaa + abba + aabb + bbaa + bbab
Exercise 3
Let the following automaton M:
How many states does the M automaton have? Give the set of final states, and the set of states
Initials. Is the automaton deterministic? What state is the controller in after reading the word bbabbb? Is this word recognized by the PLC / accepted by the PLC? Same questions for the word babaabba.
Make the M controller complete. Is the word baa recognized by this automaton? accepted by this machine?
Let the following automaton N:
In which states can the automaton N be after having read babba? Is this word accepted by this automaton? Same question for the word abbb.
The first questions ask for a formal description of the automaton M. When we construct the transition table, we notice that the automaton M is deterministic unlike the automaton N. To complete M, we must add the trash state, all words are recognized but the accepted language remains the same as incomplete.
To read the first word: 1 ⊢ b1 ⊢ bb1 ⊢ bba2 ⊢ bbab3 ⊢ bbabb4 ⊢ bbabbb2 or 2 is not a final state so it is recognized but not accepted. The principle of derivation is the same if the automaton is deterministic, otherwise a derivation tree must be created.
To read the last word:
Note that the automaton can read the word abbb in two ways, when a word can no longer be read in a branch, we note # and the branch ends.
Automaton construction
Exercise 4
For each of the languages below, explain the language and draw an automaton that recognizes it using a construction method.
- L is the language denoted by aba + bab.
- L is the language denoted by (aba)∗+ (bab)∗.
- L = {u ∈ {a, b}∗ such that u contains the factor bbb}.
- L = {u ∈ {a, b}∗ such that u does not contain the bbb factor
Exercise 5
Build with the method of your choice the automata recognizing the following languages (write the regular expression denoting these languages):
- The language of words containing at least once the letter a
- The language of words containing at most once the letter a
- The language of words containing an even number of times the letter a
- The language of words admitting aba as a factor
Recognized language
Exercise 6
Using the method of your choice, determine the language recognized by the following PLCs:
Exercise 7
Let the grammar G = ({a, b, c}, {S, A}, S, P); where P contains the following rules: S → aS | bA; A → cA | ε
Determine if the words w1 = abac, w2 = aabccc, w3 = cabbac and w4 = ab are generated by G. Find the language generated by G (which we denote by L (G)).
The words w1 and w3 are not generated by G; the words w2 and w4 are generated by G: S ⊢ aS ⊢ aaS ⊢ aabA ⊢ aabcA ⊢ aabccA ⊢ aabcccA ⊢ w2 and for w4: S ⊢ aS ⊢ abA ⊢ ab = w4.
To find the language, write the automaton generated by the grammar then use the method of your choice to obtain its regular expression: a * bc *.
Exercise 8
Let the grammar g = <{a, b, c}, {S, A, B}, S, P> where: P = {S → aA | ε; A → bA | cB; B → bB | To }.
Find the corresponding system of equations (of regular expressions). Solve this system.
We will associate a variable with each non-terminal of g: X0 (associated with S), X1 (with A) and X2 (with B). We translate the production rules of P into regular expression equations:
By applying Arden's theorem to the 3rd equation, we obtain: X2 = b * a. By replacing X2 in the 2nd equation we will have: X1 = b.X1 + cb * a; then with the Arden theorem we obtain: X1 = b * cb * a. We replace in the first equation and we will have: X0 = ab * cb * a + ε which denotes the language generated by g.
Exercise 9
Let the grammar g = <{a, b, c}, {S, A, B}, S, P> where: P = {S → baA | aS | ε; A → aA | bB | ε; B → cB | aA}.
Construct the simple finite state automaton A equivalent to g. Write the system of equations associated with A. Find the regular expression that denotes L (A).
To find the simple automaton associated with g, we can decompose the rule S → baA into two rules: S → bC and C → aA; or C is a new non-terminal. We construct the equivalent simple automaton A by associating a state of the automaton with each non-terminal, this state will be final when the associated non-terminal produces ε. The transitions of A will be deduced from the production rules of g.
The system of regular equations associated with A:
To find the regular expression that denotes L (A), we solve the system to find the value of X0. From the fourth equation we have: X3 = c * aX2; we replace in the third: X2 = aX2 + bc * aX2 + ε = (a + bc * a) X2 + ε which is resolved with X2 = (a + bc * a) *. We replace in the second: X1 = a (a + bc * a) *. Then in the first: X0 = aX0 + ba (a + bc * a) * + ε. And we thus obtain the solution: X0 = a * (ba (a + bc * a) * + ε). So L (A) is denoted by the regular expression: a * ba (a + bc * a) * + a *.
EN 
FR 
ES