Théorie des automates: terminologies et applications

À l’ère technologique d’aujourd’hui, le domaine du matériel et des logiciels a connu un développement considérable. L'un des principaux domaines de développement a été vu dans les méthodes de conception de matériel. Avec le technologie croissante , le concept de co-conception Matériel - Logiciel a pu être mis en œuvre. Différentes méthodes sont développées par lesquelles, en utilisant un logiciel on peut concevoir et simuler entièrement les systèmes matériels. L'une de ces méthodes est la théorie des automates. La théorie des automates est la branche de l'informatique qui traite de la conception du modèle abstrait des dispositifs informatiques qui suivent automatiquement la séquence prédéterminée d'étapes. Cet article présente de brèves informations sur le didacticiel sur les automates.

Qu'est-ce que la théorie des automates?

Le mot Automata est dérivé du grec, qui signifie «auto-agissant». Un automate est un modèle mathématique de la machine. L'automate se compose d'états et de transitions. Lorsque l'entrée est donnée à l'automate, il effectue une transition vers l'état suivant, en fonction de la fonction de transition. Les entrées de la fonction de transition sont l'état actuel et les symboles récents. Si un automate a un nombre fini d'états, il est connu sous le nom d'automates finis ou Machine à états finis . Les automates finis sont représentés par un 5-tuple (Q, ∑, δ, qo, F)

Où,

Q = ensemble fini d'états.

∑ = ensemble fini de symboles également appelé Alphabet des automates.

δ = la fonction de transition.

qo = état initial de l'entrée.

F = ensemble des états finaux de Q.

Terminologies de base de la théorie des automates

Certaines des terminologies de base de la théorie des automates sont:

1 . Alphabet : Tout ensemble fini de symboles dans la théorie des automates est appelé Alphabet. Représenté par la lettre∑ l'ensemble {a, b, c, d, e,} est appelé ensemble d'alphabet, alors que les lettres de l'ensemble 'a', 'b', 'c', 'd', 'e' sont appelées symboles.

deux . Chaîne de caractères : Dans les automates, une chaîne est une suite finie de symboles tirés de l’ensemble de l’alphabet ∑, par exemple, la chaîne S = ‘adeaddadc’ est valide sur l’ensemble de l’alphabet∑ = {a, b, c, d, e,}

3 . Longueur de chaîne : Le nombre de symboles présents dans la chaîne est appelé Longueur de la chaîne. Pour la chaîne S = 'adaada', la longueur de la chaîne est | S | = 6. Si la longueur de la chaîne est égale à 0, alors on l'appelle une chaîne vide.

4 . Kleen Star : C'est l'opérateur unaire sur l'ensemble des symboles Σ, qui donne l'ensemble infini de toutes les chaînes possibles, y compris λ, de toutes les longueurs possibles sur l'ensemble Σ. Il représenté par. Par exemple, pour l'ensemble Σ = {c, d}, ∑ * = {λ, c, d, cd, dc, cc, dd, ……}.

5 . Fermeture Kleen : C'est l'ensemble infini de toutes les chaînes possibles de l'ensemble alphabétique excluant λ. Il est indiqué par. Pour l'ensemble Σ = {a, d}, ∑ + = {a, d, ad, da, aa, dd,… ..}.

6 . Langue : La langue est le sous-ensemble de l'ensemble d'étoiles Kleeneene * pour certains ensembles d'alphabet Σ. La langue peut être finie ou infinie. Par exemple si une langue prend toutes les chaînes possibles de longueur 2 sur l'ensemble Σ = {a, d}, alors L = {aa, ad, da, dd}.

Langages formels et automates

Dans la théorie des automates, le langage formel est un ensemble de chaînes, où chaque chaîne est composé de symboles appartenant à l'ensemble fini de l'alphabet Σ. Considérons un langage chat, qui peut contenir toutes les chaînes de l'ensemble infini ci-dessous ...
miauler!
meww!
mewww !! ……

L'alphabet défini pour le langage des chats est Σ = {m, e, w,!}. Laissez cet ensemble être utilisé pour un modèle d'automates à états finis-m. Alors le langage formel caractérisé par le modèle m est noté

L (m)
L (m) = {«mew!», «Meww!», «Mewww», ……}

Automaton est utile pour définir un langage car il peut exprimer un ensemble infini sous une forme fermée. Les langues formelles ne sont pas les mêmes que les langues naturelles que nous parlons dans notre vie de tous les jours. Un langage formel peut désigner les différents états de la machine, contrairement à nos langages réguliers. Le langage formel est utilisé pour modéliser une partie du langage naturel comme la syntaxe etc… Les langages formels sont définis par des automates à états finis. Il existe deux perspectives principales des automates à états finis: les accepteurs qui peuvent dire si une chaîne est dans le langage et le second est le générateur qui produit uniquement les chaînes dans le langage.

Automates finis déterministes

Dans les automates de type déterministe, lorsqu'une entrée est donnée, nous pouvons toujours déterminer dans quel état la transition se trouverait. Comme il s'agit d'un automate fini, il est appelé Automates finis déterministes.

Représentation graphique

Le diagramme d'état est les digraphes utilisés pour la représentation graphique des automates finis déterministes. Comprenons avec un exemple. Soit les automates finis déterministes…
Q = {a, b, c, d}.
Σ = {0, 1}
= {a}
F = {d} et la fonction de transition soit

Forme tabulaire de représentation graphique

Diagramme d'état

Diagramme d'état des automates à états finis déterministes

À partir du diagramme d'état

• Les états sont représentés par des sommets.
• Les transitions sont représentées par l'arc étiqueté avec un alphabet d'entrée.
• L'arc entrant unique vide représente l'état initial.
• L'état avec des cercles doubles est l'état final.

Automates finis non déterministes

Les automates dans lesquels l'état de sortie de l'entrée donnée ne peut pas être déterminé sont appelés automates non déterministes. Il est également appelé automates finis non déterministes, car il a un nombre fini d'états. Les automates finis non déterministes sont représentés par l'ensemble des 5 -tuple où (Q, ∑, δ, qo, F)

Q = ensemble fini d'états.
∑ = Jeu de l'alphabet.
δ = la fonction de transition

où : qo = Etat initial.

Représentation graphique

Les automates finis non déterministes sont représentés à l'aide du diagramme d'états. Que les automates finis non déterministes soient

Q = {a, b, c, d}
Σ = {0,1}
qo = {a}
F = {d}

Les transitions sont

Forme tabulaire de représentation graphique

Diagramme d'état

Diagramme d'état des automates finis non déterministes

Applications de la théorie des automates

Les applications de théorie des automates inclure les éléments suivants.

• La théorie des automates est très utile dans les domaines de la théorie du calcul, des productions de compilateurs, de l'IA, etc.
• Pour les compilateurs de traitement de texte et les conceptions matérielles, les automates finis jouent un rôle majeur.
• Pour les applications en IA et en langages de programmation , La grammaire sans contexte est très utile.
• Dans le domaine de la biologie, les automates cellulaires sont utiles.
• Dans la théorie des champs finis, nous pouvons également trouver l'application des automates.

Dans cet article, nous avons appris une brève introduction aux langages et au calcul de la théorie des automates. Les automates existent depuis la période préhistorique. Avec l'invention des nouvelles technologies, de nombreux nouveaux développements sont observés dans ce domaine. Quel type d'automates avez-vous rencontré?