É uma forma de representar um modelo matemático. Modelo mostrado abaixo contem 3 estados sendo ele {q0,q1,q2}. Sempre inicia-se com a chave (exemplo de chave) “Símbolo antes do q0” é termina com o circulo duplo, que significa estado final e aceitação. Obs.: Vamos chamar esse autômato de M1.

Exemplo de diagrama de estado, onde ele contem 3 estados.
Exemplo de diagrama de estado, onde ele contem 3 estados.

Estado Inicial (q0) – indicado pela seta apontando para ele a partir do nada.
Estado de aceitação (q1) – indicado pelo círculo duplo
Setas – transições

Quando esse autômato recebe uma cadeia de entrada como 1101, ele processa essa cadeia e produz uma saída (aceita/rejeita). (exemplo acima)

  1. Começa no estado q0.
  2. Lê 1, segue a transição de q0 para q1.
  3. Lê 1, segue a transição de q1 para q1.
  4. Lê 0, segue a transição de q1 para q2.
  5. Lê 1, segue a transição de q2 para q1.
    Aceita porque está no estado de aceitação q1 no final da entrada.

Definição formal

Por quê a definição formal ? R. É precisa (resolve quaisquer ambiguidade). Provê notação (ajuda a pensar e expressar pensamentos claramente).

Um Autômato Finito é uma 5-upla (Q, Σ, δ, q0, F), onde:

  1. Q é um conjunto finito conhecido como conjunto de estados,
  2. Σ é um conjunto finito chamado de alfabeto,
  3. δ : Q x Σ → Q é a função de transição,
  4. q0 pertence a Q e é o estado inicial,
  5. F está contido em Q e é o conjunto de estados de aceitação.

Ex.: Podemos descrever o autômato acima M1 escrevendo:

M1 = (Q, Σ, δ, q0, F), onde

  1. Q = {q0, q1, q3}
  2. Σ = {0, 1}
  3. δ é descrita como →
    4. q0 é o estado inicial e
    5. F = {q1}

δ é descrita como →

0 1
q0 q0 q1
q1 q2 q1
q2 q1 q1

Autômatos Finitos, um exemplo para começarem a familiarizar!

Se A é o conjunto de todas as cadeias que a máquina M aceita (reconhece), dizemos que A é a linguagem da máquina M e escrevemos L(M) = A.Uma máquina pode aceitar várias cadeias mas ela reconhece apenas uma linguagem.

Ex. A = {w | w contém pelo menos um 1 e um número par de zeros segue o último 1}.

Resposta do autômato A
Resposta do autômato A.

B = {w | w é a cadeia vazia ε ou termina em 0}. Como seria ?

Resposta do autômato B
Resposta do autômato B.

C = {w | w começa e termina com o mesmo símbolo}.

Resposta do autômato C.
Resposta do autômato C.

Não perca a próxima publicação. Até breve!