Deterministic finite automaton

Difficulty
Easy 25%

Deterministic finite automaton

We are used to drawing a automaton deterministic finite, by figuring the states by circles, by indicating the initial state by an incoming arrow, the accepting states by a double circle or an outgoing arrow, and the transition from state q to state q' by reading the letter α by an arrow going from q to q' and labeled by α.

deterministic finite automaton

A deterministic finite automaton A is a triplet (Vt, Q, T) where

  • Vt is the vocabulary of the automaton;
  • Q is the finite set of states of the automaton;
  • T: Q × Vt → Q, is a partial application called the automaton transition function.

When T is total, in other words if there is in each state exactly one transition for any letter of the alphabet, the automaton is said to be complete.

Reading a word

Note that the derivations produced by the reading of a word w by a deterministic finite automaton is linear and is therefore free of ambiguity: the reading of the letters composing the word causes well-defined transitions until it is blocked in the event of transitions. missing, or until reaching a certain state after the complete reading of the word. To check the reading of a word, it is necessary to start from the initial states and consume the symbols one by one while moving in the PLC until one has an impossible case or the complete reading of the word.

We deduce the fundamental property of complete deterministic automata:

Let A = (Vt, Q, T) be a complete deterministic finite automaton. So, for any word u ∈ Vt and any state q ∈ Q, there exists a unique state q '∈ Q such that q (u) → Aq'.

In practice, it can be useful to make a PLC complete by adding a new state called trash to which all the missing transitions go. The blocking calculations then end up in the trash where they remain captured.

A deterministic automaton can also be defined with two additional data:

  • of an initial state i ∈ Q;
  • of a set of accepting states F ⊆ Q;

Note that the initial state and the accepting states can also be deduced from the T rules.

A word w is recognized by the automaton if there is a so-called successful calculation resulting from the initial state i and ending in an accepting state after having read the word w. We denote by L (A) the language of words recognized by the automaton A. A language recognized by an automaton is said to be recognizable. We denote by Rec the set of recognizable languages. Adding a trash state does not change the words recognized by a PLC.

From language to automaton

Any language accepted by a finite automaton is regular. All regular language is accepted by a finite automaton.

For each of the languages below, explain the language and draw a deterministic automaton that recognizes it.

  • 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

deterministic finite automaton

We can effectively transform a grammar regular on the right in a deterministic finite automaton and vice versa. The non-terminals correspond to the states of the automaton.

Automatons with recognized words

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.

deterministic finite automaton

We can symbolize (and even store) the transitions of a finite automaton in the form of a two-dimensional array. The lines represent the transition start states, the columns indicate the symbols and the values the transition destination states.

For the automaton A, it suffices to evaluate (1,3) and (1,4) of the following matrices - indeed the recognized words start at state 1 and end in state 3 or 4:

deterministic finite automaton

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.