La théorie des automates est une branche théorique de l'informatique et des mathématiques. C'est l'étude des machines abstraites et des problèmes de calcul qui peuvent être résolus à l'aide de ces machines. La machine abstraite s’appelle les automates. La principale motivation derrière le développement de la théorie des automates était de développer des méthodes pour décrire et analyser le comportement dynamique des systèmes discrets.
Cet automate est constitué d'états et de transitions. Le État est représenté par cercles , et le Transitions est représenté par flèches .
Les automates sont le genre de machine qui prend une chaîne en entrée et cette entrée passe par un nombre fini d'états et peut entrer dans l'état final.
Il existe des terminologies de base qui sont importantes et fréquemment utilisées dans les automates :
Symboles :
Les symboles sont une entité ou des objets individuels, qui peuvent être n'importe quelle lettre, alphabet ou n'importe quelle image.
Exemple:
1, une, b, #
Alphabets :
Les alphabets sont un ensemble fini de symboles. Il est noté ∑.
Exemples:
∑ = {a, b} ∑ = {A, B, C, D} ∑ = {0, 1, 2} ∑ = {0, 1, ....., 5] ∑ = {#, β, Δ} Chaîne:
C'est une collection finie de symboles de l'alphabet. La chaîne est notée w.
Exemple 1:
Si ∑ = {a, b}, les différentes chaînes qui peuvent être générées à partir de ∑ sont {ab, aa, aaa, bb, bbb, ba, aba.....}.
- Une chaîne sans occurrence de symboles est appelée chaîne vide. Il est représenté par ε.
- Le nombre de symboles dans une chaîne w est appelé la longueur d'une chaîne. Il est noté |w|.
Exemple 2 :
w = 010 Number of Sting |w| = 3
Langue:
Un langage est une collection de chaînes appropriées. Un langage formé sur Σ peut être Fini ou Infini .
Exemple 1
L1 = {Set of string of length 2} = {aa, bb, ba, bb} <strong>Finite Language</strong> Exemple : 2
L2 = {Set of all strings starts with 'a'} = {a, aa, aaa, abb, abbb, ababb} <strong>Infinite Language</strong>