^{PDFprof.com Search Engine}

A2 Automates et algorithmes (II)

Quel est le langage reconnu par l'automate ?
Le mot w appartient au langage reconnu par l'automate si il existe un chemin de l'état initial à un état final qui décrit ce mot. e est un mot du langage reconnu par l'automate si l'état initial est final.
Comment déterminer un automate ?
Un automate est déterministe si et seulement si les deux conditions suivantes sont vérifiées : 1.
L'automate possède un et un seul état initial ; 2.
Pour chaque état q et pour chaque lettre α, il existe au plus une transition issue de q d'étiquette α.
Comment savoir si un automate est complet ?
En informatique, le déterminisme est le fait de ne pas avoir le choix entre plusieurs exécutions.
Un automate fini et déterministe est complet si et seulement si δ est une application de Q × Σ sur Q.
De chaque état, il part alors exactement un arc étiqueté par chacune des lettres de l'alphabet Σ.
Soit (Q, q0, F, δ) un automate fini deterministe : — Un blocage de l'automate est un couple (q, x) ∈ Q × s tel que δ(q, x) n'est pas défini. — Un automate sans blocages est dit complet. — L'automate est dit standard si pour tout (q, x) ∈ Q × s , δ(q, x) ̸= q0.

Quel est le langage reconnu par l'automate ?