Que tal compañeros del 6to cuatrimestre de Ingenieria en Sistemas
Este es mi blog y les doy la mas cordial bienvenida...
Hay que seguir hechandole aun mas ganas para poder seguir y terminar con esta meta que nos pusimos, espero que los ochos que estamos ahorita nos veamos hasta el 9no. cuatrimestre, hay que apoyarnos y animo, mucho animo
Son los deseos de su compañera y amiga
Tayde Jimenez
viernes, 10 de septiembre de 2010
viernes, 4 de junio de 2010
Reglas de Programación y Programa invento
* jive [libro.c]
* jive [estudio.c]
ent a,b,c.
inicio()
{
imp//”Dame valor A”.
alm%a.
Iip//Dame valor B”.
alm%b.
c=a+b.
imp//c.
}
Reglas claves con las que se cumple:
3-6 se cumple al utilizar nombres de variables que realizan funciones similares
4-1 escribe una sentencia por línea
Reglas claves con las que no se cumple:
1-2 no cumple ya que el .c se encuentra en la parte pública y no en la privada
Por lo tanto para que cumpla el programa con las reglas, solo se tendra que cambiar en las librerías el .c por el .h
Reglas de Programación del libro Elementos de Estilo en C
Capítulo 1: Estilo y Organización de Programas
Regla 1-1: Organiza los programas para legibilidad, al igual que esperarías que un autor organizaría un libro.
Regla 1-2: Divide cada módulo en un parte pública (lo que se requiere para usar el módulo) y una parte privada (lo que se requiere para hacer el trabajo). La parte pública va en un archivo .h mientras que la parte privada va en un archivo .c .
Regla 1-3: Usa espacios en blanco para separar una función en párrafos.
Regla 1-4: Coloca cada sentencia en su propia línea.
Regla 1-5: Evita sentencias muy largas. Usa en su lugar sentencias múltiples más cortas.
Capítulo 2: Fundamentos de Archivos, Comentarios, y Encabezados de Programas
Regla 2-1: Mantén los archivos de programas no mayores a 2,000 ó 3,000 líneas.
Regla 2-2: Mantén todas las líneas de tu programa debajo de 72 caracteres o menos.
Regla 2-3: Usa paradas de tabuladores de 8 caracteres.
Regla 2-4: Usa solamente los 95 caracteres ASCII estándar en tus programas. Evita caracteres exóticos. (Los caracteres extranjeros pueden ser usados si estás escribiendo comentarios en una lengua extranjera.)
Regla 2-5: Incluye un comentario de cabecera al comienzo de cada archivo que explique el archivo.
Regla 2-6: Deja fuera los comentarios innecesarios si ellos requieren mantenimiento y no estás dispuesto a dárselo.
Regla 2-7: Comenta tu código mientras lo escribes.
Capítulo 3: Nombres de Variables
Regla 3-1: Usa nombres de variable simples y descriptivos.
Regla 3-2: Los buenos nombres de variable se crean usando una palabra o juntando dos o tres palabras, separadas por "_" (guión bajo).
Regla 3-3: Nunca uses l (L minúscula) o O (O mayúscula) como nombres de variables o constantes.
Regla 3-4: No uses los nombres de funciones o de constantes de biblioteca existentes.
Regla 3-5: No uses nombres de variables que difieran por uno o dos caracteres. Haz cada nombre obviamente diferente de cada uno de los demás.
Regla 3-6: Usa nombres similares para variables que realizan funciones similares.
Regla 3-7: Cuando crees un nombre de variable de dos palabras donde las palabras puedan ser puestas en cualquier orden, siempre coloca de primero la más importante.
Regla 3-8: Los prefijos y sufijos estándar son _ptr, _p, _file, _fd, y n_.
Regla 3-9: Los nombres cortos tales como x, y, y i son aceptables cuando su significado es claro y cuando un nombre largo no añadiría información o claridad adicional.
Rule 3-10: Use argc para el número de argumentos de la línea de comandos y argv para la lista de argumentos. No uses esos nombres para nada más.
Regla 3-11: Sigue cada declaración de variable con un comentario que la defina.
Regla 3-12: Cuando sea posible, incluye las unidades de medida en la descripción de una variable.
Regla 3-13: Nombra y comenta cada campo de una estructura o unión igual que una variable.
Regla 3-14: Inicia cada definición de estructura o unión con un comentario multilínea describiéndola.
Regla 3-15: Coloca al menos una línea en blanco antes y después de la definición de una estructura o unión.
Regla 3-16: Cuando no puedas poner un comentario descriptivo al final de una declaración de variable, colócalo en una línea separada arriba de ella. Usa líneas en blanco para separar el par declaración/comentario del resto del código.
Regla 3-17: Agrupa variables similares juntas. Cuando sea posible, usa la misma estructura para cada grupo.
Regla 3-18: No uses variables escondidas.
Regla 3-19: Usa los nombres INT16, INT32, UINT16, y UINT32 para aplicaciones portables.
Regla 3-20: Los números de punto flotante deben tener al menos un dígito a ambos lados del punto decimal.
Regla 3-21: El exponente en un número de punto flotante debe ser una e minúscula. Esta es siempre seguida por un signo.
Regla 3-22: Empieza los números hexadecimales con Ox. (x minúscula solamente.)
Regla 3-23: Usa letras mayúsculas de la A a la F cuando construyas constantes hexadecimales.
Regla 3-24: Las constantes largas deberían terminar con una L mayúscula.
Capítulo 4: Formateo de Sentencias
Regla 4-1: Escribe una sentencia por línea.
Regla 4-2: Coloca espacios antes y después de cada operador aritmético, al igual que colocas espacios entre las palabras cuando escribes.
Regla 4-3: Cambia una sentencia larga y compleja por varias sentencias más pequeñas y más simples.
Regla 4-4: En una sentencia que consiste de dos o más líneas, cada línea excepto la primera debe indentarse un nivel extra para indicar que es una continuación de la primera.
Regla 4-5: Cuando escribas sentencias multilíneas, coloca los operadores aritméticos y lógicos al final de cada línea.
Regla 4-6: Cuando dividas una línea, el punto preferido de división es donde el anidamiento de los paréntesis sea menor.
Regla 4-7: Alinea verticalmente los niveles de paréntesis.
Regla 4-8: Divide las sentencias for largas en los límites de sus sentencias.
Regla 4-9: Siempre divide una sentencia for en tres líneas.
Regla 4-10: Escribe las sentencias switch en una línea independiente.
Regla 4-11: Mantén los condicionales en una única línea si es posible.
Regla 4-12: Cuando dividas una cláusula condicional (?:), escríbela en tres líneas: la línea de la condición, la línea del valor verdadero, y la línea del valor falso. Indenta la segunda y la tercera línea un nivel extra.
Regla 4-13: Evita los efectos colaterales.
Regla 4-14: Coloca los operadores ++ y -- en sus propias líneas. No uses ++ y -- dentro de otras sentencias.
Regla 4-15: Nunca coloques una sentencia de asignación dentro de otra sentencia.
Regla 4-16: Si el colocar dos o más sentencias en una misma línea mejora la claridad del programa, entonces hazlo así.
Regla 4-17: Cuando uses más de una sentencia por línea, organiza las sentencias en columnas.
Regla 4-18: Indenta un nivel para cada nuevo nivel de lógica.
Regla 4-19: El mejor tamaño de indentación es de cuatro espacios.
Capítulo 5: Detalles de Sentencias
Regla 5-1: Coloca siempre un comentario en la sentencia nula, aún si es la única.
Regla 5-2: En las expresiones en C, puedes asumir que *, /, y % vienen después de + y -. Coloca paréntesis alrededor de todo lo demás.
Regla 5-3: Usa declaraciones de funciones estilo ANSI siempre que sea posible.
Regla 5-4: Cuando uses parámetros tipo K&R (Kernighan&Ritchie), declara un tipo para cada parámetro.
Regla 5-5: Cuando uses parámetros tipo K&R (Kernighan&Ritchie), coloca la declaración de tipo de los parámetros en el mismo orden en que aparecen en la cabecera de la función.
Regla 5-6: Siempre declara un tipo para la función.
Regla 5-7: Siempre declara funciones que no retornan un valor como void.
Regla 5-8: No permitas más de 5 parámetros para una función.
Regla 5-9: Evita usar variables globales cuando los parámetros de la función pueden bastar.
Regla 5-10: Evita las listas de parámetros de longitud variable. Son difíciles de programar y fácilmente pueden causar problemas.
Regla 5-11: Cuando un if afecta a más de una línea, enciérralas entre llaves.
Regla 5-12: En una cadena de if, trata las palabras else if como una única palabra clave.
Regla 5-13: Nunca uses el operador coma cuando en su lugar puedas usar llaves.
Regla 5-14: Cuando crees ciclos infinitos, usa while (1) en lugar de for(;;).
Regla 5-15: Evita usar do/while. Usa en su lugar while y break.
Regla 5-16: Usa el operador coma dentro de una sentencia for solamente para poner juntas dos sentencias. Nunca lo uses para combinar tres sentencias.
Regla 5-17: Usa un printf por línea de salida.
Regla 5-18: A menos que se garantice la extrema eficiencia, usa printf en lugar de puts y putc.
Regla 5-19: Empieza las etiquetas goto en la primer columna.
Regla 5-20: Termina cada case en un switch con un break o el comentario /* El flujo continúa en el siguiente case */.
Regla 5-21: Siempre coloca un break al final del último case en una sentencia switch.
Regla 5-22: Siempre incluye un caso default en cada switch, aún cuando no contenga más que la sentencia nula.
Capítulo 6: Preprocesador
Regla 6-1: Las constantes #define se declaran como variables. Siempre coloca un comentario que describa a la constante después de cada declaración.
Regla 6-2: Los nombres de constantes son todos en mayúsculas.
Regla 6-3: Si el valor de una constante es algo más que un simple número, enciérralo entre paréntesis.
Regla 6-4: El uso de const se prefiere sobre #define para especificar constantes.
Regla 6-5: Cuando sea posible, usa typedef en lugar de #define.
Regla 6-6: No uses #define para definir nuevos elementos de lenguaje.
Regla 6-7: Nunca uses #define para redefinir palabras claves o funciones estándar de C.
Regla 6-8: Encierra las macros parametrizadas entre paréntesis.
Regla 6-9: Encierra cada argumento para una macro parametrizada entre paréntesis.
Regla 6-10: Siempre encierra las macros que definen múltiple sentencias de C entre llaves.
Regla 6-11: Si una macro contiene más de una sentencia, usa una estructura do/while para encerrar la macro. (No olvides dejar el punto y coma de la sentencia).
Regla 6-12: Cuando crees macros multilíneas, alinea los caracteres de continuación diagonal inversa (\) en una columna.
Regla 6-13: Comenta siempre cualquier macro parametrizada que se vea como una función.
Regla 6-14: Las directivas #include vienen justo después de los comentario de encabezado. Coloca primero las inclusiones del sistema, seguidas de las inclusiones locales.
Regla 6-15: No uses rutas absolutas en las directivas #include. Deja que la opción -I haga el trabajo.
Regla 6-16: Comenta las directivas #else y #endif con el símbolo usado en el #ifdef inicial o la directiva #endif.
Regla 6-17: Usa prudentemente la compilación condicional. No permitas que los condicionales oscurezcan el código.
Regla 6-18: Define (o no definas) el control de compilación de símbolo condicional en el código en lugar de usar la opción -D para el compilador.
Regla 6-19: Coloca las sentencias #define y #undef para control de compilación de símbolos al comienzo del programa.
Regla 6-20: No comentes código no utilizado. Usa la compilación condicional (#ifdef #undef) para deshacerte del código no deseado.
Regla 6-21: Usa #ifdef QQQ para eliminar código temporalmente durante la depuración.
Capítulo 7: Estilo de Organización de Directorio y Makefile
Regla 7-1: Siempre que sea posible, coloca todos los archivos para un programa o biblioteca en un mismo directorio.
Capítulo 8: Programación Amistosa con el Usuario
Regla 8-1: Ley de la Menor Sorpresa: El programa debería actuar de la manera que menos sorprenda al usuario.
Regla 8-2: Empieza cada mensaje de error con el rótulo Error:. Inicia cada mensaje de advertencia con Advertencia:.
* jive [estudio.c]
ent a,b,c.
inicio()
{
imp//”Dame valor A”.
alm%a.
Iip//Dame valor B”.
alm%b.
c=a+b.
imp//c.
}
Reglas claves con las que se cumple:
3-6 se cumple al utilizar nombres de variables que realizan funciones similares
4-1 escribe una sentencia por línea
Reglas claves con las que no se cumple:
1-2 no cumple ya que el .c se encuentra en la parte pública y no en la privada
Por lo tanto para que cumpla el programa con las reglas, solo se tendra que cambiar en las librerías el .c por el .h
Reglas de Programación del libro Elementos de Estilo en C
Capítulo 1: Estilo y Organización de Programas
Regla 1-1: Organiza los programas para legibilidad, al igual que esperarías que un autor organizaría un libro.
Regla 1-2: Divide cada módulo en un parte pública (lo que se requiere para usar el módulo) y una parte privada (lo que se requiere para hacer el trabajo). La parte pública va en un archivo .h mientras que la parte privada va en un archivo .c .
Regla 1-3: Usa espacios en blanco para separar una función en párrafos.
Regla 1-4: Coloca cada sentencia en su propia línea.
Regla 1-5: Evita sentencias muy largas. Usa en su lugar sentencias múltiples más cortas.
Capítulo 2: Fundamentos de Archivos, Comentarios, y Encabezados de Programas
Regla 2-1: Mantén los archivos de programas no mayores a 2,000 ó 3,000 líneas.
Regla 2-2: Mantén todas las líneas de tu programa debajo de 72 caracteres o menos.
Regla 2-3: Usa paradas de tabuladores de 8 caracteres.
Regla 2-4: Usa solamente los 95 caracteres ASCII estándar en tus programas. Evita caracteres exóticos. (Los caracteres extranjeros pueden ser usados si estás escribiendo comentarios en una lengua extranjera.)
Regla 2-5: Incluye un comentario de cabecera al comienzo de cada archivo que explique el archivo.
Regla 2-6: Deja fuera los comentarios innecesarios si ellos requieren mantenimiento y no estás dispuesto a dárselo.
Regla 2-7: Comenta tu código mientras lo escribes.
Capítulo 3: Nombres de Variables
Regla 3-1: Usa nombres de variable simples y descriptivos.
Regla 3-2: Los buenos nombres de variable se crean usando una palabra o juntando dos o tres palabras, separadas por "_" (guión bajo).
Regla 3-3: Nunca uses l (L minúscula) o O (O mayúscula) como nombres de variables o constantes.
Regla 3-4: No uses los nombres de funciones o de constantes de biblioteca existentes.
Regla 3-5: No uses nombres de variables que difieran por uno o dos caracteres. Haz cada nombre obviamente diferente de cada uno de los demás.
Regla 3-6: Usa nombres similares para variables que realizan funciones similares.
Regla 3-7: Cuando crees un nombre de variable de dos palabras donde las palabras puedan ser puestas en cualquier orden, siempre coloca de primero la más importante.
Regla 3-8: Los prefijos y sufijos estándar son _ptr, _p, _file, _fd, y n_.
Regla 3-9: Los nombres cortos tales como x, y, y i son aceptables cuando su significado es claro y cuando un nombre largo no añadiría información o claridad adicional.
Rule 3-10: Use argc para el número de argumentos de la línea de comandos y argv para la lista de argumentos. No uses esos nombres para nada más.
Regla 3-11: Sigue cada declaración de variable con un comentario que la defina.
Regla 3-12: Cuando sea posible, incluye las unidades de medida en la descripción de una variable.
Regla 3-13: Nombra y comenta cada campo de una estructura o unión igual que una variable.
Regla 3-14: Inicia cada definición de estructura o unión con un comentario multilínea describiéndola.
Regla 3-15: Coloca al menos una línea en blanco antes y después de la definición de una estructura o unión.
Regla 3-16: Cuando no puedas poner un comentario descriptivo al final de una declaración de variable, colócalo en una línea separada arriba de ella. Usa líneas en blanco para separar el par declaración/comentario del resto del código.
Regla 3-17: Agrupa variables similares juntas. Cuando sea posible, usa la misma estructura para cada grupo.
Regla 3-18: No uses variables escondidas.
Regla 3-19: Usa los nombres INT16, INT32, UINT16, y UINT32 para aplicaciones portables.
Regla 3-20: Los números de punto flotante deben tener al menos un dígito a ambos lados del punto decimal.
Regla 3-21: El exponente en un número de punto flotante debe ser una e minúscula. Esta es siempre seguida por un signo.
Regla 3-22: Empieza los números hexadecimales con Ox. (x minúscula solamente.)
Regla 3-23: Usa letras mayúsculas de la A a la F cuando construyas constantes hexadecimales.
Regla 3-24: Las constantes largas deberían terminar con una L mayúscula.
Capítulo 4: Formateo de Sentencias
Regla 4-1: Escribe una sentencia por línea.
Regla 4-2: Coloca espacios antes y después de cada operador aritmético, al igual que colocas espacios entre las palabras cuando escribes.
Regla 4-3: Cambia una sentencia larga y compleja por varias sentencias más pequeñas y más simples.
Regla 4-4: En una sentencia que consiste de dos o más líneas, cada línea excepto la primera debe indentarse un nivel extra para indicar que es una continuación de la primera.
Regla 4-5: Cuando escribas sentencias multilíneas, coloca los operadores aritméticos y lógicos al final de cada línea.
Regla 4-6: Cuando dividas una línea, el punto preferido de división es donde el anidamiento de los paréntesis sea menor.
Regla 4-7: Alinea verticalmente los niveles de paréntesis.
Regla 4-8: Divide las sentencias for largas en los límites de sus sentencias.
Regla 4-9: Siempre divide una sentencia for en tres líneas.
Regla 4-10: Escribe las sentencias switch en una línea independiente.
Regla 4-11: Mantén los condicionales en una única línea si es posible.
Regla 4-12: Cuando dividas una cláusula condicional (?:), escríbela en tres líneas: la línea de la condición, la línea del valor verdadero, y la línea del valor falso. Indenta la segunda y la tercera línea un nivel extra.
Regla 4-13: Evita los efectos colaterales.
Regla 4-14: Coloca los operadores ++ y -- en sus propias líneas. No uses ++ y -- dentro de otras sentencias.
Regla 4-15: Nunca coloques una sentencia de asignación dentro de otra sentencia.
Regla 4-16: Si el colocar dos o más sentencias en una misma línea mejora la claridad del programa, entonces hazlo así.
Regla 4-17: Cuando uses más de una sentencia por línea, organiza las sentencias en columnas.
Regla 4-18: Indenta un nivel para cada nuevo nivel de lógica.
Regla 4-19: El mejor tamaño de indentación es de cuatro espacios.
Capítulo 5: Detalles de Sentencias
Regla 5-1: Coloca siempre un comentario en la sentencia nula, aún si es la única.
Regla 5-2: En las expresiones en C, puedes asumir que *, /, y % vienen después de + y -. Coloca paréntesis alrededor de todo lo demás.
Regla 5-3: Usa declaraciones de funciones estilo ANSI siempre que sea posible.
Regla 5-4: Cuando uses parámetros tipo K&R (Kernighan&Ritchie), declara un tipo para cada parámetro.
Regla 5-5: Cuando uses parámetros tipo K&R (Kernighan&Ritchie), coloca la declaración de tipo de los parámetros en el mismo orden en que aparecen en la cabecera de la función.
Regla 5-6: Siempre declara un tipo para la función.
Regla 5-7: Siempre declara funciones que no retornan un valor como void.
Regla 5-8: No permitas más de 5 parámetros para una función.
Regla 5-9: Evita usar variables globales cuando los parámetros de la función pueden bastar.
Regla 5-10: Evita las listas de parámetros de longitud variable. Son difíciles de programar y fácilmente pueden causar problemas.
Regla 5-11: Cuando un if afecta a más de una línea, enciérralas entre llaves.
Regla 5-12: En una cadena de if, trata las palabras else if como una única palabra clave.
Regla 5-13: Nunca uses el operador coma cuando en su lugar puedas usar llaves.
Regla 5-14: Cuando crees ciclos infinitos, usa while (1) en lugar de for(;;).
Regla 5-15: Evita usar do/while. Usa en su lugar while y break.
Regla 5-16: Usa el operador coma dentro de una sentencia for solamente para poner juntas dos sentencias. Nunca lo uses para combinar tres sentencias.
Regla 5-17: Usa un printf por línea de salida.
Regla 5-18: A menos que se garantice la extrema eficiencia, usa printf en lugar de puts y putc.
Regla 5-19: Empieza las etiquetas goto en la primer columna.
Regla 5-20: Termina cada case en un switch con un break o el comentario /* El flujo continúa en el siguiente case */.
Regla 5-21: Siempre coloca un break al final del último case en una sentencia switch.
Regla 5-22: Siempre incluye un caso default en cada switch, aún cuando no contenga más que la sentencia nula.
Capítulo 6: Preprocesador
Regla 6-1: Las constantes #define se declaran como variables. Siempre coloca un comentario que describa a la constante después de cada declaración.
Regla 6-2: Los nombres de constantes son todos en mayúsculas.
Regla 6-3: Si el valor de una constante es algo más que un simple número, enciérralo entre paréntesis.
Regla 6-4: El uso de const se prefiere sobre #define para especificar constantes.
Regla 6-5: Cuando sea posible, usa typedef en lugar de #define.
Regla 6-6: No uses #define para definir nuevos elementos de lenguaje.
Regla 6-7: Nunca uses #define para redefinir palabras claves o funciones estándar de C.
Regla 6-8: Encierra las macros parametrizadas entre paréntesis.
Regla 6-9: Encierra cada argumento para una macro parametrizada entre paréntesis.
Regla 6-10: Siempre encierra las macros que definen múltiple sentencias de C entre llaves.
Regla 6-11: Si una macro contiene más de una sentencia, usa una estructura do/while para encerrar la macro. (No olvides dejar el punto y coma de la sentencia).
Regla 6-12: Cuando crees macros multilíneas, alinea los caracteres de continuación diagonal inversa (\) en una columna.
Regla 6-13: Comenta siempre cualquier macro parametrizada que se vea como una función.
Regla 6-14: Las directivas #include vienen justo después de los comentario de encabezado. Coloca primero las inclusiones del sistema, seguidas de las inclusiones locales.
Regla 6-15: No uses rutas absolutas en las directivas #include. Deja que la opción -I haga el trabajo.
Regla 6-16: Comenta las directivas #else y #endif con el símbolo usado en el #ifdef inicial o la directiva #endif.
Regla 6-17: Usa prudentemente la compilación condicional. No permitas que los condicionales oscurezcan el código.
Regla 6-18: Define (o no definas) el control de compilación de símbolo condicional en el código en lugar de usar la opción -D para el compilador.
Regla 6-19: Coloca las sentencias #define y #undef para control de compilación de símbolos al comienzo del programa.
Regla 6-20: No comentes código no utilizado. Usa la compilación condicional (#ifdef #undef) para deshacerte del código no deseado.
Regla 6-21: Usa #ifdef QQQ para eliminar código temporalmente durante la depuración.
Capítulo 7: Estilo de Organización de Directorio y Makefile
Regla 7-1: Siempre que sea posible, coloca todos los archivos para un programa o biblioteca en un mismo directorio.
Capítulo 8: Programación Amistosa con el Usuario
Regla 8-1: Ley de la Menor Sorpresa: El programa debería actuar de la manera que menos sorprenda al usuario.
Regla 8-2: Empieza cada mensaje de error con el rótulo Error:. Inicia cada mensaje de advertencia con Advertencia:.
Mi Lenguaje
* jive [libro.c]
* jive [estudio.c]
ent a,b,c.
inicio()
{
imp//”Dame valor A”.
alm%a.
Iip//Dame valor B”.
alm%b.
c=a+b.
imp//c.
}
Reglas claves con las que se cumple:
3-6 se cumple al utilizar nombres de variables que realizan funciones similares
4-1 escribe una sentencia por línea
Reglas claves con las que no se cumple:
1-2 no cumple ya que el .c se encuentra en la parte pública y no en la privada
Por lo tanto para que cumpla el programa con las reglas, solo se tendra que cambiar en las librerías el .c por el .h
Reglas de Programación del libro Elementos de Estilo en C
Capítulo 1: Estilo y Organización de Programas
Regla 1-1: Organiza los programas para legibilidad, al igual que esperarías que un autor organizaría un libro.
Regla 1-2: Divide cada módulo en un parte pública (lo que se requiere para usar el módulo) y una parte privada (lo que se requiere para hacer el trabajo). La parte pública va en un archivo .h mientras que la parte privada va en un archivo .c .
Regla 1-3: Usa espacios en blanco para separar una función en párrafos.
Regla 1-4: Coloca cada sentencia en su propia línea.
Regla 1-5: Evita sentencias muy largas. Usa en su lugar sentencias múltiples más cortas.
Capítulo 2: Fundamentos de Archivos, Comentarios, y Encabezados de Programas
Regla 2-1: Mantén los archivos de programas no mayores a 2,000 ó 3,000 líneas.
Regla 2-2: Mantén todas las líneas de tu programa debajo de 72 caracteres o menos.
Regla 2-3: Usa paradas de tabuladores de 8 caracteres.
Regla 2-4: Usa solamente los 95 caracteres ASCII estándar en tus programas. Evita caracteres exóticos. (Los caracteres extranjeros pueden ser usados si estás escribiendo comentarios en una lengua extranjera.)
Regla 2-5: Incluye un comentario de cabecera al comienzo de cada archivo que explique el archivo.
Regla 2-6: Deja fuera los comentarios innecesarios si ellos requieren mantenimiento y no estás dispuesto a dárselo.
Regla 2-7: Comenta tu código mientras lo escribes.
Capítulo 3: Nombres de Variables
Regla 3-1: Usa nombres de variable simples y descriptivos.
Regla 3-2: Los buenos nombres de variable se crean usando una palabra o juntando dos o tres palabras, separadas por "_" (guión bajo).
Regla 3-3: Nunca uses l (L minúscula) o O (O mayúscula) como nombres de variables o constantes.
Regla 3-4: No uses los nombres de funciones o de constantes de biblioteca existentes.
Regla 3-5: No uses nombres de variables que difieran por uno o dos caracteres. Haz cada nombre obviamente diferente de cada uno de los demás.
Regla 3-6: Usa nombres similares para variables que realizan funciones similares.
Regla 3-7: Cuando crees un nombre de variable de dos palabras donde las palabras puedan ser puestas en cualquier orden, siempre coloca de primero la más importante.
Regla 3-8: Los prefijos y sufijos estándar son _ptr, _p, _file, _fd, y n_.
Regla 3-9: Los nombres cortos tales como x, y, y i son aceptables cuando su significado es claro y cuando un nombre largo no añadiría información o claridad adicional.
Rule 3-10: Use argc para el número de argumentos de la línea de comandos y argv para la lista de argumentos. No uses esos nombres para nada más.
Regla 3-11: Sigue cada declaración de variable con un comentario que la defina.
Regla 3-12: Cuando sea posible, incluye las unidades de medida en la descripción de una variable.
Regla 3-13: Nombra y comenta cada campo de una estructura o unión igual que una variable.
Regla 3-14: Inicia cada definición de estructura o unión con un comentario multilínea describiéndola.
Regla 3-15: Coloca al menos una línea en blanco antes y después de la definición de una estructura o unión.
Regla 3-16: Cuando no puedas poner un comentario descriptivo al final de una declaración de variable, colócalo en una línea separada arriba de ella. Usa líneas en blanco para separar el par declaración/comentario del resto del código.
Regla 3-17: Agrupa variables similares juntas. Cuando sea posible, usa la misma estructura para cada grupo.
Regla 3-18: No uses variables escondidas.
Regla 3-19: Usa los nombres INT16, INT32, UINT16, y UINT32 para aplicaciones portables.
Regla 3-20: Los números de punto flotante deben tener al menos un dígito a ambos lados del punto decimal.
Regla 3-21: El exponente en un número de punto flotante debe ser una e minúscula. Esta es siempre seguida por un signo.
Regla 3-22: Empieza los números hexadecimales con Ox. (x minúscula solamente.)
Regla 3-23: Usa letras mayúsculas de la A a la F cuando construyas constantes hexadecimales.
Regla 3-24: Las constantes largas deberían terminar con una L mayúscula.
Capítulo 4: Formateo de Sentencias
Regla 4-1: Escribe una sentencia por línea.
Regla 4-2: Coloca espacios antes y después de cada operador aritmético, al igual que colocas espacios entre las palabras cuando escribes.
Regla 4-3: Cambia una sentencia larga y compleja por varias sentencias más pequeñas y más simples.
Regla 4-4: En una sentencia que consiste de dos o más líneas, cada línea excepto la primera debe indentarse un nivel extra para indicar que es una continuación de la primera.
Regla 4-5: Cuando escribas sentencias multilíneas, coloca los operadores aritméticos y lógicos al final de cada línea.
Regla 4-6: Cuando dividas una línea, el punto preferido de división es donde el anidamiento de los paréntesis sea menor.
Regla 4-7: Alinea verticalmente los niveles de paréntesis.
Regla 4-8: Divide las sentencias for largas en los límites de sus sentencias.
Regla 4-9: Siempre divide una sentencia for en tres líneas.
Regla 4-10: Escribe las sentencias switch en una línea independiente.
Regla 4-11: Mantén los condicionales en una única línea si es posible.
Regla 4-12: Cuando dividas una cláusula condicional (?:), escríbela en tres líneas: la línea de la condición, la línea del valor verdadero, y la línea del valor falso. Indenta la segunda y la tercera línea un nivel extra.
Regla 4-13: Evita los efectos colaterales.
Regla 4-14: Coloca los operadores ++ y -- en sus propias líneas. No uses ++ y -- dentro de otras sentencias.
Regla 4-15: Nunca coloques una sentencia de asignación dentro de otra sentencia.
Regla 4-16: Si el colocar dos o más sentencias en una misma línea mejora la claridad del programa, entonces hazlo así.
Regla 4-17: Cuando uses más de una sentencia por línea, organiza las sentencias en columnas.
Regla 4-18: Indenta un nivel para cada nuevo nivel de lógica.
Regla 4-19: El mejor tamaño de indentación es de cuatro espacios.
Capítulo 5: Detalles de Sentencias
Regla 5-1: Coloca siempre un comentario en la sentencia nula, aún si es la única.
Regla 5-2: En las expresiones en C, puedes asumir que *, /, y % vienen después de + y -. Coloca paréntesis alrededor de todo lo demás.
Regla 5-3: Usa declaraciones de funciones estilo ANSI siempre que sea posible.
Regla 5-4: Cuando uses parámetros tipo K&R (Kernighan&Ritchie), declara un tipo para cada parámetro.
Regla 5-5: Cuando uses parámetros tipo K&R (Kernighan&Ritchie), coloca la declaración de tipo de los parámetros en el mismo orden en que aparecen en la cabecera de la función.
Regla 5-6: Siempre declara un tipo para la función.
Regla 5-7: Siempre declara funciones que no retornan un valor como void.
Regla 5-8: No permitas más de 5 parámetros para una función.
Regla 5-9: Evita usar variables globales cuando los parámetros de la función pueden bastar.
Regla 5-10: Evita las listas de parámetros de longitud variable. Son difíciles de programar y fácilmente pueden causar problemas.
Regla 5-11: Cuando un if afecta a más de una línea, enciérralas entre llaves.
Regla 5-12: En una cadena de if, trata las palabras else if como una única palabra clave.
Regla 5-13: Nunca uses el operador coma cuando en su lugar puedas usar llaves.
Regla 5-14: Cuando crees ciclos infinitos, usa while (1) en lugar de for(;;).
Regla 5-15: Evita usar do/while. Usa en su lugar while y break.
Regla 5-16: Usa el operador coma dentro de una sentencia for solamente para poner juntas dos sentencias. Nunca lo uses para combinar tres sentencias.
Regla 5-17: Usa un printf por línea de salida.
Regla 5-18: A menos que se garantice la extrema eficiencia, usa printf en lugar de puts y putc.
Regla 5-19: Empieza las etiquetas goto en la primer columna.
Regla 5-20: Termina cada case en un switch con un break o el comentario /* El flujo continúa en el siguiente case */.
Regla 5-21: Siempre coloca un break al final del último case en una sentencia switch.
Regla 5-22: Siempre incluye un caso default en cada switch, aún cuando no contenga más que la sentencia nula.
Capítulo 6: Preprocesador
Regla 6-1: Las constantes #define se declaran como variables. Siempre coloca un comentario que describa a la constante después de cada declaración.
Regla 6-2: Los nombres de constantes son todos en mayúsculas.
Regla 6-3: Si el valor de una constante es algo más que un simple número, enciérralo entre paréntesis.
Regla 6-4: El uso de const se prefiere sobre #define para especificar constantes.
Regla 6-5: Cuando sea posible, usa typedef en lugar de #define.
Regla 6-6: No uses #define para definir nuevos elementos de lenguaje.
Regla 6-7: Nunca uses #define para redefinir palabras claves o funciones estándar de C.
Regla 6-8: Encierra las macros parametrizadas entre paréntesis.
Regla 6-9: Encierra cada argumento para una macro parametrizada entre paréntesis.
Regla 6-10: Siempre encierra las macros que definen múltiple sentencias de C entre llaves.
Regla 6-11: Si una macro contiene más de una sentencia, usa una estructura do/while para encerrar la macro. (No olvides dejar el punto y coma de la sentencia).
Regla 6-12: Cuando crees macros multilíneas, alinea los caracteres de continuación diagonal inversa (\) en una columna.
Regla 6-13: Comenta siempre cualquier macro parametrizada que se vea como una función.
Regla 6-14: Las directivas #include vienen justo después de los comentario de encabezado. Coloca primero las inclusiones del sistema, seguidas de las inclusiones locales.
Regla 6-15: No uses rutas absolutas en las directivas #include. Deja que la opción -I haga el trabajo.
Regla 6-16: Comenta las directivas #else y #endif con el símbolo usado en el #ifdef inicial o la directiva #endif.
Regla 6-17: Usa prudentemente la compilación condicional. No permitas que los condicionales oscurezcan el código.
Regla 6-18: Define (o no definas) el control de compilación de símbolo condicional en el código en lugar de usar la opción -D para el compilador.
Regla 6-19: Coloca las sentencias #define y #undef para control de compilación de símbolos al comienzo del programa.
Regla 6-20: No comentes código no utilizado. Usa la compilación condicional (#ifdef #undef) para deshacerte del código no deseado.
Regla 6-21: Usa #ifdef QQQ para eliminar código temporalmente durante la depuración.
Capítulo 7: Estilo de Organización de Directorio y Makefile
Regla 7-1: Siempre que sea posible, coloca todos los archivos para un programa o biblioteca en un mismo directorio.
Capítulo 8: Programación Amistosa con el Usuario
Regla 8-1: Ley de la Menor Sorpresa: El programa debería actuar de la manera que menos sorprenda al usuario.
Regla 8-2: Empieza cada mensaje de error con el rótulo Error:. Inicia cada mensaje de advertencia con Advertencia:.
* jive [estudio.c]
ent a,b,c.
inicio()
{
imp//”Dame valor A”.
alm%a.
Iip//Dame valor B”.
alm%b.
c=a+b.
imp//c.
}
Reglas claves con las que se cumple:
3-6 se cumple al utilizar nombres de variables que realizan funciones similares
4-1 escribe una sentencia por línea
Reglas claves con las que no se cumple:
1-2 no cumple ya que el .c se encuentra en la parte pública y no en la privada
Por lo tanto para que cumpla el programa con las reglas, solo se tendra que cambiar en las librerías el .c por el .h
Reglas de Programación del libro Elementos de Estilo en C
Capítulo 1: Estilo y Organización de Programas
Regla 1-1: Organiza los programas para legibilidad, al igual que esperarías que un autor organizaría un libro.
Regla 1-2: Divide cada módulo en un parte pública (lo que se requiere para usar el módulo) y una parte privada (lo que se requiere para hacer el trabajo). La parte pública va en un archivo .h mientras que la parte privada va en un archivo .c .
Regla 1-3: Usa espacios en blanco para separar una función en párrafos.
Regla 1-4: Coloca cada sentencia en su propia línea.
Regla 1-5: Evita sentencias muy largas. Usa en su lugar sentencias múltiples más cortas.
Capítulo 2: Fundamentos de Archivos, Comentarios, y Encabezados de Programas
Regla 2-1: Mantén los archivos de programas no mayores a 2,000 ó 3,000 líneas.
Regla 2-2: Mantén todas las líneas de tu programa debajo de 72 caracteres o menos.
Regla 2-3: Usa paradas de tabuladores de 8 caracteres.
Regla 2-4: Usa solamente los 95 caracteres ASCII estándar en tus programas. Evita caracteres exóticos. (Los caracteres extranjeros pueden ser usados si estás escribiendo comentarios en una lengua extranjera.)
Regla 2-5: Incluye un comentario de cabecera al comienzo de cada archivo que explique el archivo.
Regla 2-6: Deja fuera los comentarios innecesarios si ellos requieren mantenimiento y no estás dispuesto a dárselo.
Regla 2-7: Comenta tu código mientras lo escribes.
Capítulo 3: Nombres de Variables
Regla 3-1: Usa nombres de variable simples y descriptivos.
Regla 3-2: Los buenos nombres de variable se crean usando una palabra o juntando dos o tres palabras, separadas por "_" (guión bajo).
Regla 3-3: Nunca uses l (L minúscula) o O (O mayúscula) como nombres de variables o constantes.
Regla 3-4: No uses los nombres de funciones o de constantes de biblioteca existentes.
Regla 3-5: No uses nombres de variables que difieran por uno o dos caracteres. Haz cada nombre obviamente diferente de cada uno de los demás.
Regla 3-6: Usa nombres similares para variables que realizan funciones similares.
Regla 3-7: Cuando crees un nombre de variable de dos palabras donde las palabras puedan ser puestas en cualquier orden, siempre coloca de primero la más importante.
Regla 3-8: Los prefijos y sufijos estándar son _ptr, _p, _file, _fd, y n_.
Regla 3-9: Los nombres cortos tales como x, y, y i son aceptables cuando su significado es claro y cuando un nombre largo no añadiría información o claridad adicional.
Rule 3-10: Use argc para el número de argumentos de la línea de comandos y argv para la lista de argumentos. No uses esos nombres para nada más.
Regla 3-11: Sigue cada declaración de variable con un comentario que la defina.
Regla 3-12: Cuando sea posible, incluye las unidades de medida en la descripción de una variable.
Regla 3-13: Nombra y comenta cada campo de una estructura o unión igual que una variable.
Regla 3-14: Inicia cada definición de estructura o unión con un comentario multilínea describiéndola.
Regla 3-15: Coloca al menos una línea en blanco antes y después de la definición de una estructura o unión.
Regla 3-16: Cuando no puedas poner un comentario descriptivo al final de una declaración de variable, colócalo en una línea separada arriba de ella. Usa líneas en blanco para separar el par declaración/comentario del resto del código.
Regla 3-17: Agrupa variables similares juntas. Cuando sea posible, usa la misma estructura para cada grupo.
Regla 3-18: No uses variables escondidas.
Regla 3-19: Usa los nombres INT16, INT32, UINT16, y UINT32 para aplicaciones portables.
Regla 3-20: Los números de punto flotante deben tener al menos un dígito a ambos lados del punto decimal.
Regla 3-21: El exponente en un número de punto flotante debe ser una e minúscula. Esta es siempre seguida por un signo.
Regla 3-22: Empieza los números hexadecimales con Ox. (x minúscula solamente.)
Regla 3-23: Usa letras mayúsculas de la A a la F cuando construyas constantes hexadecimales.
Regla 3-24: Las constantes largas deberían terminar con una L mayúscula.
Capítulo 4: Formateo de Sentencias
Regla 4-1: Escribe una sentencia por línea.
Regla 4-2: Coloca espacios antes y después de cada operador aritmético, al igual que colocas espacios entre las palabras cuando escribes.
Regla 4-3: Cambia una sentencia larga y compleja por varias sentencias más pequeñas y más simples.
Regla 4-4: En una sentencia que consiste de dos o más líneas, cada línea excepto la primera debe indentarse un nivel extra para indicar que es una continuación de la primera.
Regla 4-5: Cuando escribas sentencias multilíneas, coloca los operadores aritméticos y lógicos al final de cada línea.
Regla 4-6: Cuando dividas una línea, el punto preferido de división es donde el anidamiento de los paréntesis sea menor.
Regla 4-7: Alinea verticalmente los niveles de paréntesis.
Regla 4-8: Divide las sentencias for largas en los límites de sus sentencias.
Regla 4-9: Siempre divide una sentencia for en tres líneas.
Regla 4-10: Escribe las sentencias switch en una línea independiente.
Regla 4-11: Mantén los condicionales en una única línea si es posible.
Regla 4-12: Cuando dividas una cláusula condicional (?:), escríbela en tres líneas: la línea de la condición, la línea del valor verdadero, y la línea del valor falso. Indenta la segunda y la tercera línea un nivel extra.
Regla 4-13: Evita los efectos colaterales.
Regla 4-14: Coloca los operadores ++ y -- en sus propias líneas. No uses ++ y -- dentro de otras sentencias.
Regla 4-15: Nunca coloques una sentencia de asignación dentro de otra sentencia.
Regla 4-16: Si el colocar dos o más sentencias en una misma línea mejora la claridad del programa, entonces hazlo así.
Regla 4-17: Cuando uses más de una sentencia por línea, organiza las sentencias en columnas.
Regla 4-18: Indenta un nivel para cada nuevo nivel de lógica.
Regla 4-19: El mejor tamaño de indentación es de cuatro espacios.
Capítulo 5: Detalles de Sentencias
Regla 5-1: Coloca siempre un comentario en la sentencia nula, aún si es la única.
Regla 5-2: En las expresiones en C, puedes asumir que *, /, y % vienen después de + y -. Coloca paréntesis alrededor de todo lo demás.
Regla 5-3: Usa declaraciones de funciones estilo ANSI siempre que sea posible.
Regla 5-4: Cuando uses parámetros tipo K&R (Kernighan&Ritchie), declara un tipo para cada parámetro.
Regla 5-5: Cuando uses parámetros tipo K&R (Kernighan&Ritchie), coloca la declaración de tipo de los parámetros en el mismo orden en que aparecen en la cabecera de la función.
Regla 5-6: Siempre declara un tipo para la función.
Regla 5-7: Siempre declara funciones que no retornan un valor como void.
Regla 5-8: No permitas más de 5 parámetros para una función.
Regla 5-9: Evita usar variables globales cuando los parámetros de la función pueden bastar.
Regla 5-10: Evita las listas de parámetros de longitud variable. Son difíciles de programar y fácilmente pueden causar problemas.
Regla 5-11: Cuando un if afecta a más de una línea, enciérralas entre llaves.
Regla 5-12: En una cadena de if, trata las palabras else if como una única palabra clave.
Regla 5-13: Nunca uses el operador coma cuando en su lugar puedas usar llaves.
Regla 5-14: Cuando crees ciclos infinitos, usa while (1) en lugar de for(;;).
Regla 5-15: Evita usar do/while. Usa en su lugar while y break.
Regla 5-16: Usa el operador coma dentro de una sentencia for solamente para poner juntas dos sentencias. Nunca lo uses para combinar tres sentencias.
Regla 5-17: Usa un printf por línea de salida.
Regla 5-18: A menos que se garantice la extrema eficiencia, usa printf en lugar de puts y putc.
Regla 5-19: Empieza las etiquetas goto en la primer columna.
Regla 5-20: Termina cada case en un switch con un break o el comentario /* El flujo continúa en el siguiente case */.
Regla 5-21: Siempre coloca un break al final del último case en una sentencia switch.
Regla 5-22: Siempre incluye un caso default en cada switch, aún cuando no contenga más que la sentencia nula.
Capítulo 6: Preprocesador
Regla 6-1: Las constantes #define se declaran como variables. Siempre coloca un comentario que describa a la constante después de cada declaración.
Regla 6-2: Los nombres de constantes son todos en mayúsculas.
Regla 6-3: Si el valor de una constante es algo más que un simple número, enciérralo entre paréntesis.
Regla 6-4: El uso de const se prefiere sobre #define para especificar constantes.
Regla 6-5: Cuando sea posible, usa typedef en lugar de #define.
Regla 6-6: No uses #define para definir nuevos elementos de lenguaje.
Regla 6-7: Nunca uses #define para redefinir palabras claves o funciones estándar de C.
Regla 6-8: Encierra las macros parametrizadas entre paréntesis.
Regla 6-9: Encierra cada argumento para una macro parametrizada entre paréntesis.
Regla 6-10: Siempre encierra las macros que definen múltiple sentencias de C entre llaves.
Regla 6-11: Si una macro contiene más de una sentencia, usa una estructura do/while para encerrar la macro. (No olvides dejar el punto y coma de la sentencia).
Regla 6-12: Cuando crees macros multilíneas, alinea los caracteres de continuación diagonal inversa (\) en una columna.
Regla 6-13: Comenta siempre cualquier macro parametrizada que se vea como una función.
Regla 6-14: Las directivas #include vienen justo después de los comentario de encabezado. Coloca primero las inclusiones del sistema, seguidas de las inclusiones locales.
Regla 6-15: No uses rutas absolutas en las directivas #include. Deja que la opción -I haga el trabajo.
Regla 6-16: Comenta las directivas #else y #endif con el símbolo usado en el #ifdef inicial o la directiva #endif.
Regla 6-17: Usa prudentemente la compilación condicional. No permitas que los condicionales oscurezcan el código.
Regla 6-18: Define (o no definas) el control de compilación de símbolo condicional en el código en lugar de usar la opción -D para el compilador.
Regla 6-19: Coloca las sentencias #define y #undef para control de compilación de símbolos al comienzo del programa.
Regla 6-20: No comentes código no utilizado. Usa la compilación condicional (#ifdef #undef) para deshacerte del código no deseado.
Regla 6-21: Usa #ifdef QQQ para eliminar código temporalmente durante la depuración.
Capítulo 7: Estilo de Organización de Directorio y Makefile
Regla 7-1: Siempre que sea posible, coloca todos los archivos para un programa o biblioteca en un mismo directorio.
Capítulo 8: Programación Amistosa con el Usuario
Regla 8-1: Ley de la Menor Sorpresa: El programa debería actuar de la manera que menos sorprenda al usuario.
Regla 8-2: Empieza cada mensaje de error con el rótulo Error:. Inicia cada mensaje de advertencia con Advertencia:.
viernes, 28 de mayo de 2010
Automatas Finitos
2.- Automatas Finitos
En este capítulo estudiaremos un tipo de máquinas abstractas
de computación en donde la entrada consiste de una cadena de un
determinado alfabeto, y la salida o resultado de la computación
es la aceptación o no de la cadena de entrada. El conjunto de
cadenas aceptadas por la máquina es el lenguaje reconocido por
la máquina. De esta forma, asociamos lenguajes y máquinas, los
dos tópicos principales de esta materia.
2.1 Autómatas Finítos Determinísticos (AFD)
Un AFD es un quintuple M = (Q, ∑, δ, q0, F), donde Q es una máquina de estados finita, ∑ es el alfabeto, q0 es el estado inicial, F es el estado(s) final(es) y δ es una función de Q x ∑ a Q llamada la función de transición.
Ejemplo: El siguiente AFD acepta el conjunto de cadenas que contienen la subcadena bb y donde ∑={a,b}. Esto quiere decir que L(M) = (a|b)*bb(a|b)* .
M: Q = {q0, q1, q2 }
∑ = {a, b}
F = {q2}
La función de transición d es dada en forma tabular y llamada tabla de transición.
Para las cadenas abba y abab tenemos las siguientes
operaciones (computaciones) en la tabla:
[q0, abba] [q0, abab]
-[q0, bba] -[q0, bab]
-[q1, ba] -[q1, ab]
-[q2, a] -[q0, b]
-[q2, λ] -[q1, λ]
acepta rechazado
La cadena abba es aceptada ya que la computación se
para (halts) en estado q2.
Una cadena de entrada es aceptada si existe una computación que procesa toda la cadena de entrada y para en un estado final o aceptador.
Diagramas de Estado
El diagrama de estado de un AFD es un grafo dirigido-etiquetado
en el cual los nodos representan los estados de la máquina y los
arcos son obtenidos de la función de transición.
Otra definición es la siguiente:
2.2 Autómatas Finitos No determinísticos (AFN)
La diferencia es el no determinismo de esta clase de autómatas. Esto se manifiesta en la función de transición que en los AFD significa moverse de un estado a otro bajo un símbolo de entrada. En un AFN la función de transición también contempla lo anterior, pero además contempla otras dos transiciones: moverse de un estado a varios estados bajo una sola entrada o símbolo; y moverse de un estado a otro bajo no entrada o símbolo. Estas tres transiciones se dan como
La relación entre AFD y AFN se sumariza con la siguiente frase: “Cada AFD es AFN”. La función de transición de un AFD especifica exactamente que con una entrada solo se puede ir a un estado. Mientras en un AFN con una entrada se puede ir a cero, uno o mas estados. Esto quiere decir que la familia de AFDs es un subconjunto de los AFN.
Una cadena de entrada para un AFN puede generar distintas computaciones. En unos casos el automata para (halt) sin aceptar la cadena, en otros la rechaza o las acepta.
Ejemplo: El AFN M para la cadena ababb con tres diferentes computaciones.
M: Q = {q0, q1, q2 }
∑ = {a, b}
F = {q2}
La primera computación procesa toda la entrada y para en un estado de rechazar. La segunda computación, para (halt) después de ejecutar tres instrucciones ya que no existe acción cuando la máquina esta en estado q1 y leyendo una a. Por último, la tercera computación acepta la entrada.
Una cadena de entrada es aceptada si existe una computación que procesa toda la cadena de entrada y para en un estado final o aceptador. Una cadena de entrada está en el lenguaje de un AFN si existe una computación que lo acepte. El lenguaje de un AFN M, denotado L(M), es el conjunto de cadenas aceptadas por M.
El diagrama de estados para el AFN del ejemplo anterior es el siguiente:
El diagrama aceptado por este último AFN es (a | b)*bb
Es AFN porqué existen dos transiciones de q0 a q0 y de q0 a q1 ante una misma entrada: b
El siguiente diagrama de estados para un AFN acepta el lenguaje expresado por (ab)* | a*
Es AFN porqué existen dos transiciones de q0 a q1 y de q0 a q3 ante una misma entrada: a
Transiciones Lambda
Las transiciones de estado a estado en AFD y AFN se llevan a cabo al procesar o leer un símbolo de entrada. Podemos también redefinir a un AFN de tal manera que admita transiciones de estado a estado sin leer un símbolo de entrada.
Una transición de esta forma es llamada transición lambda.
A este tipo de máquinas se les llama AFN- λ.
Por medio de movimientos lambda se puede construir máquinas complejas a partir de máquinas mas simples.
La definición de halting (cuando parar) se extiende para incluir la posibilidad que una computación puede continuar usando transiciones lambda después de que toda la cadena de entrada ha sido leída. También se pide, al igual que en los anteriores autómatas, que termine en un estado final, esto para finalizar el AFN-λ con éxito.
Ejemplo: Sea M1 y M2 las siguientes máquinas que aceptan los lenguajes descritos por (a | b)*bb (a | b)*
y (b | ab)* (a | l).
Podemos construír máquinas compuestas combinando los doagramas de estado M1 y M2.
El lenguaje del AFN-λ M es L(M1) U L(M2)
Una computación en la máquina M comienza siguiendo un arco lambda a un estado inicial de M1 o M2.
Ejemplo: Un AFN-λ M que acepta L(M1) L(M2), la concatenación de dos lenguajes se construye juntando las dos máquinas con un arco lambda.
Una cadena de entrada es aceptada solo si consiste de una cadena de L(M1) seguido de una cadena de L(M2)
2.3 Equivalencia de AFN y AFD
Tres clases de autómatas finitos se han estudiado. En esta sección demostraremos que los tres tipos de autómatas aceptan el mismo tipo de lenguajes; mejor dicho, el lenguaje aceptado por un AFN- l es aceptado por un equivalente AFN y también por un equivalente AFD. Demostraremos como a un AFN- l y aun AFN le podemos quitar su no determinismo mediante la construcción de un AFD equivalente.
En la figura anterior las transiciones de el estado q1 ante entrada α son el conjunto {q2, q3, q5, q6}. Esto debido a que podemos alcanzar o llegar a esos estados desde el estado q1 y solo leyendo α. Al estado q4 llegamos leyendo solo λ.
La función de transición t de un NFA- λ es una función un poco diferente a la función de transición δ de un AFD o un AFN. En la función t, las transiciones ante λ son válidas para moverse de un estado a otro y juntándola con una entrada del alfabeto.
Ejemplo: Las tablas de transición siguientes ejemplifican las funciones de transición δ y t para el siguiente AFN- λ(diagrama de estado M). El lenguaje de M es a+c*b*.
La función de transición t es usada para construir un autómata finito deterministico equivalente. El procedimiento usa el diagrama de estados de el AFN- λ para construir el diagrama de estados de el equivalente AFD.
Ejemplo: Construir un AFD equivalente para el siguiente AFN- λ.
Su correspondiente diagrama de estados:
Se crean tres nuevos estados a los cuales se les aplica el mismo procedimiento para obtener hacia que estados se moverá. Este procedimiento termina hasta que no hay no se genere un nuevo estado.
A partir del diagrama de estados se puede construir el AFD equivalente.
El AFN M acepta el lenguaje a+ b+. Procedemos a convertirlo a un equivalente AFD.
2.4 Propiedades de los Lenguajes aceptados por un Autómata Finito.
Cada autómata finito con alfabeto ∑ acepta un lenguaje para ∑. Podemos probar que la familia de lenguajes aceptados por un autómata finito consiste precisamente de los conjuntos o lenguajes regulares para ∑.
Primero demostramos que cada conjunto o lenguaje regular es aceptado por algún AFN- λ. La demostración va de acuerdo a una definición recursiva. Los lenguajes o conjuntos regulares se construyen a partir de los elementos básicos 0 (conjunto o estado vacío), λ (cadena vacía) y conjuntos individuales que contienen elementos del alfabeto.
Los diagramas de estado para las máquinas que aceptan dichos conjuntos son:
Conjuntos regulares se construyen de los elementos básicos usando unión, concatenación y operación Kleene Star. Al igual que los conjuntos regulares, autómatas finitos mas complejos se pueden construir a partir de los diagramas anteriores y que acepten la unión, concatenación y operación Kleene Star de lenguajes regulares.
Ejemplo: El lenguaje L(M1) U L(M2) es aceptado por la máquina siguiente:
La concatenación de dos lenguajes L(M1) L(M2) regulares puede ser aceptado por la máquina siguiente:
Una máquina que acepta L(M1)* es la siguiente:
CONCLUSION
Usando los autómatas finitos anteriores podemos construir una máquina para cualquier expresión regular que describa a un lenguaje o conjunto regular. Por lo tanto, la conclusión es de que la familia de lenguajes aceptados por una máquina o autómata finito son del tipo regular.
2.5 Autómatas Finitos y Expresiones Regulares.
Los lenguajes regulares son definidos por medio de expresiones regulares y aceptados por medio de autómatas finitos. Podemos establecer que un lenguaje es regular si
- Es una expresión regular bajo un ∑.
- Es aceptado por un AFD, AFN o AFN- λ.
- Es generado por una gramática regular.
En cuanto a las expresiones regulares y autómatas, hemos ya comprobado en la sección anterior que podemos construir un autómata finito para cualquier expresión regular dada. Por otra parte existen métodos para producir una expresión regular a partir de un autómata finito.
2.6 Determinación de lenguajes regulares y no regulares.
Dado el lenguaje {aibi | i<=n} ¿podemos construir un AFD que acepte dicho lenguaje?
El siguiente AFD acepta dicho lenguaje pero está incompleto.
El AFD anterior está incompleto puesto que es imposible construir un AFD para un lenguaje que no es regular. De hecho dicho lenguaje es del tipo contexto libre, o es un lenguaje no regular.
Se puede demostrar que un lenguaje es regular al construir un autómata finito que lo acepte. Pero para demostrar que no es regular necesitamos usar otras técnicas.
En este capítulo estudiaremos un tipo de máquinas abstractas
de computación en donde la entrada consiste de una cadena de un
determinado alfabeto, y la salida o resultado de la computación
es la aceptación o no de la cadena de entrada. El conjunto de
cadenas aceptadas por la máquina es el lenguaje reconocido por
la máquina. De esta forma, asociamos lenguajes y máquinas, los
dos tópicos principales de esta materia.
2.1 Autómatas Finítos Determinísticos (AFD)
Un AFD es un quintuple M = (Q, ∑, δ, q0, F), donde Q es una máquina de estados finita, ∑ es el alfabeto, q0 es el estado inicial, F es el estado(s) final(es) y δ es una función de Q x ∑ a Q llamada la función de transición.
Ejemplo: El siguiente AFD acepta el conjunto de cadenas que contienen la subcadena bb y donde ∑={a,b}. Esto quiere decir que L(M) = (a|b)*bb(a|b)* .
M: Q = {q0, q1, q2 }
∑ = {a, b}
F = {q2}
La función de transición d es dada en forma tabular y llamada tabla de transición.
Para las cadenas abba y abab tenemos las siguientes
operaciones (computaciones) en la tabla:
[q0, abba] [q0, abab]
-[q0, bba] -[q0, bab]
-[q1, ba] -[q1, ab]
-[q2, a] -[q0, b]
-[q2, λ] -[q1, λ]
acepta rechazado
La cadena abba es aceptada ya que la computación se
para (halts) en estado q2.
Una cadena de entrada es aceptada si existe una computación que procesa toda la cadena de entrada y para en un estado final o aceptador.
Diagramas de Estado
El diagrama de estado de un AFD es un grafo dirigido-etiquetado
en el cual los nodos representan los estados de la máquina y los
arcos son obtenidos de la función de transición.
Otra definición es la siguiente:
2.2 Autómatas Finitos No determinísticos (AFN)
La diferencia es el no determinismo de esta clase de autómatas. Esto se manifiesta en la función de transición que en los AFD significa moverse de un estado a otro bajo un símbolo de entrada. En un AFN la función de transición también contempla lo anterior, pero además contempla otras dos transiciones: moverse de un estado a varios estados bajo una sola entrada o símbolo; y moverse de un estado a otro bajo no entrada o símbolo. Estas tres transiciones se dan como
La relación entre AFD y AFN se sumariza con la siguiente frase: “Cada AFD es AFN”. La función de transición de un AFD especifica exactamente que con una entrada solo se puede ir a un estado. Mientras en un AFN con una entrada se puede ir a cero, uno o mas estados. Esto quiere decir que la familia de AFDs es un subconjunto de los AFN.
Una cadena de entrada para un AFN puede generar distintas computaciones. En unos casos el automata para (halt) sin aceptar la cadena, en otros la rechaza o las acepta.
Ejemplo: El AFN M para la cadena ababb con tres diferentes computaciones.
M: Q = {q0, q1, q2 }
∑ = {a, b}
F = {q2}
La primera computación procesa toda la entrada y para en un estado de rechazar. La segunda computación, para (halt) después de ejecutar tres instrucciones ya que no existe acción cuando la máquina esta en estado q1 y leyendo una a. Por último, la tercera computación acepta la entrada.
Una cadena de entrada es aceptada si existe una computación que procesa toda la cadena de entrada y para en un estado final o aceptador. Una cadena de entrada está en el lenguaje de un AFN si existe una computación que lo acepte. El lenguaje de un AFN M, denotado L(M), es el conjunto de cadenas aceptadas por M.
El diagrama de estados para el AFN del ejemplo anterior es el siguiente:
El diagrama aceptado por este último AFN es (a | b)*bb
Es AFN porqué existen dos transiciones de q0 a q0 y de q0 a q1 ante una misma entrada: b
El siguiente diagrama de estados para un AFN acepta el lenguaje expresado por (ab)* | a*
Es AFN porqué existen dos transiciones de q0 a q1 y de q0 a q3 ante una misma entrada: a
Transiciones Lambda
Las transiciones de estado a estado en AFD y AFN se llevan a cabo al procesar o leer un símbolo de entrada. Podemos también redefinir a un AFN de tal manera que admita transiciones de estado a estado sin leer un símbolo de entrada.
Una transición de esta forma es llamada transición lambda.
A este tipo de máquinas se les llama AFN- λ.
Por medio de movimientos lambda se puede construir máquinas complejas a partir de máquinas mas simples.
La definición de halting (cuando parar) se extiende para incluir la posibilidad que una computación puede continuar usando transiciones lambda después de que toda la cadena de entrada ha sido leída. También se pide, al igual que en los anteriores autómatas, que termine en un estado final, esto para finalizar el AFN-λ con éxito.
Ejemplo: Sea M1 y M2 las siguientes máquinas que aceptan los lenguajes descritos por (a | b)*bb (a | b)*
y (b | ab)* (a | l).
Podemos construír máquinas compuestas combinando los doagramas de estado M1 y M2.
El lenguaje del AFN-λ M es L(M1) U L(M2)
Una computación en la máquina M comienza siguiendo un arco lambda a un estado inicial de M1 o M2.
Ejemplo: Un AFN-λ M que acepta L(M1) L(M2), la concatenación de dos lenguajes se construye juntando las dos máquinas con un arco lambda.
Una cadena de entrada es aceptada solo si consiste de una cadena de L(M1) seguido de una cadena de L(M2)
2.3 Equivalencia de AFN y AFD
Tres clases de autómatas finitos se han estudiado. En esta sección demostraremos que los tres tipos de autómatas aceptan el mismo tipo de lenguajes; mejor dicho, el lenguaje aceptado por un AFN- l es aceptado por un equivalente AFN y también por un equivalente AFD. Demostraremos como a un AFN- l y aun AFN le podemos quitar su no determinismo mediante la construcción de un AFD equivalente.
En la figura anterior las transiciones de el estado q1 ante entrada α son el conjunto {q2, q3, q5, q6}. Esto debido a que podemos alcanzar o llegar a esos estados desde el estado q1 y solo leyendo α. Al estado q4 llegamos leyendo solo λ.
La función de transición t de un NFA- λ es una función un poco diferente a la función de transición δ de un AFD o un AFN. En la función t, las transiciones ante λ son válidas para moverse de un estado a otro y juntándola con una entrada del alfabeto.
Ejemplo: Las tablas de transición siguientes ejemplifican las funciones de transición δ y t para el siguiente AFN- λ(diagrama de estado M). El lenguaje de M es a+c*b*.
La función de transición t es usada para construir un autómata finito deterministico equivalente. El procedimiento usa el diagrama de estados de el AFN- λ para construir el diagrama de estados de el equivalente AFD.
Ejemplo: Construir un AFD equivalente para el siguiente AFN- λ.
Su correspondiente diagrama de estados:
Se crean tres nuevos estados a los cuales se les aplica el mismo procedimiento para obtener hacia que estados se moverá. Este procedimiento termina hasta que no hay no se genere un nuevo estado.
A partir del diagrama de estados se puede construir el AFD equivalente.
El AFN M acepta el lenguaje a+ b+. Procedemos a convertirlo a un equivalente AFD.
2.4 Propiedades de los Lenguajes aceptados por un Autómata Finito.
Cada autómata finito con alfabeto ∑ acepta un lenguaje para ∑. Podemos probar que la familia de lenguajes aceptados por un autómata finito consiste precisamente de los conjuntos o lenguajes regulares para ∑.
Primero demostramos que cada conjunto o lenguaje regular es aceptado por algún AFN- λ. La demostración va de acuerdo a una definición recursiva. Los lenguajes o conjuntos regulares se construyen a partir de los elementos básicos 0 (conjunto o estado vacío), λ (cadena vacía) y conjuntos individuales que contienen elementos del alfabeto.
Los diagramas de estado para las máquinas que aceptan dichos conjuntos son:
Conjuntos regulares se construyen de los elementos básicos usando unión, concatenación y operación Kleene Star. Al igual que los conjuntos regulares, autómatas finitos mas complejos se pueden construir a partir de los diagramas anteriores y que acepten la unión, concatenación y operación Kleene Star de lenguajes regulares.
Ejemplo: El lenguaje L(M1) U L(M2) es aceptado por la máquina siguiente:
La concatenación de dos lenguajes L(M1) L(M2) regulares puede ser aceptado por la máquina siguiente:
Una máquina que acepta L(M1)* es la siguiente:
CONCLUSION
Usando los autómatas finitos anteriores podemos construir una máquina para cualquier expresión regular que describa a un lenguaje o conjunto regular. Por lo tanto, la conclusión es de que la familia de lenguajes aceptados por una máquina o autómata finito son del tipo regular.
2.5 Autómatas Finitos y Expresiones Regulares.
Los lenguajes regulares son definidos por medio de expresiones regulares y aceptados por medio de autómatas finitos. Podemos establecer que un lenguaje es regular si
- Es una expresión regular bajo un ∑.
- Es aceptado por un AFD, AFN o AFN- λ.
- Es generado por una gramática regular.
En cuanto a las expresiones regulares y autómatas, hemos ya comprobado en la sección anterior que podemos construir un autómata finito para cualquier expresión regular dada. Por otra parte existen métodos para producir una expresión regular a partir de un autómata finito.
2.6 Determinación de lenguajes regulares y no regulares.
Dado el lenguaje {aibi | i<=n} ¿podemos construir un AFD que acepte dicho lenguaje?
El siguiente AFD acepta dicho lenguaje pero está incompleto.
El AFD anterior está incompleto puesto que es imposible construir un AFD para un lenguaje que no es regular. De hecho dicho lenguaje es del tipo contexto libre, o es un lenguaje no regular.
Se puede demostrar que un lenguaje es regular al construir un autómata finito que lo acepte. Pero para demostrar que no es regular necesitamos usar otras técnicas.
Gramaticas
1.- GRAMATICAS
1.1 Introducción a las Gramáticas
Una gramática es una herramienta o notación que nos
permite definir un lenguaje por medio de una serie de reglas
que nos dicen como construír cadenas v´alidas (oraciones)
para el lenguaje.
Chomski formalizó el concepto de una gramatica, al hacer
observaciones importantes en la complejidad de una
gramática que a su vez establece la complejidad de el lenguaje
Como se estableció antes, un lenguaje es un conjunto finíto
de cadenas desde un alfabeto. Una gramática es una forma de
describir al lenguaje.
1.2 Estructuras de las gramáticas
Una gramática G consiste de:
Un alfabeto de símbolos terminales ∑
Un conjunto finíto de variables (símbolos no-terminales) V
Un conjunto de reglas de substitución o producciones P
Un símbolo inicial ∑
G = (∑, V, P, S)
Una regla de substitución o producción está formada por
una parte izquierda α y una parte derecha β: α → β
Su significado es reemplazar α con β.
La parte izquierda son cadenas desde V U ∑, que contienen al
menos una variable desde V: α es un miembro de
(V U ∑)* V (V U ∑)*
Mientras que el lado derecho son cadenas desde V U ∑: β es
un miembro de
(V U ∑)*
La gramática produce cadenas de ∑* al aplicar las producciones e
iniciando con el símbolo inicial hasta que no existan variables.
Cada vez que una producción o regla es aplicada, una forma de
sentencia (cadenas de variables de V y terminales de ∑) es
producida.
El lenguaje generado por la gramática, L(G), es el conjunto de
cadenas que pueden generarse aplicando las reglas anteriormente
descritas.
Ejemplo: Consideremos la siguiente gramática
G = (∑, V, P, S)
V= {S, A}
∑= {a, m, o, t}
P={(1) S → toAto, (2) A → ma, (3) A → maA }
Que genera el lenguaje
L(G)= {tomato, tomamato, tomamamato,...}
Usando las siguientes reglas para la cadena tomamato
S→(1) toAto→(3) tomaAto→(2)tomamato
1.3 Clasificación de las Gramáticas
N. Chomsky en 1959 en su famoso artículo “On certain formal
properties of grammars” definió cuatro familias de gramáticas
(y lenguajes) que forman lo que se llama la jerarquía de
Chomsky. Estas son: gramáticas sin restricciones, de contexto
sensitivo, de contexto libre y regulares (tipo 0, 1, 2 y 3).
La restricciones puestas en cada regla aumentan con el número
de la gramática.
Gramáticas sin Restricciones.
Son el tipo de gramática mas generales. Una producción u→v
indica que una ocurrencia de una subcadena u en una cadena
puede ser reemplazada con la cadena v. La única restricción
en una producción es que el lado izquierdo no sea cadena nula.
Una definición formal de una gramática sin restricciones es
la siguiente:
Un cuadruplo (V, ∑, P, S) donde V es un conjunto finito de
variables, ∑ (el alfabeto) es un conjunto de símbolos terminales
(del alfabeto), P es un conjunto de producciones y S es el
símbolo inicial de V. Una producción de esta clase de gramática
tiene la forma u→v, donde u es miembro de (V U ∑)+ y v es
miembro de (V U ∑)* .
Ejemplo: La gramática sin restricciones
V= {S, A, C}
∑= {a,b,c}
S → aAbc | λ
A → aAbC | λ
Cb → bC
Cc → cc
Con símbolo inicial S genera el lenguaje {ai bi ci | i>=0}.
Gramáticas de Contexto Sensitivo
Estas gramáticas representan un paso intermedio entre las
gramáticas de contexto libre y las gramáticas sin restricciones.
Para estas gramáticas no existe restricción alguna en la parte
izquierda de la producción, pero la longitud de la parte derecha
debe ser al menos la longitud de la parte izquierda.
Una definición formal de una gramática de contexto sensitivo es
la siguiente:
Un cuadruplo G= (V, ∑, P, S) donde cada producción tiene la
forma u → v, donde u es un miembro de (V U ∑)+ , v es miembro
de (V U ∑)+ y longitud(u) >= longitud (v). Un lenguaje generado
por una gramática de contexto sensitivo es llamado lenguaje
de contexto sensitivo (en gramáticas sin restricciones el lenguaje
también es llamado sin restricciones).
Si eliminamos las producciones de cadena vacía de la anterior
gramática sin restricciones, tenemos una gramática de contexto
sensitivo.
S → aAbc | abc
A → aAbC | abC
que produce un lenguaje similar al ejemplo anterior.
Gramáticas de Contexto Libre
La flexibilidad proporcionada por las gramáticas de contexto
libre es tal que es la mas usada para definir la sintaxis de los
lenguajes de programación.
Una definición formal de una gramática de contexto sensitivo es
la siguiente:
Es un cuadruplo G= (V, ∑, P, S) donde V es un conjunto finito
de variables, ∑ es un conjunto finito de símbolos terminales,
P es un conjunto finito de reglas y S es el símbolo inicial.
Cada producción tiene la forma u→v, donde u es una variable
del conjunto V, y v es un miembro de (V U ∑)* . Esto quiere decir
En la parte izquierda dela producción viene siempre una variable
(símbolo no terminal) y en la parte derecha pueden venir
cualquier número de símbolos terminales y no terminales
incluyendo la cadena nula.
Una gramática de contexto libre produce un lenguaje también de
contexto libre: G → L(G).
Ejemplo: La siguiente gramática genera el lenguaje que consiste
de cadenas con un número par positivo de a’s.
G= (V, ∑ , P, S)
V={S,A}
∑={a,b}
P: S → AA
A → AAA | bA | Ab | a
Una derivación por la izquierda es la siguiente:
S→AA→bAA→baA→baa
Una derivación por la derecha
S→AA→AbA→Aba→aba
Gramáticas Regulares
Estas gramáticas constituyen una importante subclase de
las gramáticas de contexto libre. Son también útiles en la
definición de lenguajes de programación.
Una gramática es regular (GR) si cada regla o producción
cumple con las siguientes formas:
1.- A → a
2.- A → aB
3.- A → λ
Donde A, B son miembros de V y a es miembro de ∑ .
Una GR G genera un lenguaje regular L(G).
Ejemplo
La siguiente es una GCL ( λ U (ab)+a*)
G: S → abSA | λ
A → Aa | λ
una correspondiente gramática regular sería:
S → aB | λ
B → bS | bA
A → aA | λ
1.4 Representación de Gramáticas
En las secciones anteriores, se usaron pequeñas gramáticas
para generar lenguajes también pequeños. Esos ejemplos
sirvieron para ilustrar el uso de gramáticas para definir lenguajes.
Por otra parte, en el diseño de lenguajes de programación se
maneja sintaxis y alfabetos mas complejas y mas grandes. Esto
Por supuesto, incrementa la complejidad de las reglas para
generar el lenguaje.
Notación de BNF.
John Backus y Peter Naur inventaron un sistema de reglas para
definir el lenguaje de programación ALGOL 60. Este sistema
recibió el nombre de Backus-Naur Form o BNF. La sintaxis del
Pascal también fue definido con este sistema o técnica, y hoy en
día se usa para definir la gran mayoría de los lenguajes de
programación
Una especificación BNF es un conjunto de reglas de producción,
escritas como:
::=
Diagramas Sintácticos
Es también un tipo de notación para especificar la sintaxis de
Un lenguaje. La diferencia con la notación BNF es que en esta
se usan líneas y figuras en lugar de nombres.
1.1 Introducción a las Gramáticas
Una gramática es una herramienta o notación que nos
permite definir un lenguaje por medio de una serie de reglas
que nos dicen como construír cadenas v´alidas (oraciones)
para el lenguaje.
Chomski formalizó el concepto de una gramatica, al hacer
observaciones importantes en la complejidad de una
gramática que a su vez establece la complejidad de el lenguaje
Como se estableció antes, un lenguaje es un conjunto finíto
de cadenas desde un alfabeto. Una gramática es una forma de
describir al lenguaje.
1.2 Estructuras de las gramáticas
Una gramática G consiste de:
Un alfabeto de símbolos terminales ∑
Un conjunto finíto de variables (símbolos no-terminales) V
Un conjunto de reglas de substitución o producciones P
Un símbolo inicial ∑
G = (∑, V, P, S)
Una regla de substitución o producción está formada por
una parte izquierda α y una parte derecha β: α → β
Su significado es reemplazar α con β.
La parte izquierda son cadenas desde V U ∑, que contienen al
menos una variable desde V: α es un miembro de
(V U ∑)* V (V U ∑)*
Mientras que el lado derecho son cadenas desde V U ∑: β es
un miembro de
(V U ∑)*
La gramática produce cadenas de ∑* al aplicar las producciones e
iniciando con el símbolo inicial hasta que no existan variables.
Cada vez que una producción o regla es aplicada, una forma de
sentencia (cadenas de variables de V y terminales de ∑) es
producida.
El lenguaje generado por la gramática, L(G), es el conjunto de
cadenas que pueden generarse aplicando las reglas anteriormente
descritas.
Ejemplo: Consideremos la siguiente gramática
G = (∑, V, P, S)
V= {S, A}
∑= {a, m, o, t}
P={(1) S → toAto, (2) A → ma, (3) A → maA }
Que genera el lenguaje
L(G)= {tomato, tomamato, tomamamato,...}
Usando las siguientes reglas para la cadena tomamato
S→(1) toAto→(3) tomaAto→(2)tomamato
1.3 Clasificación de las Gramáticas
N. Chomsky en 1959 en su famoso artículo “On certain formal
properties of grammars” definió cuatro familias de gramáticas
(y lenguajes) que forman lo que se llama la jerarquía de
Chomsky. Estas son: gramáticas sin restricciones, de contexto
sensitivo, de contexto libre y regulares (tipo 0, 1, 2 y 3).
La restricciones puestas en cada regla aumentan con el número
de la gramática.
Gramáticas sin Restricciones.
Son el tipo de gramática mas generales. Una producción u→v
indica que una ocurrencia de una subcadena u en una cadena
puede ser reemplazada con la cadena v. La única restricción
en una producción es que el lado izquierdo no sea cadena nula.
Una definición formal de una gramática sin restricciones es
la siguiente:
Un cuadruplo (V, ∑, P, S) donde V es un conjunto finito de
variables, ∑ (el alfabeto) es un conjunto de símbolos terminales
(del alfabeto), P es un conjunto de producciones y S es el
símbolo inicial de V. Una producción de esta clase de gramática
tiene la forma u→v, donde u es miembro de (V U ∑)+ y v es
miembro de (V U ∑)* .
Ejemplo: La gramática sin restricciones
V= {S, A, C}
∑= {a,b,c}
S → aAbc | λ
A → aAbC | λ
Cb → bC
Cc → cc
Con símbolo inicial S genera el lenguaje {ai bi ci | i>=0}.
Gramáticas de Contexto Sensitivo
Estas gramáticas representan un paso intermedio entre las
gramáticas de contexto libre y las gramáticas sin restricciones.
Para estas gramáticas no existe restricción alguna en la parte
izquierda de la producción, pero la longitud de la parte derecha
debe ser al menos la longitud de la parte izquierda.
Una definición formal de una gramática de contexto sensitivo es
la siguiente:
Un cuadruplo G= (V, ∑, P, S) donde cada producción tiene la
forma u → v, donde u es un miembro de (V U ∑)+ , v es miembro
de (V U ∑)+ y longitud(u) >= longitud (v). Un lenguaje generado
por una gramática de contexto sensitivo es llamado lenguaje
de contexto sensitivo (en gramáticas sin restricciones el lenguaje
también es llamado sin restricciones).
Si eliminamos las producciones de cadena vacía de la anterior
gramática sin restricciones, tenemos una gramática de contexto
sensitivo.
S → aAbc | abc
A → aAbC | abC
que produce un lenguaje similar al ejemplo anterior.
Gramáticas de Contexto Libre
La flexibilidad proporcionada por las gramáticas de contexto
libre es tal que es la mas usada para definir la sintaxis de los
lenguajes de programación.
Una definición formal de una gramática de contexto sensitivo es
la siguiente:
Es un cuadruplo G= (V, ∑, P, S) donde V es un conjunto finito
de variables, ∑ es un conjunto finito de símbolos terminales,
P es un conjunto finito de reglas y S es el símbolo inicial.
Cada producción tiene la forma u→v, donde u es una variable
del conjunto V, y v es un miembro de (V U ∑)* . Esto quiere decir
En la parte izquierda dela producción viene siempre una variable
(símbolo no terminal) y en la parte derecha pueden venir
cualquier número de símbolos terminales y no terminales
incluyendo la cadena nula.
Una gramática de contexto libre produce un lenguaje también de
contexto libre: G → L(G).
Ejemplo: La siguiente gramática genera el lenguaje que consiste
de cadenas con un número par positivo de a’s.
G= (V, ∑ , P, S)
V={S,A}
∑={a,b}
P: S → AA
A → AAA | bA | Ab | a
Una derivación por la izquierda es la siguiente:
S→AA→bAA→baA→baa
Una derivación por la derecha
S→AA→AbA→Aba→aba
Gramáticas Regulares
Estas gramáticas constituyen una importante subclase de
las gramáticas de contexto libre. Son también útiles en la
definición de lenguajes de programación.
Una gramática es regular (GR) si cada regla o producción
cumple con las siguientes formas:
1.- A → a
2.- A → aB
3.- A → λ
Donde A, B son miembros de V y a es miembro de ∑ .
Una GR G genera un lenguaje regular L(G).
Ejemplo
La siguiente es una GCL ( λ U (ab)+a*)
G: S → abSA | λ
A → Aa | λ
una correspondiente gramática regular sería:
S → aB | λ
B → bS | bA
A → aA | λ
1.4 Representación de Gramáticas
En las secciones anteriores, se usaron pequeñas gramáticas
para generar lenguajes también pequeños. Esos ejemplos
sirvieron para ilustrar el uso de gramáticas para definir lenguajes.
Por otra parte, en el diseño de lenguajes de programación se
maneja sintaxis y alfabetos mas complejas y mas grandes. Esto
Por supuesto, incrementa la complejidad de las reglas para
generar el lenguaje.
Notación de BNF.
John Backus y Peter Naur inventaron un sistema de reglas para
definir el lenguaje de programación ALGOL 60. Este sistema
recibió el nombre de Backus-Naur Form o BNF. La sintaxis del
Pascal también fue definido con este sistema o técnica, y hoy en
día se usa para definir la gran mayoría de los lenguajes de
programación
Una especificación BNF es un conjunto de reglas de producción,
escritas como:
Diagramas Sintácticos
Es también un tipo de notación para especificar la sintaxis de
Un lenguaje. La diferencia con la notación BNF es que en esta
se usan líneas y figuras en lugar de nombres.
jueves, 20 de mayo de 2010
AUTOMATAS Y LENGUAJES
DEFINICIONES PREVIAS
Símbolo: Es un conjunto que se deja como verdad, los símbolos son letras, dígitos, caracteres o cadenas de letras y/o caracteres asi como también las palabras reservadas de algún lenguaje de programación. Por ejemplo:
A,b,c,#,%,0,1,+,*,then, end, else.
Vocabulario o Alfabeto: Es un conjunto finito de símbolos. El alfabeto esta representado por el símbolo V y se define por enumeración en forma ascendente. Para decir que un símbolo pertenece a cierto alfabeto se denota por el símbolo Є. Ejemplo:
V1 {A, B, C, D, E,}
V2 {a, b, c, 0, 1, 2}
V3 {if, then, end, a, b, =, ;, >}
Cadena: Es la secuencia de símbolos de un determinado alfabeto, por ejemplo: utilizando los alfabetos del tiempo anterior
abc es una cadena del alfabeto V2
if a>b then b=a; es una cadena del alfabeto V3
Longitud de Cadena: Es el numero de símbolos que tiene la cadena. Por ejemplo:
|abcd| 4
|if a>b then b=a;| 9
Cadena vacía: Es aquella que no tiene símbolos y se representa con el símbolo λ y su longitud es cero. Ejemplo:
|λ| 0
Concatenación de cadenas: Es aquella en donde dos cadenas α y β forman una nueva αβ integrados pos los símbolos de la cadena α seguidos por los de la β. El elemento neutro de la concatenación es λ. Ejemplo:
αλ = λα = α
Universo del discurso: Es el conjunto finito de todas las cadenas que se pueden formar con los símbolos de un alfabeto y se representa W(V). la cadena vacía también pertenece a W(V). Ejemplo:
del alfabeto V={a}
W(V)={λ, a, aa, aaa, aaaa, ……}
Lenguaje: Es un subconjunto del universo del discurso o también se puede definir como un conjunto de palabras de un determinado alfabeto. Ejemplo: sobre el alfabeto {0, 1}. Este lenguaje tiene infinitas cadenas. Algunas cadenas de este lenguaje serian
λ
0
1
0011
010
0110
000000101101
111111
Lenguaje vacio: Es un conjunto vacio que se denota por {0}. Hay que tener cuidado de no confundirlo con una cadena vacía {λ} ya que en este caso el numero de elementos (Cardinal) es diferente. Ejemplo:
Cardinal ({0}) = 0
Cardinal ({λ}) = 1
Gramática: Es el conjunto de cadenas de símbolos que constituyen un lenguaje.
Autómata: Es una construcción lógica que recibe una entrada y produce una salida. En caso de los procesadores de lenguaje 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.
Símbolo: Es un conjunto que se deja como verdad, los símbolos son letras, dígitos, caracteres o cadenas de letras y/o caracteres asi como también las palabras reservadas de algún lenguaje de programación. Por ejemplo:
A,b,c,#,%,0,1,+,*,then, end, else.
Vocabulario o Alfabeto: Es un conjunto finito de símbolos. El alfabeto esta representado por el símbolo V y se define por enumeración en forma ascendente. Para decir que un símbolo pertenece a cierto alfabeto se denota por el símbolo Є. Ejemplo:
V1 {A, B, C, D, E,}
V2 {a, b, c, 0, 1, 2}
V3 {if, then, end, a, b, =, ;, >}
Cadena: Es la secuencia de símbolos de un determinado alfabeto, por ejemplo: utilizando los alfabetos del tiempo anterior
abc es una cadena del alfabeto V2
if a>b then b=a; es una cadena del alfabeto V3
Longitud de Cadena: Es el numero de símbolos que tiene la cadena. Por ejemplo:
|abcd| 4
|if a>b then b=a;| 9
Cadena vacía: Es aquella que no tiene símbolos y se representa con el símbolo λ y su longitud es cero. Ejemplo:
|λ| 0
Concatenación de cadenas: Es aquella en donde dos cadenas α y β forman una nueva αβ integrados pos los símbolos de la cadena α seguidos por los de la β. El elemento neutro de la concatenación es λ. Ejemplo:
αλ = λα = α
Universo del discurso: Es el conjunto finito de todas las cadenas que se pueden formar con los símbolos de un alfabeto y se representa W(V). la cadena vacía también pertenece a W(V). Ejemplo:
del alfabeto V={a}
W(V)={λ, a, aa, aaa, aaaa, ……}
Lenguaje: Es un subconjunto del universo del discurso o también se puede definir como un conjunto de palabras de un determinado alfabeto. Ejemplo: sobre el alfabeto {0, 1}. Este lenguaje tiene infinitas cadenas. Algunas cadenas de este lenguaje serian
λ
0
1
0011
010
0110
000000101101
111111
Lenguaje vacio: Es un conjunto vacio que se denota por {0}. Hay que tener cuidado de no confundirlo con una cadena vacía {λ} ya que en este caso el numero de elementos (Cardinal) es diferente. Ejemplo:
Cardinal ({0}) = 0
Cardinal ({λ}) = 1
Gramática: Es el conjunto de cadenas de símbolos que constituyen un lenguaje.
Autómata: Es una construcción lógica que recibe una entrada y produce una salida. En caso de los procesadores de lenguaje 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.
Cuestionario (Conceptos Básicos)
1.- Define que es un Bit
Un bit es un dígito del sistema de numeración binario.
Mientras que en el sistema de numeración decimal se usan diez dígitos, en el binario se usan sólo dos dígitos, el 0 y el 1. Un bit o dígito binario puede representar uno de esos dos valores, 0 ó 1.
El bit es la unidad mínima de información empleada en informática, en cualquier dispositivo digital, o en la teoría de la información. Con él, podemos representar dos valores cuales quiera, como verdadero o falso, abierto o cerrado, blanco o negro, norte o sur, masculino o femenino, rojo o azul, etc. Basta con asignar uno de esos valores al estado de "apagado" (0), y el otro al estado de "encendido" (1).
2.- Define que es un Nibble
Se denomina nibble o cuarteto al conjunto de cuatro dígitos binarios (bits) o medio octeto. Su interés se debe a que cada cifra en hexadecimal (0, 1, 2,..., 9, A, B, C, D, E, F) se puede representar con un cuarteto, puesto que 24=16. También el cuarteto es la base del sistema de codificación BCD. A continuación se muestra la correspondencia entre las dieciséis cifras hexadecimales y sus correspondientes representaciones binarias en forma de cuarteto:
0000 = 0,
0001 = 1,
0010 = 2,
0011 = 3,
0100 = 4,
0101 = 5,
0110 = 6,
0111 = 7,
1000 = 8,
1001 = 9,
1010 = A,
1011 = B,
1100 = C,
1101 = D,
1110 = E,
1111 = F.
3.- Con que tipo de señales trabajan los circuitos digitales
La estructura de los circuitos digitales no difieren mucho de los analógicos pero su diferencia fundamental es que trabajan con señales discretas con dos únicos valores posibles.
La señal digital es un tipo de señal generada por algún tipo de fenómeno electromagnético en que cada signo que codifica el contenido de la misma puede ser analizado en término de algunas magnitudes que representan valores discretos, en lugar de valores dentro de un cierto rango. Por ejemplo, el interruptor de la luz sólo puede tomar dos valores o estados: abierto o cerrado, o la misma lámpara: encendida o apagada. Esto no significa que la señal físicamente sea discreta ya que los campos electromagnéticos suelen ser continuos, sino que en general existe una forma de discretizarla unívocamente.
4.- Define que es un circuito integrado
Un circuito integrado (CI), es una pastilla pequeña de material semiconductor, de algunos milímetros cuadrados de área, sobre la que se fabrican circuitos electrónicos generalmente mediante fotolitografía y que está protegida dentro de un encapsulado de plástico o cerámica. El encapsulado posee conductores metálicos apropiados para hacer conexión entre la pastilla y un circuito impreso.
5.- Cuales son los tipos de tecnología de fabricación de un circuito integrado
Los circuitos integrados digitales se pueden clasificar en dos grandes grupos de acuerdo al tipo de transistores utilizados para implementar sus funciones internas de conmutación en bipolares y MOS.
Los circuitos integrados digitales bipolares se fabrican con transistores bipolares tipo NPN y PNP y los de tipo MOS utilizan MOSFET´s (transistores de efecto de campo de compuerta aislada) tipo N y P.
Un bit es un dígito del sistema de numeración binario.
Mientras que en el sistema de numeración decimal se usan diez dígitos, en el binario se usan sólo dos dígitos, el 0 y el 1. Un bit o dígito binario puede representar uno de esos dos valores, 0 ó 1.
El bit es la unidad mínima de información empleada en informática, en cualquier dispositivo digital, o en la teoría de la información. Con él, podemos representar dos valores cuales quiera, como verdadero o falso, abierto o cerrado, blanco o negro, norte o sur, masculino o femenino, rojo o azul, etc. Basta con asignar uno de esos valores al estado de "apagado" (0), y el otro al estado de "encendido" (1).
2.- Define que es un Nibble
Se denomina nibble o cuarteto al conjunto de cuatro dígitos binarios (bits) o medio octeto. Su interés se debe a que cada cifra en hexadecimal (0, 1, 2,..., 9, A, B, C, D, E, F) se puede representar con un cuarteto, puesto que 24=16. También el cuarteto es la base del sistema de codificación BCD. A continuación se muestra la correspondencia entre las dieciséis cifras hexadecimales y sus correspondientes representaciones binarias en forma de cuarteto:
0000 = 0,
0001 = 1,
0010 = 2,
0011 = 3,
0100 = 4,
0101 = 5,
0110 = 6,
0111 = 7,
1000 = 8,
1001 = 9,
1010 = A,
1011 = B,
1100 = C,
1101 = D,
1110 = E,
1111 = F.
3.- Con que tipo de señales trabajan los circuitos digitales
La estructura de los circuitos digitales no difieren mucho de los analógicos pero su diferencia fundamental es que trabajan con señales discretas con dos únicos valores posibles.
La señal digital es un tipo de señal generada por algún tipo de fenómeno electromagnético en que cada signo que codifica el contenido de la misma puede ser analizado en término de algunas magnitudes que representan valores discretos, en lugar de valores dentro de un cierto rango. Por ejemplo, el interruptor de la luz sólo puede tomar dos valores o estados: abierto o cerrado, o la misma lámpara: encendida o apagada. Esto no significa que la señal físicamente sea discreta ya que los campos electromagnéticos suelen ser continuos, sino que en general existe una forma de discretizarla unívocamente.
4.- Define que es un circuito integrado
Un circuito integrado (CI), es una pastilla pequeña de material semiconductor, de algunos milímetros cuadrados de área, sobre la que se fabrican circuitos electrónicos generalmente mediante fotolitografía y que está protegida dentro de un encapsulado de plástico o cerámica. El encapsulado posee conductores metálicos apropiados para hacer conexión entre la pastilla y un circuito impreso.
5.- Cuales son los tipos de tecnología de fabricación de un circuito integrado
Los circuitos integrados digitales se pueden clasificar en dos grandes grupos de acuerdo al tipo de transistores utilizados para implementar sus funciones internas de conmutación en bipolares y MOS.
Los circuitos integrados digitales bipolares se fabrican con transistores bipolares tipo NPN y PNP y los de tipo MOS utilizan MOSFET´s (transistores de efecto de campo de compuerta aislada) tipo N y P.
Suscribirse a:
Entradas (Atom)