Teoria da computação – Diagrama de estados

É 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.

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}.

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

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

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