Introducción a la teoría de los autómatas

Introducción a la teoría de los autómatas

¿Qué son las máquinas?

El término «Autómatas» proviene de la palabra griega «αὐτόματα», que significa «autoactiva». Un autómata (plural «Autómatas») es un dispositivo informático autopropulsado abstracto que realiza automáticamente una secuencia determinada de operaciones.

Un autómata con un número finito de estados se llama Máquina de estados finitos (FA) o Máquina de estados finitos (FSM).

Definición formal de una máquina de estados finitos.

El autómata se puede representar como un conjunto de cinco (Q, ∑, δ, q0, F), donde –

• Q – un conjunto finito de estados.

• ∑ conjunto de caracteres finito llamado alfabeto máquina.

• δ – función de transición.

• q0 es el estado inicial a partir del cual se procesa cualquier entrada (q0 ∈ Q).

• F es un conjunto de estados / estados finales Q (F ⊆ Q).

Terminología relacionada

Alfabeto

• Definición – Un alfabeto – cualquier conjunto de caracteres finito.

• Ejemplo – ∑ = {a, b, c, d} es conjunto de alfabeto donde ‘a’, ‘b’, ‘c’ y ‘d’ – simbolos…

Un hilo

• Definición – Y un hilo – la secuencia final de caracteres tomados de.

• Ejemplo – ‘cabcad’ es una cadena alfabética válida ∑ = {a, b, c, d}

Longitud de la línea

• Definición – Este es el número de caracteres por línea. (Denotado | S |).

• Ejemplos de –

  • Si S = ‘cabcad’, | S | = 6

  • Si | S | = 0, se llama linea vacia (Denotado λ o ε)

Estrella de Kleene

• Definición – Estrella Kleene, ∑ *, es un operador unario sobre un conjunto de caracteres o cadenas, ∑, que da un conjunto infinito de todas las cadenas posibles de todas las longitudes posibles en ∑ incluso λ…

• Representación – ∑ * = ∑0 ∪ ∑1 ∪ ∑2 ∪ ……. donde ∑p es el conjunto de todas las cadenas posibles de longitud p.

• Ejemplo – Si ∑ = {a, b}, ∑ * = {λ, a, b, aa, ab, ba, bb, ………..}

Cierre de cuñas / Plus

• Definición – Colocar ∑ + – un conjunto infinito de todas las cadenas posibles de todas las longitudes posibles sobre ∑, excluyendo λ.

• Representación – ∑ + = ∑1 ∪ ∑2 ∪ ∑3 ∪ …….

  ∑ + = ∑ * – {λ}

• Ejemplo – Si ∑ = {a, b}, ∑ + = {a, b, aa, ab, ba, bb, ………..}

Lengua

• Definición – El idioma es un subconjunto de ∑ * para algún alfabeto ∑. Puede ser finito o infinito.

• Ejemplo – Si el lenguaje acepta todas las cadenas posibles de longitud 2 sobre ∑ = {a, b}, entonces L = {ab, aa, ba, bb}