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

Autómatas - ¿Qué es?

El término "Autómatas" se deriva de la palabra griega "αὐτόματα" que significa "autoactiva". Un autómata (Automata en plural) es un dispositivo informático autopropulsado abstracto que sigue automáticamente una secuencia predeterminada de operaciones.

Un autómata con un número finito de estados se llama Finite Automaton (FA) o Finite State Machine (FSM).

Definición formal de un autómata finito

Un autómata se puede representar mediante una tupla de 5 (Q, ∑, δ, q 0 , F), donde -

  • Q es un conjunto finito de estados.

  • ∑ es un conjunto finito de símbolos, llamado alphabet del autómata.

  • δ es la función de transición.

  • q0es el estado inicial desde donde se procesa cualquier entrada (q 0 ∈ Q).

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

Terminologías relacionadas

Alfabeto

  • Definition - un alphabet es cualquier conjunto finito de símbolos.

  • Example - ∑ = {a, b, c, d} es una alphabet set donde 'a', 'b', 'c' y 'd' son symbols.

Cuerda

  • Definition - A string es una secuencia finita de símbolos tomados de ∑.

  • Example - 'cabcad' es una cadena válida en el conjunto alfabético ∑ = {a, b, c, d}

Longitud de una cuerda

  • Definition- Es el número de símbolos presentes en una cadena. (Denotado por|S|).

  • Examples -

    • Si S = 'cabcad', | S | = 6

    • Si | S | = 0, se llama empty string (Denotado por λ o ε)

Estrella de Kleene

  • Definition - La estrella de Kleene, ∑*, es un operador unario en un conjunto de símbolos o cadenas, ∑, que da el conjunto infinito de todas las cadenas posibles de todas las longitudes posibles en ∑ incluso λ.

  • Representation- ∑ * = ∑ 0 ∪ ∑ 1 ∪ ∑ 2 ∪ ……. donde ∑ p es el conjunto de todas las cadenas posibles de longitud p.

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

Cierre Kleene / Plus

  • Definition - El conjunto ∑+ es el conjunto infinito de todas las cadenas posibles de todas las longitudes posibles sobre ∑ excluyendo λ.

  • Representation- ∑ + = ∑ 1 ∪ ∑ 2 ∪ ∑ 3 ∪ …….

    ∑ + = ∑ * - {λ}

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

Idioma

  • Definition- Un idioma es un subconjunto de ∑ * para algún alfabeto ∑. Puede ser finito o infinito.

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