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}