Introdução à teoria dos autômatos
Autômatos - O que é?
O termo "autômato" é derivado da palavra grega "αὐτόματα" que significa "ação automática". Um autômato (autômato no plural) é um dispositivo de computação autopropelido abstrato que segue uma sequência predeterminada de operações automaticamente.
Um autômato com um número finito de estados é chamado de Finite Automaton (FA) ou Finite State Machine (FSM).
Definição formal de um autômato finito
Um autômato pode ser representado por uma 5-tupla (Q, ∑, δ, q 0 , F), onde -
Q é um conjunto finito de estados.
∑ é um conjunto finito de símbolos, chamado de alphabet do autômato.
δ é a função de transição.
q0é o estado inicial de onde qualquer entrada é processada (q 0 ∈ Q).
F é um conjunto de estados / estados finais de Q (F ⊆ Q).
Terminologias Relacionadas
Alfabeto
Definition - um alphabet é qualquer conjunto finito de símbolos.
Example - ∑ = {a, b, c, d} é um alphabet set onde 'a', 'b', 'c' e 'd' são symbols.
Corda
Definition - A string é uma sequência finita de símbolos tirada de ∑.
Example - 'cabcad' é uma string válida no conjunto de alfabeto ∑ = {a, b, c, d}
Comprimento de uma corda
Definition- É o número de símbolos presentes em uma string. (Denotado por|S|)
Examples -
Se S = 'cabcad', | S | = 6
Se | S | = 0, é chamado de empty string (Denotado por λ ou ε)
Kleene Star
Definition - A estrela Kleene, ∑*, é um operador unário em um conjunto de símbolos ou strings, ∑, que dá o conjunto infinito de todas as cordas possíveis de todos os comprimentos possíveis ao longo ∑ Incluindo λ.
Representation- ∑ * = ∑ 0 ∪ ∑ 1 ∪ ∑ 2 ∪ ……. onde ∑ p é o conjunto de todas as strings possíveis de comprimento p.
Example - Se ∑ = {a, b}, ∑ * = {λ, a, b, aa, ab, ba, bb, ……… ..}
Kleene Closure / Plus
Definition - o conjunto ∑+ é o conjunto infinito de todas as cordas possíveis de todos os comprimentos possíveis em ∑ excluindo λ.
Representation- ∑ + = ∑ 1 ∪ ∑ 2 ∪ ∑ 3 ∪ …….
∑ + = ∑ * - {λ}
Example- Se ∑ = {a, b}, ∑ + = {a, b, aa, ab, ba, bb, ……… ..}
Língua
Definition- Um idioma é um subconjunto de ∑ * para algum alfabeto ∑. Pode ser finito ou infinito.
Example - Se a linguagem assumir todas as strings possíveis de comprimento 2 em ∑ = {a, b}, então L = {ab, aa, ba, bb}