Corrected exercises on the language theory, 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)has. For this you can do a tree possibilities 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 automata. This question can be answered systematically by using matrices. For this, we represent the automaton (which we can see as a graph) by the adjacency matrix. Thus, the index coefficient 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.

Corrected exercises on the theory of languages, automata and grammars. The exercises are followed by a correction.

For the automaton A1, it suffices to evaluate (1,3) and (1,4) of the following matrices:

Corrected exercises on language theory, automata and grammars

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:

Corrected exercises on language theory, automata and grammars

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:

Corrected exercises on language theory, automata and grammars

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:

Corrected exercises on language theory, automata and grammars

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:

Corrected exercises on language theory, automata and grammars

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:

Corrected exercises on language theory, automata and grammars

Exercise 7

 Be there 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 system of equations (ofregular expressions) matching. 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:

Corrected exercises on language theory, automata and grammars

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.

Corrected exercises on language theory, automata and grammars

The system of regular equations associated with A:

Corrected exercises on language theory, automata and grammars

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 *.

To share
en_GBEN