Lenguajes regulares
Páginas: 6 (1356 palabras)
Publicado: 15 de mayo de 2011
Teoría de la Computación
“Lenguajes Regulares y Expresiones Regulares”
Ingeniería en Sistemas Computacionales
Asesor:
Aida Antonio Pacheco
Alumno:
Héctor López Felipe
4to Semestre Grupo A
Tuxtepec, Oaxaca a 18 de marzo de 2011
Para empezar a desarrollar este tema veremos que un autómata finito es un modelo matemático de una máquina que acepta cadenas de un lenguaje definidosobre un alfabeto A. Consiste en un conjunto finito de estados y un conjunto de transiciones entre esos estados, que dependen de los símbolos de la cadena de entrada. El autómata finito acepta una cadena x si la secuencia de transiciones correspondientes a los símbolos de x conduce desde el estado inicial a un estado final y los Lenguajes Regulares son los más simples y restringidos dentro de lajerarquía de Chomsky. Estos lenguajes pueden además ser descritos mediante dos representaciones: las Expresiones Regulares y las Gramáticas 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 de pila
* un autómatafinito alterno
* una máquina de Turing de solo lectura
* Es generado por:
* una gramática regular
* una gramática de prefijos
* Es descrito por:
* una expresión regular
Los lenguajes regulares se llaman así porque sus palabras contienen “regularidades” o repeticiones de los mismos componentes, como por ejemplo en el lenguaje L1 siguiente:
L1 = {ab, abab, ababab,abababab, . . .}
En este ejemplo se aprecia que las palabras de L1 son simplemente repeticiones de “ab” cualquier número de veces. Aquí la “regularidad” consiste en que las palabras contienen “ab” algún número de veces.
Otro ejemplo más complicado sería el lenguaje L2:
L2 = {abc, cc, abab, abccc, ababc, . . .}
La regularidad en L2 consiste en que sus palabras comienzan con repeticiones de“ab”, seguidas de repeticiones de “c”. Similarmente es posible definir muchos otros lenguajes basados en la idea de repetir esquemas simples. Esta es la idea básica para formar los lenguajes Regulares.
Adicionalmente a las repeticiones de esquemas simples, vamos a considerar que los lenguajes finitos son también regulares por definición.
Por ejemplo, el lenguaje L3 = {anita, lava, la, tina} esregular.
Finalmente, al combinar lenguajes regulares uniéndolos o concatenándolos, también se obtiene un lenguaje regular.
Por ejemplo, L1 U L3 = {anita, lava, la, tina, ab, abab, ababab, abababab, . . .} es regular.
También es regular una concatenación como L3L3 = {anitaanita, anitalava, anitala, anitatina, lavaanita, lavalava, lavala, lavatina, . . .}
DEFINICIÓN FORMAL DE LENGUAJESREGULARES
Definición.- Un lenguaje L es regular si y sólo si se cumple al menos una de las condiciones siguientes:
* L es finito;
* L es la unión o la concatenación de otros lenguajes regulares R1 y R2, L = R1 U R2 o L = R1R2 respectivamente.
* L es la cerradura de Kleene de algún lenguaje regular, L = R*.
Esta definición nos permite construir expresiones en la notación de conjuntosque representan lenguajes regulares.
Ejemplo.- Sea el lenguaje L de palabras formadas por a y b, pero que empiezan con a, como aab, ab, a, abaa, etc. Probar que este lenguaje es regular, y dar una expresión de conjuntos que lo represente.
Solución.- El alfabeto es _ = {a, b}. El lenguaje L puede ser visto como la concatenación de una a con cadenas cualesquiera de a y b; ahora bien, éstasúltimas son los elementos de {a, b}*, mientras que el lenguaje que sólo contiene la palabra a es {a}. Ambos lenguajes son regulares. Entonces su concatenación es {a}{a, b}*, que también es regular.
EXPRESIONES REGULARES
La notación de conjuntos nos permite describir los lenguajes regulares, pero nosotros quisiéramos una notación en que las representaciones de los lenguajes fueran...
“Lenguajes Regulares y Expresiones Regulares”
Ingeniería en Sistemas Computacionales
Asesor:
Aida Antonio Pacheco
Alumno:
Héctor López Felipe
4to Semestre Grupo A
Tuxtepec, Oaxaca a 18 de marzo de 2011
Para empezar a desarrollar este tema veremos que un autómata finito es un modelo matemático de una máquina que acepta cadenas de un lenguaje definidosobre un alfabeto A. Consiste en un conjunto finito de estados y un conjunto de transiciones entre esos estados, que dependen de los símbolos de la cadena de entrada. El autómata finito acepta una cadena x si la secuencia de transiciones correspondientes a los símbolos de x conduce desde el estado inicial a un estado final y los Lenguajes Regulares son los más simples y restringidos dentro de lajerarquía de Chomsky. Estos lenguajes pueden además ser descritos mediante dos representaciones: las Expresiones Regulares y las Gramáticas 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 de pila
* un autómatafinito alterno
* una máquina de Turing de solo lectura
* Es generado por:
* una gramática regular
* una gramática de prefijos
* Es descrito por:
* una expresión regular
Los lenguajes regulares se llaman así porque sus palabras contienen “regularidades” o repeticiones de los mismos componentes, como por ejemplo en el lenguaje L1 siguiente:
L1 = {ab, abab, ababab,abababab, . . .}
En este ejemplo se aprecia que las palabras de L1 son simplemente repeticiones de “ab” cualquier número de veces. Aquí la “regularidad” consiste en que las palabras contienen “ab” algún número de veces.
Otro ejemplo más complicado sería el lenguaje L2:
L2 = {abc, cc, abab, abccc, ababc, . . .}
La regularidad en L2 consiste en que sus palabras comienzan con repeticiones de“ab”, seguidas de repeticiones de “c”. Similarmente es posible definir muchos otros lenguajes basados en la idea de repetir esquemas simples. Esta es la idea básica para formar los lenguajes Regulares.
Adicionalmente a las repeticiones de esquemas simples, vamos a considerar que los lenguajes finitos son también regulares por definición.
Por ejemplo, el lenguaje L3 = {anita, lava, la, tina} esregular.
Finalmente, al combinar lenguajes regulares uniéndolos o concatenándolos, también se obtiene un lenguaje regular.
Por ejemplo, L1 U L3 = {anita, lava, la, tina, ab, abab, ababab, abababab, . . .} es regular.
También es regular una concatenación como L3L3 = {anitaanita, anitalava, anitala, anitatina, lavaanita, lavalava, lavala, lavatina, . . .}
DEFINICIÓN FORMAL DE LENGUAJESREGULARES
Definición.- Un lenguaje L es regular si y sólo si se cumple al menos una de las condiciones siguientes:
* L es finito;
* L es la unión o la concatenación de otros lenguajes regulares R1 y R2, L = R1 U R2 o L = R1R2 respectivamente.
* L es la cerradura de Kleene de algún lenguaje regular, L = R*.
Esta definición nos permite construir expresiones en la notación de conjuntosque representan lenguajes regulares.
Ejemplo.- Sea el lenguaje L de palabras formadas por a y b, pero que empiezan con a, como aab, ab, a, abaa, etc. Probar que este lenguaje es regular, y dar una expresión de conjuntos que lo represente.
Solución.- El alfabeto es _ = {a, b}. El lenguaje L puede ser visto como la concatenación de una a con cadenas cualesquiera de a y b; ahora bien, éstasúltimas son los elementos de {a, b}*, mientras que el lenguaje que sólo contiene la palabra a es {a}. Ambos lenguajes son regulares. Entonces su concatenación es {a}{a, b}*, que también es regular.
EXPRESIONES REGULARES
La notación de conjuntos nos permite describir los lenguajes regulares, pero nosotros quisiéramos una notación en que las representaciones de los lenguajes fueran...
Leer documento completo
Regístrate para leer el documento completo.