Deterministic finite state automaton DFA

The automata are represented by displaying the states by circles, indicating the initial state by an incoming arrow, the accepting states by a double circle or an outgoing arrow, and the transition from the state q to the state q’ by reading the letter α by an arrow going from q to q’ and labeled by α.

langage26

A deterministic finite state 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 transition function.

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

 

How to read a word

Let us note that the derivations produced by the reading of a word w by a deterministic finite state automaton is linear and is therefore unambiguous: 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 leave the initial states and consume one by one the symbols while moving in the automaton until having an impossible case or the complete reading of the word.

Let A = (Vt, Q, T) be a complete deterministic finite automaton. Then, for every 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 complete automaton by adding a new state called bin 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:

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

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

A word w is recognized by the automaton if there is a so-called successful calculation from the initial state i and ending in accepting state after having read the word w. We denote by L(A) the language of the 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 controller.

 

From a language to an automaton

Any language accepted by a finite automaton is regular. Any 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

langage4

From automaton to a recognized word

Give all words of length 0, 1, 2, 3 and 4 recognized by the following DFA. It is possible to answer this question in a systematic way using the matrices. For this, we represent the automaton (that 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 automaton, if the initial state was the state i and the final state, the state j. If one wishes to obtain the words of length k recognized by our automaton, it suffices to multiply the matrix by itself.

langage5

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

For automaton A, (1,3) and (1,4) are the word starting in state 1 and finishing in state 3 or 4 – indeed the recognized words start at state 1 and end at state 3 or 4:

langage6

RESULTS : Words of length 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