TEORIA DE LA COMPUTACION.

OBJETIVO DE LA MATERIA: OBJETIVO DE LA MATERIA: EL ESTUDIANTE COMPRENDERÁ LA BASE TEÓRICA PARA LA CONSTRUCCIÓN DE SISTEMAS FORMALES Y UTILIZARÁ TÉCNICAS DE PROGRAMACIÓN PARA MODELARLOS.

Profesor: M.C. José Angel Toledo Alvarez
http://angel-toledo.blogspot.com/
taja2005@gmail.com

EXAMEN DE RECONOCIMIENTO

1.- Defina los siguientes conceptos: alfabeto, carácter, palabra y lenguaje.

2.- Explique ampliamente que es la Teoría de Conjuntos y para que sirve.

3.- Describa de manera esquemática como esta construido (estructuralmente) nuestro idioma ESPAÑOL.

4.- Explique ampliamente que es la LOGICA PROPOSICIONAL y para que sirve.

5.- Explique que diferencias existen entre una TAUTOLOGIA y una CONTRADICCION.

6.- Describa el concepto de AUTOMATA, su clasificación y sus aplicaciones.

7.- Con la ayuda de un ejemplo, describa que es una TABLA DE VERDAD y como se utiliza.

8.- Realice un GRAFO (o DIGRAFO) que ilustre el comportamiento de una máquina expendedora de refrescos.

9.- Explique ampliamente cuales son las fases de un COMPILADOR (al realizar la ejecución de un programa).

10.- Explique ampliamente cual es el factor común entre un COMPILADOR, un TRADUCTOR, un ENCRIPTADOR y el IDIOMA ZAPOTECO.

Unidad 1.- Introducción.

1.1 Autómatas, computabilidad y
complejidad.
1.2 Nociones matemáticas.
1.2.1 Conjuntos
1.2.2 Funciones y Relaciones
1.2.3 Cadenas y Lenguajes
1.3 Inducción matemática.

Transparencia de Informática teórica (Grupo EVANNAI): http://et.evannai.inf.uc3m.es/docencia/it_II/transparencias.html

The Alan Turing Home Page: http://www.turing.org.uk/turing/

The Virtual Museum of Computing: http://vmoc.museophile.sbu.ac.uk/

Informática y Matemáticas: http://biblioweb.sindominio.net/telematica/conf-ernesto/node1.html

Lenguajes Formales: http://webdiis.unizar.es/~elvira/lengForm.pdf

Teoría de la Computabilidad Computacional: http://sisbib.unmsm.edu.pe/bibvirtualdata/publicaciones/risi/N1_2004/a14.pdf
Recordatorio de Lógica Proposicional: http://es.wikipedia.org/wiki/Lógica_proposicional

Recordatorio de Teoría de Conjuntos: http://es.wikipedia.org/wiki/Teorìa_de_conjuntos

Ejercicios de Matemáticas Discretas: http://canek.uam.mx/MatDis/Matdis.htm

Actividad 1 U1: Tomando como refrencia las lecturas recomendadas, realice un mapa mental-conceptual que ilustre y clarifique el tema de la unidad 1.

TC Cuestionario 1 Introducción.

1.- Defina los siguientes conceptos: Autómatas, computabilidad y complejidad computacional.

2.- Explique ampliamente en que consiste la Teoría de Conjuntos y cuales son sus aplicaciones.

3.- Explique ampliamente en que consiste la Lógica Proposicional y cuales son sus aplicaciones.

4.- Defina y de tres ejemplos de los siguientes conceptos: Conjuntos, Funciones y Relaciones, Cadenas y Lenguajes.

5.- Explique ampliamente que es la “Inducción matemática”, para que se utiliza y de tres ejemplos de su aplicación.

6.- Defina los siguientes conceptos y de tres ejemplos de cada uno de ellos: Carácter, Símbolo, Alfabeto, palabra, cadena de caracteres, lenguaje, gramática, sintaxis, semántica.

7.- Explique cual es la diferencia entre un cuantificador existencial y un cuantificador universal y de tres ejemplos de la aplicación de cada uno de ellos.

8.- Defina los siguientes conceptos y de tres ejemplos de cada uno de ellos: Fórmulas equivalentes, Forma Normal Conjuntiva, Forma Normal Disyuntiva

9.- Realice las siguientes demostraciones:

( p "y" q )’ <--> p’ "o" q’
( p "o" q ) "o" r <--> p "o" ( q "o" r )
( p <--> q ) <--> r <--> p <--> ( q <--> r )

10.- Explique ampliamente cuales son los axiomas de Peano y de tres ejemplos de su aplicación.

Unidad 2.- Lenguajes regulares.

2.1 Autómatas finitos
2.1.1 Autómatas finitos
determinísticos.
2.1.2 Autómatas finitos No
determínisticos
2.2 Expresiones regulares.
2.3 Lenguajes no regulares.

Expresiones Regulares: http://es.wikipedia.org/wiki/Expresiones_regulares

Conociendo a las expresiones regulares: http://www.zonasiete.org/manual/ch13s03.html

Sitio de Expresiones Regulares: http://www.regular-expressions.info/

Lenguajes Regulares: http://es.wikipedia.org/wiki/Lenguaje_regular

Lenguajes regulares: http://www.itculiacan.edu.mx/apuntes/maestros/Ricardo%20Quintero/Mis%20Webs/parte%202%20Lenguajes%20Regulares/2Lenguajes%20regulares.htm

http://ji.ehu.es/kea-mac1/cas/Temario_fitxategiak/Tema2.pdf

Autómatas y Lenguajes Formales: http://pisuerga.inf.ubu.es/cgosorio/ALeF/#contenidos

Lenguajes, Gramáticas y Autómatas: http://pisuerga.inf.ubu.es/cgosorio/ALeF/UD23/lenguajes.pdf

Apuntes de Lenguajes y Autómatas: http://platon.escet.urjc.es/grupo/docencia/automatas/apuntes/

Autómatas Finitos y Lenguajes Regulares: http://dac.escet.urjc.es/~lrincon/uned/ta1/ta1-tema1.pdf

Actividad 1 U2: Tomando como refrencia las lecturas recomendadas, realice un mapa mental-conceptual que ilustre y clarifique el tema de la unidad 2.

Cuestionario de la unidad 2:

1.- Explique en que consisten las Expresiones Regulares y los Lenguajes Regulares y de 5 ejemplos reales de cada uno de estos.

2.- Explique en que consiste el AFD y el AFD y de 5 ejemplos reales de su aplicación (que ilustre cada uno de sus elementos).

3.- Explique ampliamente el lema de Bombeo y su aplicación práctica en la Teória de la Computación.

4.- Explique ampliamente en que consiste la notación BNF e ilustre su aplicación en un lenguaje de programación de alto nivel.

5.- Realice el Análisis y Diseño de un Lenguaje Regular y su Autómata correspondiente que valide diferentes expresiones polinómicas de segundo grado.

Unidad 3.- Lenguajes libres de contexto.

3.1 Gramáticas libres de contexto.
3.2 Árboles de derivación.
3.3 Formas normales de Chomsky.
3.4 Formas normales de Greibach.
3.5 Eliminación de Factores Comunes
izquierdos.
3.6 Eliminación de recursividad izquierda.
3.7 Eliminación de la ambigüedad.
3.8 Autómatas Push-Down.
3.9 Lenguajes no regulares.

Gramamática Libre de Contexto: http://es.wikipedia.org/wiki/Gramática_libre_de_contexto

Lenguajes Libres de Contexto: http://delta.cs.cinvestav.mx/~gmorales/ta/node103.html

Ciencias de la computación: http://www.exa.unicen.edu.ar/catedras/ccomp1/

LLC y Compiladores: http://www.geocities.com/marioztobon/compiladores.htm

LIC y AP: http://www.infor.uva.es/~mluisa/talf/docs/teoria/final1.pdf

Noam Chomsky, Politics or Science: http://homepages.uel.ac.uk/C.Knight/chomsky.htm

AP y LIC: http://dac.escet.urjc.es/~lrincon/uned/ta1/ta1-tema2.pdf

English Lecture: http://en.wikipedia.org/wiki/Context-free_language

Actividad 1 U3: Tomando como refrencia las lecturas recomendadas, realice un mapa mental-conceptual que ilustre y clarifique el tema de la unidad 3.

Ejercicio Práctico U3:

Escriba un programa en JAVA que traduzca una expresión regular en un autómata finitio.

Ref.- Libro "Introducción a la teoría de Autómatas, Lenguajes y Computación." de John E. Hopcroft y Jeffrey D. Ullman.

Unidad 4.- Máquinas de Turing.

4.1 Definición formal de una máquina de
Turing.
4.2 Construcción modular de una máquina
de Turing.
4.3 Lenguajes aceptados por la MT.
4.4 Variantes de una máquina de Turing.
4.5 Problemas de Hilbert.
Máquina de Computación Lógica: http://www.zator.com/Cpp/E0_1_1.htm

MT con Lego: http://www.microsiervos.com/archivo/juegos-y-diversion/maquina-de-turing-de-lego.html

Funciones calculables: http://www.usergioarboleda.edu.co/matematicas/memorias/memorias13/Máquinas%20de%20Post%20y%20de%20Turing.pdf

Máquinas de Turing: http://www.infor.uva.es/~mluisa/talf/docs/teoria/final2.pdf

Máquina de Turing Universal: http://www.infor.uva.es/~mluisa/talf/docs/teoria/final3.pdf

MT y LEF: http://dac.escet.urjc.es/~lrincon/uned/ta1/ta1-tema3.pdf

MT CINVESTAV: http://acme.math.cinvestav.mx/~basico/siete.html

English Lecture: http://www.turing.org.uk/turing/scrapbook/machine.html

Actividad 1 U4: Tomando como refrencia las lecturas recomendadas, realice un mapa mental-conceptual que ilustre y clarifique el tema de la unidad 4.

Actividad 2 U4: Realizar un análisis de los enlaces recomendados (incluyendo la "English Lecture") y realizar un Mapa Mental (Multimedia en ppt) que explique el Que, Quien, Como, Donde, Cuando, Porqué y Para qué de la Máquina de Turing argumentando ampliamente su Modelado Matemático y Algoritmo de funcionamiento.

Unidad 5.- Decibilidad.

5.1 Lenguajes Decidibles.
5.2 El problemas de Halting.
5.3 Decidibilidad de Teorías Lógicas.

Lenguajes decideibles: http://webdiis.unizar.es/~elvira/lengForm.pdf

Lógica y Computación: http://www.filosoficas.unam.mx/~morado/LogicaHoy/alvarado.htm

Lenguajes decidibles por una Máquina de Turing: http://www.filosoficas.unam.mx/~morado/LogicaHoy/alvarado.htm

Problemas de decisión:
http://www2.ing.puc.cl/~jabaier/iic2212/decision.pdf
http://es.wikipedia.org/wiki/Problema_de_decisión

Demostración del problema del paro: http://antoniojaimes.tripod.com/icc/presentaciones/c4-demo-paro.pdf

Algoritmo de Inferencia Gramatical: http://www.uv.es/hmr/Tesis/HTML/

Actividad 1 U5: Tomando como refrencia las lecturas recomendadas, realice un mapa mental-conceptual que ilustre y clarifique el tema de la unidad 5.

Unidad 6.- Reducibilidad.

6.1 Problemas insolubles para la teoría de
lenguajes.
6.2 Un problema simple insoluble.
6.3 Funciones computables.
6.4 Reducibilidad de Turing.

Complejidad Computacional: https://www.unoweb-s.uji.es/0304/IS17/ficheros0/theList/tema10.pdf
Introducciòn a la TCC: http://www3.uji.es/~martine/DOC/E45/apuntes/node47.html

Ensayo TCC: http://sisbib.unmsm.edu.pe/bibvirtualdata/publicaciones/risi/N1_2004/a14.pdf

Como ganar a la Ruleta en 21 dias: http://www-2.dc.uba.ar/materias/plp/20052C/download/charla_figueira.pdf

NP-Completitud: https://www.fdi.ucm.es/profesor/csegura/mtp0304/apuntes/NPcompletitud.pdf

Computabilidad y Algoritmos: http://juanfc.lcc.uma.es/EDU/EP/2.DescrAlgoritmos.pdf

Clases Polinómiales: http://delta.cs.cinvestav.mx/~gmorales/complex/node149.html

Presentación uniforme de la teória descriptiva de la complejidad computacional: http://www2.scielo.org.ve/scielo.php?script=sci_arttext&pid=S0001-55042002000200003&lng=pt...&nrm=iso
Otros enlaces de interes:

Sitio general de IA y Sistemas: http://pub.ufasta.edu.ar/ohcop/mapa.html

Actividad 1 U5: Tomando como refrencia las lecturas recomendadas, realice un mapa mental-conceptual que ilustre y clarifique el tema de la unidad 5.

TC Cierto o Falso: Define los conceptos y Analiza los comentarios que se encuentran en este espacio y verifica si es ciero o falso...

CONCEPTOS:
Gramatica Formal
Arbol de derivacion
Formas normales de Greibach
Formas normales de Chomsky

FRASE DE CONCEPTOS
”La gramatica formal permite especificar un lenguaje o lengua aunque para representar graficamente la forma normal de chomsky y su cadena de lenguaje un arbol de derivacion aunque para gramaticas libres de contexto enta la forma normal de Greibach.”
Cierto? o Falso?

Enlaces de interés para:
Gramática Libre de Contexto: http://es.wikipedia.org/wiki/Gramática_libre_de_contexto
Lenguajes Libres de Contexto: http://delta.cs.cinvestav.mx/~gmorales/ta/node103.html
Ciencias de la computación: http://www.exa.unicen.edu.ar/catedras/ccomp1/
LLC y Compiladores: http://www.geocities.com/marioztobon/compiladores.htm
Noam Chomsky, Politics or Science: http://homepages.uel.ac.uk/C.Knight/chomsky.htm

CONCEPTOS:
- Máquina de Turing
- Teoria de la Computabilidad
- Almacenamiento en la unidad
- Algoritmo

FRASE:
"Una máquina de Turing es una máquina que resuelve problemas que tienen solución algoritmica y son estudiaos por la Teoria de la Computabilidad, necesita un conjunto de 'reglas de transición' o 'pasos' para hacer su 'trabajo', una MT consta de una cinta con caracteres del lenguaje, un cabezal lectura/escritura y un cabezal donde almacena o borra los caracteres del lenguaje que ha validado."
Cierto? o Falso?

Enlaces:
1.- Máquina de Turing y alamacenamiento en la unidad: http://es.wikipedia.org/wiki/M%C3%A1quina_de_Turing2.- Algoritmo: http://luda.uam.mx/curso1/Introduccion%20a%20la%
20Programacion/algoritmo.htm3.- Teoría de la Computabilidad: http://es.wikipedia.org/wiki/Teor%C3%ADa_de_la_computabilidad

CONCEPTOS:
Induccion matematica
Automata
Ambigüedad
Eliminacion de la recursividad por la izquierda

FRASE
" La teoria de la computacion inicio con la induccion matematica la cual conllevo a hacer automatas las cuales pueden tener ambigüedad y estos pueden ser validadas con una gramatica la cual puede emplearse la eliminacion de la recursividad por la izquierda"
¿Cierto? o ¿Falso?

ENLACES DE INTERES:
http://es.wikipedia.org/wiki/Aut%C3%B3mata
http://es.wikipedia.org/wiki/Inducci%C3%B3n_matem%C3%A1tica

CONCEPTOS
*Chomsky
*Maquina de Turing
*Forma normal de chomshy

FRASE
"CHOMSKY DOMINO LA GRAMATICA GENERATIVA DONDE SE FORMULA LA FORMA NORMAL DE CHOMSKY QUE SIRVE PARA REPRESENTAR GRAMATICAS DONDE UTILIZO COMO BASE LA MAQUINA DE TURING EN LA CUAL SE FORMALIZA EL CONCEPTO DE ALGORITMO"
¿Cierto? o ¿Falso?

REFERENCIAS:
*MAQUINA DE TURING
http://etsiit.ugr.es/alumnos/mlii/Maquina%20de%20Turing.htm
http://www.zator.com/Cpp/E0_1_1.htm
*CHOMSKY
http://es.wikipedia.org/wiki/Noam_Chomsky
*FORMA NORMAL DE CHOMSKY
http://trevinca.ei.uvigo.es/~formella/doc/talf05/talf/node42.html

CONCEPTOS:
*Gramática de tipo 0.
*Maquina de turing.
*Lenguajes aceptados por la maquina de turing.
*Problemas computables y no computables.

"Para toda gramática de tipo 0 existe una maquina de Turing que se mueve sobre una secuencia lineal de datos que pueden resolver problemas computables y no computables."
¿Cierto o Falso?

ENLACES:
GRAMATICA TIPO 0 : http://www.frt.utn.edu.ar/sistemas/sintaxis/page15.html
MAQUINA TURING: http://es.wikipedia.org/wiki/M%C3%A1quina_de_Turing
LENGUAJES COMPUTABLES Y NO COMPUTABLES: http://campusvirtual.unex.es/cala/epistemowikia/index.php?title=Funciones_computables
LENGUAJES ACEPTADOS POR UNA MAQUINA DE TURING: http://es.wikipedia.org/wiki/Teor%C3%ADa_de_la_computabilidad

CONCEPTOS:
• Computabilidad.
• Componentes de un Automata (AFD).
• Lenguajes No Regulares.
• Lema de Bombeo.

FRASE:
“La teoria de la computabilidad es la parte de la computación que estudia los problemas de descicion que pueden ser resueltos con un algoritmo o equivalentemente con una maquina de Turing, una maquina de Turing tiene caracteristicas para leer información, esta información es un lenguaje para ello existen lenguajes que no son regulares y tecnicas para demostrarlo un ejemplo de ellos es el Lema de bombeo. Si el lenguaje L es regular existe un AFD que o reconoce. Un AFD esta constituido por una 5-tupla, estos componentes son: un conjunto de estados, un alfabeto, un estado inicial, un estado final y una regla de transicion”
¿Cierto? ó ¿Falso?

Enlaces de Interes.
Computabilidad
http://es.wikipedia.org/wiki/Teor%C3%ADa_de_la_computabilidad

Componentes de un Automata (AFD).
http://es.wikipedia.org/wiki/Aut%C3%B3mata_finito
Lenguajes No Regulares.
http://es.wikipedia.org/wiki/Lenguaje_regular
Lema de Bombeo.
http://www.itculiacan.edu.mx/apuntes/maestros/Ricardo%20Quintero/Mis%20Webs/parte%202%20Lenguajes%20Regulares/38El%20lema%20de%20bombeo.htm

CONCEPTOS:
*Simbolo
*Numero Computable
*Lenguajes aceptados por la Maquina de Turing

FRASES
"Los simbolos pueden ser caracteres o digitos(numeros) que pueden ser aproximados por un algoritmo y estos pueden ser aceptados por una Maquina de Turing ya que los lenguajes formales son aceptados por este."
-- Cierto? ó Falso?--

Links:
http://es.wikipedia.org/wiki/Teor%C3%ADa_de_la_computabilidad
http://es.wikipedia.org/wiki/Simbolo
http://biblioweb.sindominio.net/telematica/conf-ernesto/node15.html
http://mx.geocities.com/pcmuseo/infmaquinaturing.htm

CONCEPTOS:
Construcción de maquinas de turing
Bloques de construcción básicos
Expresiones regulares
Forma normal de greibach

“Frase”:

La construcción de maquinas de turing se hace mediante los bloques de construcción los cuales nos sirven para analizar expresiones regulares los cuales a su ves están formados por la forma normal de greibach
Cierto???? o falso????

Referencias:

http://es.wikipedia.org/wiki/M%C3%A1quina_de_Turing
http://es.wikipedia.org/wiki/Expresi%C3%B3n_regular
http://es.wikipedia.org/wiki/Lenguaje_regular

CONCEPTOS:
ANALISIS FUNCIONAL
FUNCIONES
AUTOMATA FINITO NO DETERMINISTICO


FRASE:
”El análisis funcional de las matemáticas donde la transición que se ejecuta en una etapa dada de un AFN puede ser incierta, y específicamente del análisis que trata del estudio de espacios de funciones.”
¿CIERTO? ¿FALSO?

ENLACES:
http://es.wikipedia.org/wiki/An%C3%A1lisis_funcional
http://www.itp.edu.mx/Tutoriales/Lenguajes_y_automatas/Principal.htm

CONCEPTOS:
Conjunto
grafo
recursividad
maquina de turing

Un grafo es un conjunto de objetos llamados vertices o nodos unidos por enlaces llamados aristas y Un conjunto es recursivo si la correspondiente función característica (que asigna el número 1 a los objetos que pertenecen al conjunto, y 0 a los que no le pertenecen) es computable en si toda definición recursiva es Turing-computable, y a la inversa, toda función computable en el sentido de Turing es recursiva
Cierto? o Falso?

Enlaces de interés para:
Conjunto: http://es.wikipedia.org/wiki/Conjunto
grafo: http://es.wikipedia.org/wiki/Grafo
recursividad: http://www.exa.unicen.edu.ar/catedras/ccomp1/
Maquina de turing: http://es.wikipedia.org/wiki/M%C3%A1quina_de_Turing

CONCEPTOS:
- Lenguaje Formal
- Máquina de Turing
- Algoritmo

" Un algoritmo es una herramienta que permite hallar la solución de un problema y su definición queda formalizada por la Máquina de Turing"

Links:
Algoritmo
http://es.wikipedia.org/wiki/Algoritmo
Maquina de Turing
http://es.wikipedia.org/wiki/M%C3%A1quina_de_Turing
Lenguajes Regulares
http://es.wikipedia.org/wiki/Lenguaje_formal

CONCEPTOS:
función computable
árbol de derivación
cadena de caracteres
maquina de turing

"UNA FUNCIÓN COMPUTABLE ES UNA CADENA DE CARACTERES QUE PUEDE SER LEIDA POR UNA MQUINA DE TURING,ESTE ENUNCIADO ES CONOCIDO COMO LA TESIS CHURCH-TURING"
¿Cierto? o ¿Falso?

LINK
www.geocities.com/pilosopica/filosofica13.htm
es.wikipedia.org/wiki/Función_computable
es.wikipedia.org/wiki/Tesis_de_Church-Turing

CONCEPTOS:
Yacc y Lex
Eliminacion de factores comunes izquierdos.
Tablas de transición


FRASE:
”Las tablas de transiciones se da entre ambas funciones de estado finito de un sistema que recibe una cadena en cada caso exactamente lo mismo que retorna la que genera las mas usuales.”
¿Cierto? ¿Falso?

ENLACES:

http://es.wikipedia.org/wiki/Yacc
http://es.wikipedia.org/wiki/Herramienta_de_programaci%C3%B3n_Lex
http://es.wikipedia.org/wiki/Tabla_de_transici%C3%B3n_de_estados

CONCEPTOS:
gramática
gramática libre de contexto
autómata finito no deterministico
maquina de turing


FRASE DE CONCEPTOS:
”La gramatica es el estudio de las reglas y principios. Donde existe gramaticas libres de contexto que parte de un simbolo no terminal, donde son las base para la creacion de automas, como lo es la maquina de turing.”
CIERTO O FALSO??

REFERENCIA:
http://es.wikipedia.org/wiki/Gram%C3%A1tica_libre_de_contexto
http://es.wikipedia.org/wiki/Aut%C3%B3mata_finito
http://es.wikipedia.org/wiki/M%C3%A1quina_de_Turing

CONCEPTOS: DECIBILIDAD, LENGUAJES DECIDIBLES, LEX YACC Y BISON.

FRASE:
Bison convierte la descripcion formal de un lenguaje, escrita como una gramatica libre de contexto. Los lenguajes decidibles so cadenas de palabras calculabres mediante funciones recursivas, un sistema formal es decidible si existe un algoritmo que diga en tiempo finito si una cadena cualquiera es un teorema o no lo es.

¿CIERTO? O ¿FALSO?

REFERENCIAS:

http://www.dsic.upv.es/~jsilva/uned/automatas1/Teoria%20de%20Automatas%20I%20(sesion%209).ppt
http://www.filosoficas.unam.mx/~morado/LogicaHoy/alvarado.htm
http://www.mitecnologico.com/Main/Decibilidad
http://es.wikipedia.org/wiki/Decibilidad
http://www.velug.org.ve/archivo/l-linux-2001-March/025778.html
http://www.ii.uam.es/~mdlcruz/docencia/compiladores/2002_2003/compiladores_02_03_yacc_bison.pdf

Responsable: Evert Valencia Chung
web:http://mx.geocities.com/takiwebox.com
Blog: http://takiwebox.blogspot.com
mail: taki_87@hotmail.com

Conceptos:

Arbol Sintáctico
Funcion
Eliminacion
Concatenacion

Frase:

"El ARBOL SINTACTICO es un árbol que refleja la estructura sintáctica de la entrada de datos. Este se representa mediante nodos, los cuales tienen una determinada FUNCION dentro del arbol. A la relacion entre cada nodo se le denomina CONCATENACION, la cual indica que de un nodo A se deriva un nodo B. Asimismo cuando un nodo no cumple las condiciones requeridas se procede a la ELIMINACION de dicho nodo".

Cierto? o Falso?

Enlances de Apoyo:

http://www.suigeneris.org/kb/display/UCABTI/Fases+de+un+Compilador

http://www.dcc.uchile.cl/~lmateu/CC10A99/Apuntes/sintaxis/index.html

CONCEPTOS:

automata finito deterministico
gramatica libre de contexto
formulacion de halting
funcion

frase de conceptos:


la gramatica libre de contexto es un conjunto de variables con los cuales representa un lenguaje, que se describen de manera de simbolos en funcion del AFD el cual puede formar estados y conjunto de transiciones, para poder hacer la formulacion de halting...



¿cierto? o ¿falso?


enlaces de interes para ....
gramatica y lenguajes
http://tomba.blogdiario.com/

automatas
http://www.mitecnologico.com/Main/AutomatasFinitosDeterministicosYNoDeterministicos
http://es.wikipedia.org/wiki/Aut%C3%B3mata_finito

funciones
http://abulafia.fciencias.unam.mx/~favio/tc71n1.pdf

CONCEPTOS:
Conjunto
Lenguajes libres de contexto
Autómatas lineales de indices
Recursividad directa

Frase

“Un conjunto de símbolos pueden ser aceptados o rechazados por un autómata lineal de índice que es parte de los lenguajes libes de contexto que se crean a partir de una gramática libre de contexto, esta a su vez puede tener una recursividad directa.”

Cierto o falso?
Referencias:
http://www.exa.unicen.edu.ar/catedras/ccomp1/Apunte5.pdf
http://es.wikipedia.org/wiki/Conjunto
http://209.85.165.104/search?q=cache:5vE7bTR1IicJ:www.matematicas.unam.mx/jloa/publicaciones/automatasyLenguajes.ps.gz+automata+lineal&hl=es&ct=clnk&cd=1&gl=mx
http://delta.cs.cinvestav.mx/~mcintosh/oldweb/tesis/genaro/node3.html
http://www.lcc.uma.es/~pastrana/EP/trabajos/17.pdf

CONCEPTOS:
Gramatica libre de contexto
Gramatica enformal normal de chomsky
Lenguaje libre de contexto

Oracion de los conceptos

Analice y decida

"Un lenguaje libre de contexto es aque producido por un gramatica libre de contexto, estas a su ves pueden ser llamadas gramaticas enformal normal de Chomsky"

Cierto? o Falso?


Ref:
http://es.wikipedia.org/wiki/Gram%C3%A1tica_libre_de_contexto
http://es.wikipedia.org/wiki/Lenguaje_libre_de_contexto
http://es.wikipedia.org/wiki/Forma_normal_de_Chomsky

CONCEPTOS:
lenguajes no regulares
conjunto
jerarquia de chomsky
gramatica libre de contexto

MI FRASE:
un ejemplo de conjunto seria
utilizar a la jerarquia de chomsky como entidad y como atributos a la gramatica libre de comntexto, la clasificacion de lenguajes como los no regulares.

cierto o falso?

ENLACES DE INTERES:

http://es.wikipedia.org/wiki/Jerarqu%C3%ADa_de_Chomsky

http://es.wikipedia.org/wiki/Gram%C3%A1tica_libre_de_contexto

http://es.wikipedia.org/wiki/Lenguaje_regular

http://es.wikipedia.org/wiki/Conjunto

Preguntas:

1. ¿Que funcion realiza un analizador lexico?
2. ¿En base a que se realizara el automata, en base al proyecto o funcion?
3. ¿Caracteristicas importantes del analizador?
4. ¿Cuales son las reglas basicas que realiza a un analizador lexico?
5. ¿Como se crea un analizador lexico?


Links de apoyo para las respuestas de las preguntas:

http://es.wikipedia.org/wiki/Analizador_l%C3%A9xico

http://nereida.deioc.ull.es/~lhp/perlexamples/node436.html

http://www.dsic.upv.es/~jsilva/uned/compiladores/Apuntes02.pdf

CONCEPTOS:
Arbol sintáctico
Forma normal de Greibach
Automatas de Push-Down
Automatas de dos pilas

FRASE:
Una gramática libre de contexto puede ser representada gracias a la forma normal de greibach, las gramaticas pueden ser representadas por un arbol sintactico y por un automata, de los cuales se derivan los automatas push-down y los automatas de dos pilas.

¿cierto? o ¿falso?

enlaces para

forma normal de greibach
es.wikipedia.org/wiki/Forma_normal_de_Greibach

arbol sintactico
www.uni.edu/~castillo/arbol-how.htm

automatas push-down
www.monografias.com/trabajos16/automatas-y-gramaticas/automatas-y-gramaticas.shtml

automatas de dos pilas
es.wikipedia.org/wiki/Tesis_de_Church-Turing

TRADUCTOR

1. ¿Cuàl seria la gramatica de un traductor?

2.Dentro de la gramatica en lo que corresponde al vocabulario ¿estarìan todos los signos de puntuacion?

3. Qué es un traductor de texto ?


4. ¿que se necesita para hacer un traductor de idioma extranjero?

5. Ventajas y desventajas de un traductor
enlaces

http://www.misrespuestas.com/que-es-un-traductor-de-texto.html

http://www.solociencia.com/informatica/06020728.htm
http://www.depi.itch.edu.mx/apacheco/expo/html/ai11/nl.html

http://www.c5.cl/Congreso/HTML/paper11.htm

http://lorien.die.upm.es/~lapiz/rtth/JORNADAS/II/articulos/6.pdf


CONCEPTOS:
- Máquina de Turing
- Contexto
- Forma normal de Greibach
- Gramatica

FRASE:

"La forma normal de greibach es un tipo estandar para representar gramaticas ya que la gramatica es el estudio de la lengua en cuanto a forma y estructura y significado."

Cierto? o Falso?

Enlaces:

1.- Gramatica: http://es.wikipedia.org/wiki/Gram%C3%A1tica

2.- forma normal de greibach: http://delta.cs.cinvestav.mx/~gmorales/ta/node113.html

3.- maquina de turing: http://www.zator.com/Cpp/E0_1_1.htm

4.- Contexto
http://es.wikipedia.org/wiki/Contexto