MiodeMi
Páginas: 6 (1481 palabras)
Publicado: 22 de julio de 2013
Matematica Discreta.- definicion
“Año de la Inversión para el Desarrollo Rural y la Seguridad Alimentaria”
UNIVERSIDAD PERUANA DE INTEGRACIÓN GLOBAL
EN LA FACULTAD DE INGENIERÍA DE SISTEMAS E INFORMÁTICA
Trabajo de Investigación
“Lenguajes Formales, Gramática formal y Árbol de Derivación.”
INTEGRANTE: Kevin CHIPANA ROMÁN
ASESOR: Ing.Luis MUÑOZ RAMOS
CICLO: III
AÑO ACADÉMICO: 2013-I
Lima 23 de Julio del 2013
I. Lenguajes Formales
Un lenguaje formal es un conjunto (finito o infinito) de cadenas finitas de símbolos primitivos.
Ejemplo: El lenguaje “Número” es simplemente el conjunto infinito de cadenas finitas formadas con los dígitos 0, 1, 2, 3, 4, 5, 6, 7, 8 y 9.
Dichas cadenas están formadas gracias aun alfabeto y a una gramática que están formalmente especificados.
El alfabeto es un conjunto finito no vacío de símbolos.
La gramática es un conjunto finito de reglas para formar cadenas finitas juntando símbolos del alfabeto.
A cada cadena de símbolos de un lenguaje formal se le llama fórmula bien formada (o palabra) del lenguaje.
1.1. Clasificación de gramaticales formales
Chomskyclasificó jerárquicamente las gramáticas formales que generan lenguajes formales, en estos tipos:
Tipo 3: Gramáticas regulares que generan lenguajes regulares.
Tipo 2: Gramáticas incontextuales que generan lenguajes incontextuales.
Tipo 1: Gramáticas contextuales que generan lenguajes contextuales.
Tipo 0: Gramáticas libres que generan lenguajes sin ningún tipo de restricción.
Cuanto menor es eltipo, mayor es el poder expresivo del lenguaje generado y más complejidad tiene su tratamiento por parte de una máquina.
1.2. Lenguajes Regulares
Un lenguaje regular es un lenguaje formal que tiene estas características:
Puede ser descrito mediante una expresión regular (expresar de forma compacta cómo son todas las cadenas de símbolos que le pertenecen).
Puede ser generado mediante unagramática regular (obtener todas las cadenas de símbolos que le pertenecen).
Puede ser reconocido mediante un autómata finito (saber si una cadena de símbolos pertenece a él o no).
¡Todas estas características facilitan mucho su tratamiento computacional, por eso nos interesan los lenguajes regulares!
Ejemplos:
Descripción del lenguaje de las cadenas que empiezan por una “a” y continúan con“a’s” y “b’s”.
a(a|b)*
Descripción del lenguaje de las cadenas que empiezan por “a”, continúan con “b’s” y “c’s” y terminan en “d”.
a(b|c)*d
Descripción del lenguaje de las cadenas formadas por trozos de cadena que pueden empezar (o no) por una “a” y continúan con un número que tenga al menos un dígito; además terminan siempre en asterisco *.
(a?[0-9]+)*\*
II. Gramática FormalUna gramática formal es un objeto o modelo matemático que permite especificar un lenguaje o lengua, es decir, es el conjunto de reglas capaces de generar todas las posibilidades combinarías de ese lenguaje, ya sea éste un lenguaje formal o un lenguaje natural.
Tiene como estructura, G = (V, T, P So,) donde las siguientes letras representan:
“V: Símbolos Variables”
“T: Símbolos Terminales”“P: Producciones o reglas sintácticas”
“So: Símbolo Inicial”
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": unafunción que determina si una cadena cualquiera pertenece a un lenguaje o es gramaticalmente incorrecta.
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...
Matematica Discreta.- definicion
“Año de la Inversión para el Desarrollo Rural y la Seguridad Alimentaria”
UNIVERSIDAD PERUANA DE INTEGRACIÓN GLOBAL
EN LA FACULTAD DE INGENIERÍA DE SISTEMAS E INFORMÁTICA
Trabajo de Investigación
“Lenguajes Formales, Gramática formal y Árbol de Derivación.”
INTEGRANTE: Kevin CHIPANA ROMÁN
ASESOR: Ing.Luis MUÑOZ RAMOS
CICLO: III
AÑO ACADÉMICO: 2013-I
Lima 23 de Julio del 2013
I. Lenguajes Formales
Un lenguaje formal es un conjunto (finito o infinito) de cadenas finitas de símbolos primitivos.
Ejemplo: El lenguaje “Número” es simplemente el conjunto infinito de cadenas finitas formadas con los dígitos 0, 1, 2, 3, 4, 5, 6, 7, 8 y 9.
Dichas cadenas están formadas gracias aun alfabeto y a una gramática que están formalmente especificados.
El alfabeto es un conjunto finito no vacío de símbolos.
La gramática es un conjunto finito de reglas para formar cadenas finitas juntando símbolos del alfabeto.
A cada cadena de símbolos de un lenguaje formal se le llama fórmula bien formada (o palabra) del lenguaje.
1.1. Clasificación de gramaticales formales
Chomskyclasificó jerárquicamente las gramáticas formales que generan lenguajes formales, en estos tipos:
Tipo 3: Gramáticas regulares que generan lenguajes regulares.
Tipo 2: Gramáticas incontextuales que generan lenguajes incontextuales.
Tipo 1: Gramáticas contextuales que generan lenguajes contextuales.
Tipo 0: Gramáticas libres que generan lenguajes sin ningún tipo de restricción.
Cuanto menor es eltipo, mayor es el poder expresivo del lenguaje generado y más complejidad tiene su tratamiento por parte de una máquina.
1.2. Lenguajes Regulares
Un lenguaje regular es un lenguaje formal que tiene estas características:
Puede ser descrito mediante una expresión regular (expresar de forma compacta cómo son todas las cadenas de símbolos que le pertenecen).
Puede ser generado mediante unagramática regular (obtener todas las cadenas de símbolos que le pertenecen).
Puede ser reconocido mediante un autómata finito (saber si una cadena de símbolos pertenece a él o no).
¡Todas estas características facilitan mucho su tratamiento computacional, por eso nos interesan los lenguajes regulares!
Ejemplos:
Descripción del lenguaje de las cadenas que empiezan por una “a” y continúan con“a’s” y “b’s”.
a(a|b)*
Descripción del lenguaje de las cadenas que empiezan por “a”, continúan con “b’s” y “c’s” y terminan en “d”.
a(b|c)*d
Descripción del lenguaje de las cadenas formadas por trozos de cadena que pueden empezar (o no) por una “a” y continúan con un número que tenga al menos un dígito; además terminan siempre en asterisco *.
(a?[0-9]+)*\*
II. Gramática FormalUna gramática formal es un objeto o modelo matemático que permite especificar un lenguaje o lengua, es decir, es el conjunto de reglas capaces de generar todas las posibilidades combinarías de ese lenguaje, ya sea éste un lenguaje formal o un lenguaje natural.
Tiene como estructura, G = (V, T, P So,) donde las siguientes letras representan:
“V: Símbolos Variables”
“T: Símbolos Terminales”“P: Producciones o reglas sintácticas”
“So: Símbolo Inicial”
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": unafunción que determina si una cadena cualquiera pertenece a un lenguaje o es gramaticalmente incorrecta.
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...
Leer documento completo
Regístrate para leer el documento completo.