A teoria dos autômatos é um ramo teórico da ciência da computação e da matemática. É o estudo das máquinas abstratas e dos problemas de computação que podem ser resolvidos com essas máquinas. A máquina abstrata é chamada de autômato. A principal motivação por trás do desenvolvimento da teoria dos autômatos foi desenvolver métodos para descrever e analisar o comportamento dinâmico de sistemas discretos.
Este autômato consiste em estados e transições. O Estado é representado por círculos , e a Transições é representado por Setas; flechas .
Autômato é o tipo de máquina que recebe alguma string como entrada e essa entrada passa por um número finito de estados e pode entrar no estado final.
Existem as terminologias básicas que são importantes e frequentemente utilizadas em autômatos:
Símbolos:
Os símbolos são uma entidade ou objetos individuais, que podem ser qualquer letra, alfabeto ou qualquer imagem.
Exemplo:
1, a, b, #
Alfabetos:
Alfabetos são um conjunto finito de símbolos. É denotado por ∑.
Exemplos:
∑ = {a, b} ∑ = {A, B, C, D} ∑ = {0, 1, 2} ∑ = {0, 1, ....., 5] ∑ = {#, β, Δ} Corda:
É uma coleção finita de símbolos do alfabeto. A string é denotada por w.
Exemplo 1:
Se ∑ = {a, b}, várias strings que podem ser geradas a partir de ∑ são {ab, aa, aaa, bb, bbb, ba, aba.....}.
- Uma string com zero ocorrências de símbolos é conhecida como string vazia. É representado por ε.
- O número de símbolos em uma string w é chamado de comprimento de uma string. É denotado por |w|.
Exemplo 2:
w = 010 Number of Sting |w| = 3
Linguagem:
Uma linguagem é uma coleção de strings apropriadas. Uma linguagem formada sobre Σ pode ser Finito ou Infinito .
Exemplo 1
L1 = {Set of string of length 2} = {aa, bb, ba, bb} <strong>Finite Language</strong> Exemplo: 2
L2 = {Set of all strings starts with 'a'} = {a, aa, aaa, abb, abbb, ababb} <strong>Infinite Language</strong>