Gramaticas Y Lenguajes Formales

UNIDAD I: GRAMÁTICAS Y LENGUAJES FORMALES TEORÍA DE LA COMPUTACIÓN
1.1.- Conceptos Introductorios.
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 lenguajeformal. Una gramática formal no describe el significado de las fórmulas bien formadas, sino solamente
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.
Un lenguaje formal es un lenguaje cuyos símbolos primitivos y reglas para unir esos símbolos están
formalmente especificados. Al conjunto de los símbolos primitivos se le llama el alfabeto (o vocabulario)
del lenguaje, y al conjunto de las reglas se lo llama la gramática formal (o sintaxis). A una cadena de
símbolos formada de acuerdoa la gramática se la llama una fórmula bien formada (o palabra) del
lenguaje. Estrictamente hablando, un lenguaje formal es idéntico al conjunto de todas sus fórmulas bien
formadas. A diferencia de lo que ocurre con el alfabeto (que debe ser un conjunto finito) y con cada
fórmula bien formada (que debe tener una longitud también finita), un lenguaje formal puede estar
compuesto por un númeroinfinito de fórmulas bien formadas.
1.2.- Lenguajes Formales y sus Operaciones.

En matemáticas, lógica, y las ciencias computacionales, un lenguaje formal es un conjunto de
palabras (cadenas de caracteres) de longitud finita formadas a partir de un alfabeto (conjunto
de caracteres) finito.
Informalmente, el término lenguaje formal se utiliza en muchos contextos (en las ciencias, enderecho, etc.) para referirse a un modo de expresión más cuidadoso y preciso que el habla
cotidiana. Hasta finales de la década de 1990, el consenso general era que un lenguaje formal,
en el sentido que trata este artículo, era en cierto modo la versión «límite» de este uso antes
mencionado: un lenguaje tan formalizado que podía ser usado en forma escrita para describir
métodos computacionales. Sinembargo, hoy en día, el punto de vista de que la naturaleza
esencial de los lenguajes naturales (sin importar su grado de «formalidad» en el sentido
informal antes descrito) difiere de manera importante de aquella de los verdaderos lenguajes
formales (en el sentido estricto de este artículo) gana cada vez más adeptos.
Un posible alfabeto sería, digamos, {a, b}, y una cadena cualquiera sobreeste alfab eto sería,
por ejemplo, ababba. Un lenguaje sobre este alfabeto, que incluyera esta cadena, sería: el
ING. SANTO RUBIO PANO / PROFESOR DE ASIGNATURA

Página 1

UNIDAD I: GRAMÁTICAS Y LENGUAJES FORMALES TEORÍA DE LA COMPUTACIÓN
conjunto de todas las cadenas que contienen el mismo número de símbolos a que b, por
ejemplo.
La palabra vacía (esto es, la cadena de longitud cero) esp ermitida y frecuentemente denotada
mediante ε o λ. Mientras que el alfabeto es un conjunto finito y cada palabra tiene una longitud
también finita, un lenguaje puede bien incluir un número infinito de palabras.
Algunos ejemplos varios de lenguajes formales:
* El conjunto de todas las palabras sobre {a, b}
* El conjunto {an: n es un número primo}
* El conjunto de todos los programas...