chomsky
Páginas: 3 (625 palabras)
Publicado: 19 de septiembre de 2013
Nombre: Eduardo Rodríguez Romero
Matrícula: 005380
Nombre del curso: Teoría computacional
Nombre del profesor:
Hernán Darío Hernández
Módulo: Cibernética
Actividad: Tipos derelaciones entre conjuntos e investigación Jerarquía de Chomsky
Fecha: 13 de septiembre de 2013
Bibliografía:
http://www.slideshare.net/DavidAngel90/jerarquia-de-chomsky-5732743http://www.wikipedia.com/wiki/Chomsky_hierarchy
http://www.itz.edu.mx/~lveyna/automatas/unidad2.htm
www.csi.ull.es/~sande/talf/talf.html
Apuntes tomados y presentación dada por el maestro el día
Dado A= {1, 2,3,4}.
R1= {(1,1), (2,2), (3,3), (4,4), (1,2), (1,3), (1,4), (2,3)}
R1
TIPO DE RELACIÓN: Relación de orden
R2= {(1,1), (2,2), (1,2),(2,1), (3,3), (3,4), (4,3), (4,4)}
R2
TIPO DE RELACIÓN: Reflexiva y simétrica, no se puede lograr una relación de orden, ni con cerraduras debido a quesus relaciones tienen simetría y la Relación de Orden debe de ser anti simétrica y con este hecho ya no se puede modificar.
LA JERARQUÍA DE CHOMSKY
Es una clasificación jerárquica de distintostipos de gramáticas formales que generan leguajes formales; fue descrita por Noam Chomsky en 1956. Clasificó las gramáticas en 4 familias:
1. Las no restringidas (tipo 0)
2. Sensibles al contexto(tipo 1)
3. Independientes al contexto (tipo 2)
4. Gramáticas regulares (tipo 3)
Gramática
Idiomas
Tipo 0
Recurrentemente enumerable
Tipo 1
Sensible al contexto
Tipo 2
Context-free
Tipo 3Regular
Gramáticas formales
Una gramática formal consta de un conjunto finito de símbolos terminales (las palabras en un lenguaje formal), un conjunto finito de símbolos no terminales, unconjunto de reglas de producción con un lado izquierdo y otro derecho, y un símbolo inicial. Las reglas se aplican sustituyendo la parte de la izquierda por la parte de la derecha. Una derivación es una...
Nombre: Eduardo Rodríguez Romero
Matrícula: 005380
Nombre del curso: Teoría computacional
Nombre del profesor:
Hernán Darío Hernández
Módulo: Cibernética
Actividad: Tipos derelaciones entre conjuntos e investigación Jerarquía de Chomsky
Fecha: 13 de septiembre de 2013
Bibliografía:
http://www.slideshare.net/DavidAngel90/jerarquia-de-chomsky-5732743http://www.wikipedia.com/wiki/Chomsky_hierarchy
http://www.itz.edu.mx/~lveyna/automatas/unidad2.htm
www.csi.ull.es/~sande/talf/talf.html
Apuntes tomados y presentación dada por el maestro el día
Dado A= {1, 2,3,4}.
R1= {(1,1), (2,2), (3,3), (4,4), (1,2), (1,3), (1,4), (2,3)}
R1
TIPO DE RELACIÓN: Relación de orden
R2= {(1,1), (2,2), (1,2),(2,1), (3,3), (3,4), (4,3), (4,4)}
R2
TIPO DE RELACIÓN: Reflexiva y simétrica, no se puede lograr una relación de orden, ni con cerraduras debido a quesus relaciones tienen simetría y la Relación de Orden debe de ser anti simétrica y con este hecho ya no se puede modificar.
LA JERARQUÍA DE CHOMSKY
Es una clasificación jerárquica de distintostipos de gramáticas formales que generan leguajes formales; fue descrita por Noam Chomsky en 1956. Clasificó las gramáticas en 4 familias:
1. Las no restringidas (tipo 0)
2. Sensibles al contexto(tipo 1)
3. Independientes al contexto (tipo 2)
4. Gramáticas regulares (tipo 3)
Gramática
Idiomas
Tipo 0
Recurrentemente enumerable
Tipo 1
Sensible al contexto
Tipo 2
Context-free
Tipo 3Regular
Gramáticas formales
Una gramática formal consta de un conjunto finito de símbolos terminales (las palabras en un lenguaje formal), un conjunto finito de símbolos no terminales, unconjunto de reglas de producción con un lado izquierdo y otro derecho, y un símbolo inicial. Las reglas se aplican sustituyendo la parte de la izquierda por la parte de la derecha. Una derivación es una...
Leer documento completo
Regístrate para leer el documento completo.