Unidad II lenguajes regulares

Trabajo de investigación

Carlos Rivera Trejo

Teoría de la computación

LENGUAJES REGULARES

Un lenguaje regular es un tipo de lenguaje formal que satisface las

siguientes propiedades:

Puede ser reconocido por:

•un autómata finito determinista •un autómata finito no determinista •un autómata finito alterno •una maquina de turing de solo lectura

Es generado por:

•una gramática regular•una gramática de prefijos

Es descrito por:

•una expresión regular

2.1 Autómata finito

Esquema lógico de un autómata finito.

Un autómata finito o máquina de estado finito es un modelo matemático de un sistema que recibe una cadena constituida por símbolos de un

alfabeto y determina si esa cadena pertenece al lenguaje que el automata reconoce.

Formalmente, un autómata finito (AF) puede ser descrito como una 5-tupla (S,Σ,T,s,A) donde:

S un conjunto de estados;

Σ es un alfabeto;

T es la función de transición::

es el estado inicial;

es un conjunto de estados de aceptación o finales.

Formas de representar un autómata:

Además de notar un AF a través de su definición formal es posible representarlo a través de otras notaciones que resultan más cómodas. Entre estas notaciones, las más usuales son:

En teoría de autómatas y lógica secuencial, una tabla de transición de estados es una tabla que muestra que estado (o estados en el caso de un Autómata finito no determinista) se moverá la máquina de estados, basándose en el estado actual y otras entradas. Una tabla de estados es esencialmente una tabla de verdad en la cual algunas de las entradas son el estado actual, y las salidas incluyen el siguiente estado, junto con otras salidas.

•Formas comunes

Tablas de estados de una dimensión

También llamdas tablas características, las tablas de estados de una dimensión son más como tablas de verdad que como las versiones de dos dimensiones. Las entradas son normalmente colocadas a la izquierda, y separadas de las salidas, las cuales están a la derecha.

Tablas de Estados de dos dimensiones Las tablas de transición de estados son normalmente tablas de dos dimensiones. Hay dos formas comunes para construirlas.

•La dimensión vertical indica los Estados Actuales, la dimensión horizontal indica eventos, y las celdas (intersecciones fila/columna) de la tabla contienen el siguiente estado si ocurre un evento (y posiblemente la acción enlazada a esta transición de estados).

Tabla de Transición de Estados

  EventsState

E1 E2   ...   En

S1 - Ay/Sj ... -

S2 - - ... Ax/Si

... ... ... ... ...

Sm Az/Sk - ... -

(S: estado, E: evento, A: acción, -: transición ilegal)

•La dimensión vertical indica los Estados Actuales, la dimensión •horizontal indica los siguientes estados, y las intersecciones •fila/columna contienen el evento el cual dirigirá al siguiente •estado particular.

Tabla de Transición de Estados

      nextcurrent

S1 S2   ...   Sm

S1 Ay/Ej - ... -

S2 - - ... Ax/Ei

... ... ... ... ...

Sm - Az/Ek ... -

(S: estado, E: evento, A: acción, -: transición imposible)

Para un autómata finito no determinista (AFND), una nueva entrada puede causar que la máquina esté en más de un estado, dado que es no determinista. Esto se denota en una tabla de transición de estados por un par de llaves { } con un conjunto de todos los estados objetivo entre ellos. Se da un ejemplo abajo.

Tabla de Transición de Estados para un AFND

  EntradaEstado

1 0 ε

S1 S1 { S2, S3 } Φ

S2 S2 S1 Φ

S3 S2 S1 S1

Aquí, una máquina no determinista en el estado S1 leyendo una entrada de 0 causará que esté en dos estados al mismo tiempo, los estados S2 y S3. La última columna define la transición legal de estados del carácter especial, ε. Este carácter especial permite a los AFND moverse a un estado diferente cuando no hay ninguna entrada. En el estado S3, el AFND puede moverse a S1 sin consumir ningún carácter de entrada. Los dos casos anteriores configuran al autómata finito no determinista.

Es posible dibujar un diagrama de estados partiendo de la tabla. Una secuencia posible de pasos a seguir es la siguiente:

1) Dibuja círculos que representen los estados dados. 2) Para cada uno de los estados, mira la correspondiente fila y dibuja una flecha para cada uno de los estados destino. Pueden ser múltiples flechas para un mismo carácter de entrada si el autómata es un AFND. 3) Designa un estado como el estado inicial. El estado inicial está dado en la definición formal del autómata. 4) Designa uno o más estados como estado final( o también llamado de aceptación). Esto también está dado en la definición formal.

Ejemplo:

Las tablas de transiciones:

Tabla de Transición de Estados

  EntradaEstado

1 0

S1 S1 S2

S2 S2 S1

Un AFD o autómata finito determinista es aquel autómata finito cuyo estado de llegada está unívocamente determinado por el estado inicial y el carácter leído por el autómata.Formalmente, un autómata finito determinista (AFD) es similar a un Autómata de estados finitos, representado con una 5-tupla (S,Σ,T,s,A) donde:

Σ es un alfabeto; S un conjunto de estados; T es la función de transición:

es el estado inicial; •es un conjunto de estados de aceptación o finales.

Al contrario de la definición de autómata finito, este es un caso particular donde no se permiten transiciones lambda (vacías), el dominio de la función T es S (con lo cual no se permiten transiciones desde un estado de un mismo símbolo a varios estados).

Expresión regular

Una expresión regular, a menudo llamada también patrón, es una expresión que describe un conjunto de cadenas sin enumerar sus elementos. Por ejemplo, el grupo formado por las cadenas Handel, Händel y Haendel se describe mediante el patrón "H(a|ä|ae)ndel". La mayoría de las formalizaciones proporcionan los siguientes constructores: una expresión regular es una forma de representar a los lenguajes regulares (finitos o infinitos) y se construye utilizando caracteres del alfabeto sobre el cual se define el lenguaje.

Específicamente, las expresiones regulares se construyen utilizando los operadores unión concatenacion y clausura de Kleene.

• Clausura de Kleene

•En lógica matemática y en ciencias de la computación, la

clausura de Kleene (también llamada estrella Kleene o

cierre estrella) es una operación unaria que se aplica sobre

un conjunto de cadena de caracteres o un conjunto de símbolos

o caracteres (alfabeto), y representa el conjunto de las cadenas

que se pueden formar tomando cualquier número de cadenas

del conjunto inicial, posiblemente con repeticiones, y

concatenándolas entre si.

•La aplicación de la clausura de Kleene a un conjunto V se

denota como V*. Es muy usada en expresiones regulares y

fue introducida en este contexto por Stephen Kleene

(1909-1994) para caracterizar un cierto autómata.

Ejemplos:

•Ejemplo de clausura de Kleene aplicada a un conjunto de cadenas:

{"ab", "c"}* = {ε, "ab", "c", "abab", "abc", "cab", "cc", "ababab",

"ababc", "abcab", "abcc", "cabab", "cabc", "ccab", "ccc", ...}

•Ejemplo de clausura de Kleene aplicada a un conjunto de caracteres:

{'a', 'b', 'c'}* = {ε, "a", "b", "c", "aa", "ab", "ac", "ba", "bb", "bc", ...}

• Lenguajes no regulares

Los lenguajes regulares infinitos (y también algunos lenguajes que

no son regulares). Gracias a este lema podremos demostrar que

ciertos lenguaje infinitos no son regulares. Es importante hacer

notar que el lema de bombeo es una herramienta adecuada para

demostrar que un lenguaje no es regular, pero no lo será para

demostrar que un lenguaje si es regular (por el hecho de que

existen algunos lenguajes no regulares que la cumplen).

Por tanto, si un lenguaje no cumple el lema de bombeo no

es regular, pero si lo cumple no podremos decir si es o no regular.

•Enunciado del Lema de Bombeo

Para todo lenguaje regular infinito L, existe una constante n,

dependiente de ese lenguaje, de forma que si w es una cadena

de L con |w| ≥ n, podemos partir w en tres cadenas, x, y, z, de forma que:

w = xyz,

y ≠ ε (o dicho de otro modo, que |y| ≥ 1),

|xy| <= n

Para cualquier k ≥ 0, la cadena xykz pertenece a L.

O sea que para cualquier cadena de L lo bastante larga, siempre podremos encontrar una partición en tres subcadenas, con una no vacía en el medio (la y) que no está demasiado lejos del comienzo de la palabra, que podremos “bombear”; es decir, que si se repite la subcadena y cualquier número de veces, la cadena resultante también pertenecerá a L.