Autómatas y Lenguajes Formales

Alfabeto

Conjunto no vacío y finito de símbolos. También se les suele llamar letras del alfabeto. Se denota con la letra griega Σ.

Ejemplos:


Σ1 = {a,b,c,...,z}
Σ2 = {0,1}

Palabra

Secuencia finita de símbolos de un alfabeto. Habitualmente se utilizan las últimas letras minúsculas de nuestro alfabeto (x, y, z) para denotar a las palabras.

Ejemplos:


x = casa es una palabra definida sobre el alfabeto Σ1
y = 010100 es una palabra definida sobre el alfabeto Σ2

Lenguaje

Se denota con la letra L y definido sobre un alfabeto Σ, es un conjunto cualquiera de palabras definidas sobre dicho alfabeto, por lo tanto, L ⊂ ω(Σ).

Autómata Finito

Autómata Finito Determinista

Autómata Finito No Determinista

En los AFD sabemos exactamente cuál es la transición que debemos llevar a cabo ante una determinada situación. Sin embargo, en los no deterministas podemos encontrarnos con varias opciones e, incluso, con λ-transiciones que se realizan sin considerar el correspondiente símbolo de la cadena de entrada. Para tener en cuenta estas consideraciones, los AFND se definen como una tupla:


AFND = (Σ, Q, f, q0, F, T), f: Q × Σ → 2Q donde


2Q es el conjunto formado por los subconjuntos de Q, incluyendo a Ø
T es una relación binaria definida sobre Q que indica las λ-transiciones del autómata (si pTq ⇒ existe una λ-transición desde p hasta q)


El resto de los símbolos tiene el mismo significado que en la definición de AFD.

Son máquinas teóricas que van cambiando de estado dependiendo de la entrada que reciban. La salida de estos Autómatas está limitada a dos valores: aceptado y no aceptado, que pueden indicar si la cadena que se ha recibido como entrada es o no válida.

Formalmente, un Autómata Finito Determinista (AFD) se define como una tupla


AFD = (Σ, Q, f, q0, F), donde


Σ es el alfabeto de entrada
Q es el conjunto finito y no vacío de los estados del Autómata
f es la función de transición que indica en qué situaciones el Autómata pasa de un estado a otro, se define f: Q × Σ → Q
q0 ∈ Q es el estado inicial
F ⊂ Q es el conjunto de estados finales de aceptación (F ≠ Ø)

Estado

Estados Marcados

Estados No Marcados

Gramática

Una gramática es una cuádrupla


G = (VAr,VT,S,P),


donde VN es un conjunto finito de símbolos variables (no terminales); VT = Σ, un conjunto finito de símbolos terminales; S, el símbolo o variable inicial; y P, un conjunto finito de reglas de derivación.

Expresiones Regulares

Cierre de Kleene (*)

Concatenación (.)

Unión (+)

  1. Asociativa (α + β) + γ = α + (β + γ)
  2. Conmutativa α + β = β + α
  3. Elemento neutro (Ø) α +Ø= α
  4. Idempotencia α + α = α
  1. Asociativa (αβ)γ = α(βγ)
  2. Distributiva respecto de la unión α(β + γ) = αβ + αγ
  3. Elemento neutro (λ) αλ = λα = α
  4. αØ=Ø
  5. No es conmutativa
  1. λ∗ = λ
  2. Ø∗ = λ
  3. α∗α∗ = α∗
  4. α∗α = αα∗
  5. (α∗)∗ = α∗
  6. α∗ = λ + αα∗
  7. α∗ = λ + α + α2 + ... + αn + αn+1α∗
  8. f(α, β, γ, . . .)+(α + β + γ + ...)∗ = (α + β + γ + ...)∗
  9. (f(α∗, β∗, γ∗,...))∗ = (α + β + γ + ...)∗

Juan G. Perales ⭐