Algoritmos

1. Autómatas y lenguajes formales 2

1.1 Definición de alfabeto 2
1.2 Definición de frase 2
1.3 Definición de cadena vacía 3
1.4 Definición de lenguaje 3
Lenguaje máquina 3
Lenguaje ensamblador 3
Lenguajes de bajo nivel 4
Lenguajes de alto nivel 4
1.4 Gramáticas formales 6
1.6 Definición de lenguaje formal 6
1.7 Jerarquización de gramáticas 7
Tipo 0 SinRestricciones 7
1.7.1 Gramáticas sensibles al contexto 8
1.7.2 Gramáticas independientes o libres de contexto
1.7.3 Gramáticas regulares 8
1.8 Propiedades de indecibilidad 9
Teorema de Gödel 9

Bibliografía 11














































1. Autómatas y lenguajes formales


Un autómata es una construcción lógicaque recibe una entrada y produce una salida en función a todo lo recibido hasta ese instante. En el caso de los procesadores de lenguajes un autómata es una construcción lógica que recibe como entrada una cadena de símbolos y produce una salida indicando si dicha cadena pertenece o no a un determinado lenguaje.


1.1 Definición de alfabeto


Se conoce como un conjunto no vacío y finito desímbolos. Por ejemplo el alfabeto español está formado por 28 símbolos. También se considera como alfabeto a la colección de todas las palabras españolas correctas o a la colección de todos los símbolos legales del lenguaje de programación Pascal (identificadores, palabras clave y reservadas, caracteres especiales, etc.).

Una secuencia finita de símbolos de un determinado alfabeto se conoce comopalabra sobre dicho alfabeto. Por ejemplo, si tenemos el alfabeto español, algunas palabras pueden ser PROGRAMA, DIGITO, LUNA, MONITOR. Pero ésta definición también permite que BHJKJG y NSDF sean también palabras. Sin embargo, usar el término palabra nos puede confundir con las palabras de algún lenguaje natural. Es por esto, que a menudo se usa el término cadena en lugar de palabra con el fin deevitar una idea preconcebida.


1.2 Definición de frase


La frase es el conjunto de instrucciones de un programa, éstas tiene sentido, significado y lógica. Por su parte, las reglas de un lenguaje de programación están compuestas por la sintaxis y la semántica (significado). Las reglas de sintaxis se definen como las palabras (o vocabulario) del lenguaje que se pueden poner juntas paraformar frases. Son datos compuestos por una secuencia de caracteres, que normalmente representan un texto legible. Es posible que la longitud de una frase o cadena no sea la misma que su tamaño máximo asignado. Como consecuencia, algunos lenguajes disponen de formas de controlar la longitud de una cadena, normalmente usando un carácter de delimitación al final o contando el número de caracteres. Porejemplo, si nuestro alfabeto base es el conjunto de todos los identificadores legales de Pascal cuya longitud es menor o igual que una constante, las palabras clave y reservadas, los símbolos especiales de Pascal, y así sucesivamente, un programa en Pascal bien construido, es una cadena. De la misma forma que basándonos en la definición se pueden formar palabras incorrectas a partir del alfabetoespañol también se pueden formar programas incorrectos sobre el alfabeto de Pascal. Las cadenas que constituyen programas en Pascal bien construidos deben cumplir ciertas restricciones, al igual que las palabras en español “legales” se construyen de una determinada manera sobre el alfabeto español.


1.3 Definición de cadena vacía


Cada símbolo de un alfabeto es una cadena sobre dichoalfabeto. La cadena vacía la cual se denota por el símbolo (, es una palabra sobre cualquier alfabeto. La palabra vacía es una secuencia vacía de símbolos tomados de cualquiera que sea el alfabeto en cuestión.


1.4 Definición de lenguaje


Un lenguaje es un conjunto de palabras o cadenas. Por ejemplo, el conjunto (1,12,123,1234) es un lenguaje sobre el alfabeto compuesto por dígitos. De forma...