APUNTES DE LENGUAJES

LENGUAJES REGULARES

Un lenguaje regular es un tipo de lenguaje formal que satisface las siguientes propiedades:

Los lenguajes más sencillos que se considerarán son los lenguajes regulares, es decir, los que se pueden generar a partir de los lenguajes básicos, con la aplicación de las operaciones de unión, concatenación y * de Kleene un número finito de veces.

Puede ser reconocido por:

·        Un autómata finito determinista

·        Un autómata finito no determinista

·        Un autómata de pila

·        Un autómata finito alterno

·        Una máquina de Turing de solo lectura

Es generado por: una gramática regular

una gramática de prefijos

AUTÓMATA FINITO DETERMINISTA

 Un autómata determinista (abreviado AFD) es un autómata finito que además es un sistema determinista; es decir, para cada estado en que se encuentre el autómata, y con cualquier símbolo del alfabeto leído, existe siempre no más de una transición posible desde ese estado y con ese símbolo.

 Definición formal Formalmente, se define como una 5-tupla (Q, Σ, q0, δ, F) donde:

• ·        Es un conjunto de estados
• ·        Es un alfabeto
• ·        Es el estado inicial
• ·        Es una función de transición
• ·        Es un conjunto de estados finales o de aceptación.

 En un AFD no pueden darse ninguno de estos dos casos:

• ·        Que existan dos transiciones del tipo δ(q,a)=q1 y δ(q,a)=q2, siendo q1 ≠ q2
• ·        Que existan transiciones del tipo δ(q, ε), donde ε es la cadena vacía, salvo que q sea un estado final, sin transiciones hacia otros estados.