GRAMATICAS REGULARES

Hola les saluda DarkJrof es nueva entrada esta chevere aqui ubicare informacion sobre gramaticas regulares y unos enlances bacansisimos.

investigador  investigador

GRAMATICAS REGULARES

Una gramática, G = (V, T, P, S), está formada por cuatro elementos:
1. El alfabeto de variables V.
2. El alfabeto de símbolos terminales T.
3. El conjunto de reglas de producción P.
4. El símbolo inicial S∈V.

La clase Gramática se utilizará para representar cualquier gramática. Así,necesitaremos disponer de las variables de instancia y métodos necesarios para manipularlas de acuerdo con la definición anterior.

alfabeto-corporativo

Analicemos, en primer lugar, qué variables de instancia serán necesarias. Los alfabetos de variables y de símbolos terminales pueden representarse mediante dos objetos de tipo String, asumiendo que los elementos que los componen se dan de manera ordenada y que el primer carácter de la cadena que representa al alfabeto de variables corresponde al símbolo inicial de la gramática.

El conjunto de reglas de producción se representará mediante un objeto de la clase Vector que contendrá a su vez
objetos de la clase Producción.

A la hora de leer y escribir el archivo con la definición de una gramática hay que tener en cuenta cómo se especificarán sus elementos en el mismo.

Por ejemplo, la gramática G = ({S,A}, {a,b}, {S–>aA, A—>aAb|b}, S)  se representará en un archivo de texto de la manera siguiente:
SA
ab
3
S aA
A aAb
A b
Cada una de las filas de este archivo representa:

Primera fila.- Una cadena en la que se especifican, ordenadamente, los símbolos que forman el alfabeto de las variables.

Segunda fila.- Una cadena en la que se especifican, ordenadamente, los símbolos que forman el alfabeto de los símbolos terminales.

Tercera fila.- Número de reglas de producción que componen la gramática.

Cuarta fila.- Primera regla de producción. Se especifica primero la parte izquierda de la regla y, después, la parte derecha ambas separadas por espacios en blanco.

Cuando se trate de una producción nula, A –> e, la cadena vacía se representará por ‘e’.

Siguientes filas.- Resto de reglas de producción.

Una gramática se dice que es regular si sus reglas de producción son de la forma A –> uB ó A —> u

donde u∈T* y A,B∈V. Esta comprobación la llevará a cabo el método boolean esRegular ( ) dentro de la clase Gramática. Una vez, finalizada la implementación de esta clase, dispondremos de todos los elementos necesarios para llevar a la práctica la equivalencia entre AFDs y gramáticas regulares.

De AFD a Gramáticas Regulares

fa

Dado un AFD, M=(Q,∑, δ, q0, F), la gramática regular, G=(V, T, P, S), que genera el mismo lenguaje que acepta M se define:

–  T = ∑,

–  Si q0 no es un estado final, qo ∉ Q, entonces V=Q, S=q0 y las reglas de producción de G son:

– Si d(qi,a) = qj, qi–>aqj
– Si qi∈F, qi–> ε
–  Si q0 es un estado final, entonces hay que añadir una nueva variable inicial S, V = {S}
U Q, y además de las reglas de producción anteriores añadiremos las siguientes: S–>q0,
S–>ε.

Gramática afd2gramatica ( )
de la clase AFD se encargará de realizar el proceso de transformación de AFD a gramática regular descrito. Además deberá modificar el método main de la clase AFD para que también pueda encontrarse la gramática regular equivalente a cualquier AFD.

Para ello el usuario deberá escribir en la línea de órdenes:
AFD <nombre archivo> donde <nombre archivo> indicará la ubicación y nombre del archivo de texto que contiene la definición del autómata cuya que se desea transformar. Como resultado
main visualizará y, después, almacenará en el archivo de texto “afd2gr.txt”, siguiendo la estructura anteriormente indicada, la gramática regular obtenida.

De Gramáticas Regulares a AFNE

Cap207

Dada una gramática regular, G=(V,T,P,S), el AFNE, M=(Q,T,δ,q0,F), que reconoce el mismo lenguaje que genera la gramática viene definido por:

–  Q = {[α] | (α=S) v (∃A∈V, u∈T* tales que A–>uα∈P)}. Es decir, los estados son todas las cadenas formadas por símbolos terminales y variables que se obtienen a partir de la parte derecha de las producciones al ir eliminando símbolo a símbolo desde el
inicio de estas.

P.ej. si la parte derecha de la regla de producción es la cadena 10A,
obtendremos los estados [10A], [0A], [A] y [ε].

–  La función de transición, d, se define de la manera siguiente:
o Si A es una variable, δ([A], e) = {[α] | A–>α∈P}. Es decir, añadiremos tantas producciones nulas como reglas de producción tenga la variable y cada una de ellas conducirá al estado formado por la cadena que aparece en la parte derecha de estas reglas.

o Si a∈T y α∈T*U T*V, entonces δ([aα],a) = {[α]}. Para los estados cuya cadena comienza por un símbolo terminal, iremos consumiendo éste y añadiendo una transición que conduzca al estado formado por la palabra que queda después de
eliminarlo.
–  q0 = [S]
–  F = {[ε]}.
El método
AFNE gramatica2afne ( )
de la clase Gramática se encargará de realizar el proceso descrito de transformación de una gramática regular a AFNE. Además deberá incluir un método main en la clase Gramática para que pueda encontrarse el AFNE equivalente. Para ello el usuario deberá escribir en la línea de órdenes:

Gramática <nombre archivo>
donde <nombre archivo> indicará la ubicación y nombre del archivo de texto que contiene la definición de la gramática regular que se desea transformar.

Como resultado main visualizará y, después, almacenará en el archivo de texto “gr2afne.txt”, siguiendo la estructura anteriormente indicada en la Unidad 2, el AFNE obtenido.

Ejemplos de Gramaticas:

Ejemplo: G = (V, T, P, S) donde:
V = {S, A, B}
T = {a, b}
P = {S–>aB, S–>bA, A–>a, A–>aS, A –>bAA, B–>b,
B–>bS, B–>aBB}

Ejemplo: G = (V, T, P, E) donde:
V = {E}
T = {+, -, ·, (, ), <id>}
P = {E–>E+E, E–>E-E, E–>E·E, E–>(E), E–><id>}

OPERACIONES CON LENGUAJES

operaciones-de-lenguajes
GRAMÁTICA FORMAL
Una gramática formal es un conjunto de reglas de formación para formar cadenas de caracteres a partir de un alfabeto dado. A las cadenas formadas según las reglas de la gramática formal se las llama fórmulas bien formadas, y el conjunto de todas las fórmulas bien formadas constituye un lenguaje formal. Una gramática formal no describe el significado de las fórmulas bien formadas, sino sólamente su forma.

Más precisamente, una gramática formal es un conjunto de reglas para reescribir cadenas de caracteres, junto con un símbolo inicial desde el cual debe comenzar la reescritura. Por lo tanto, una gramática formal generalmente se piensa como una generadora de lenguajes. Sin embargo, a veces también puede ser usada como la base para un “reconocedor”: una función que determina si una cadena cualquiera pertenece a un lenguaje o es gramaticalmente incorrecta.

La teoría de los lenguajes formales estudia las gramáticas formales y los lenguajes formales, y es una rama de la matemática aplicada. Sus aplicaciones se encuentran en la ciencia computacional teórica, la lingüística, la semántica formal, la lógica matemática y otras áreas.

Introducción

Hay distintos tipos de gramáticas formales que generan lenguajes formales (véase la jerarquía de Chomsky). Imaginemos una gramática con estas dos reglas:

1. A → bA
2. A → c

El elemento en mayúsculas es el símbolo inicial. Los elementos en minúsculas son los símbolos terminales. Para generar cadenas de caracteres, la idea es sustituir el símbolo inicial de la izquierda por los símbolos de la derecha, y luego repetir el proceso hasta que sólo haya símbolos terminales. Por ejemplo:

A → bA → bbA → bbbA → bbbc

Esta gramática da lugar a un lenguaje formal que consiste en el conjunto de todas las cadenas de caracteres que pueden ser generadas por medio ellas. Por ejemplo: bbbc, bbbbbbbbc, c, bc, etc.

Para comprender mejor la idea, podemos considerar algunas reglas de la gramática del español:

1. FRASE → SUJETO PREDICADO
2. SUJETO → ARTÍCULO SUSTANTIVO
3. PREDICADO → VERBO COMPLEMENTO
4. ARTÍCULO → el
5. SUSTANTIVO → niño
6. VERBO → duerme
7. COMPLEMENTO → plácidamente

Estas reglas pueden utilizarse para generar la frase “el niño duerme plácidamente”, así:

1. FRASE (símbolo inicial)
2. SUJETO PREDICADO (por la regla 1)
3. ARTÍCULO SUSTANTIVO PREDICADO (por la regla 2)
4. ARTÍCULO SUSTANTIVO VERBO COMPLEMENTO (por la regla 3)
5. el SUSTANTIVO VERBO COMPLEMENTO (por la regla 4)
6. el niño VERBO COMPLEMENTO (por la regla 5)
7. el niño duerme COMPLEMENTO (por la regla 6)
8. el niño duerme plácidamente (por la regla 7)

Vemos que existen unas definiciones especiales como FRASE, SUJETO, etc. que no aparecen en la frase final formada. Son unas entidades abstractas denominadas Categorías Sintácticas que no son utilizables en una frase.

Las categorías sintácticas definen la estructura del lenguaje representando porciones más o menos grandes de las frases. Existe una jerarquía interna entre las categorías sintácticas.

La categoría superior sería la FRASE que representa una oración válida en lengua castellana.

Por debajo de ella se encuentran sus componentes. Ninguna de estas categorías dan lugar a frases válidas solo la categoría superior.

Al finalizar toda la jerarquía llegamos a las palabras que son las unidades mínimas con significado que puede adoptar una frase.

Aplicando las jerarquías y sustituyendo elementos, llegamos al punto en donde todas las categorías sintácticas se han convertido en palabras, obteniendo por tanto una oración válida; como por ejemplo: El niño corre. Este proceso se llama producción o generación.

Algunos enlances
ima_diapositivas
Presentacion sobre Gramaticas
jvc-gz-ms100
Video sobre expresiones regulares
cuaderno
Cuadernillo de Automatas

Bibliografia
* Cueva Lovelle, Juan Manuel,2001, Lenguajes Gramaticas y Automatas , [en linea], Departamento de Informatica, Universidad de Oviedo, [http://www.di.uniovi.es/procesadores/Apuntes/ConceptosBasicos/AUTOMATA.pdf], [Consulta: 27 de octubre del 2010].
* Anonimo,Unidad 4.-Autómatas Finitos y Gramáticas Regulares,[en linea], [http://www.ual.es/~jsagrado/WALF/Archivos/Practicas/Unidad%204.pdf], [Consulta: 27 de octubre del 2010]

Bajo la Licencia de Creative Commons se agradece a los autores de los documentos escritos en la bibliografia y en los enlances.

Licencia de Creative Commons
← Entradas más antiguas GRAMATICAS REGULARES by Juan Diego Romero is licensed under a Creative Commons Attribution 3.0 Ecuador License.
Based on a work at darkjrof.wordpress.com.

Esta entrada fue publicada en Sin categoría. Guarda el enlace permanente.

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s