Jerarquia De Chomky

Motivación Jerarquía de Chomsky

La Jerarquía de Chomsky
Apuntes sobre la Complejidad

Universidad de Cantabria

Jerarquía de Chomsky

Motivación Jerarquía de Chomsky

Esquema

1

Motivación

2

Jerarquía de Chomsky Gramáticas Regulares Gramáticas Libres de Contexto Gramáticas Sensibles al Contexto

Jerarquía de Chomsky

Motivación Jerarquía de Chomsky

Ideas y NocionesComo se ha mencionado anteriormente, los lenguajes son conjuntos de palabras definidos por un alfabeto. No estamos interesados en cualquier conjunto, los lenguajes que nos interesan tienen una estructura inherente.

Jerarquía de Chomsky

Motivación Jerarquía de Chomsky

Ideas y Nociones
Las gramáticas nos marcan las reglas que han construido el lenguaje. Para detectar esas reglas nospodemos preguntar: ¿Es nuestro lenguaje una sucesión de símbolos donde el siguiente depende del anterior (o del siguiente)? en cualquiera de los casos vemos una relación simétrica. ¿Se puede separar cada palabra del lenguaje en partes más pequeñas que no dependan unas de otras? ¿Hay elementos que cambien su significado dependiendo del contexto? No se ajusta a ninguna de estas premisas pero sereconoce su estructura de alguna manera (mediante algún algoritmo).
Jerarquía de Chomsky

Motivación Jerarquía de Chomsky

Ideas y Nociones
Las gramáticas nos marcan las reglas que han construido el lenguaje. Para detectar esas reglas nos podemos preguntar: ¿Es nuestro lenguaje una sucesión de símbolos donde el siguiente depende del anterior (o del siguiente)? en cualquiera de los casos vemos unarelación simétrica. ¿Se puede separar cada palabra del lenguaje en partes más pequeñas que no dependan unas de otras? ¿Hay elementos que cambien su significado dependiendo del contexto? No se ajusta a ninguna de estas premisas pero se reconoce su estructura de alguna manera (mediante algún algoritmo).
Jerarquía de Chomsky

Motivación Jerarquía de Chomsky

Ideas y Nociones
Las gramáticas nosmarcan las reglas que han construido el lenguaje. Para detectar esas reglas nos podemos preguntar: ¿Es nuestro lenguaje una sucesión de símbolos donde el siguiente depende del anterior (o del siguiente)? en cualquiera de los casos vemos una relación simétrica. ¿Se puede separar cada palabra del lenguaje en partes más pequeñas que no dependan unas de otras? ¿Hay elementos que cambien su significadodependiendo del contexto? No se ajusta a ninguna de estas premisas pero se reconoce su estructura de alguna manera (mediante algún algoritmo).
Jerarquía de Chomsky

Motivación Jerarquía de Chomsky

Ideas y Nociones
Las gramáticas nos marcan las reglas que han construido el lenguaje. Para detectar esas reglas nos podemos preguntar: ¿Es nuestro lenguaje una sucesión de símbolos donde elsiguiente depende del anterior (o del siguiente)? en cualquiera de los casos vemos una relación simétrica. ¿Se puede separar cada palabra del lenguaje en partes más pequeñas que no dependan unas de otras? ¿Hay elementos que cambien su significado dependiendo del contexto? No se ajusta a ninguna de estas premisas pero se reconoce su estructura de alguna manera (mediante algún algoritmo).
Jerarquía deChomsky

Motivación Jerarquía de Chomsky

Ejemplos

Las sumas expresiones matemáticas que involucren simplemente números sumas y restas. ¿Que significa 3 − 4 + 2? ¿Que pasa si a esa expresión le añadimos paréntesis de este modo 3 − (4 + 2)? En JAVA, ¿que significa i + j?, ¿es lo mismo que las variables i, j sean strings que sean enteros ó números en punto flotante? Pensemos ahora en algunalengua humana, como español, ¿es fácil detectar ironía?

Jerarquía de Chomsky

Motivación Jerarquía de Chomsky

Ejemplos

Las sumas expresiones matemáticas que involucren simplemente números sumas y restas. ¿Que significa 3 − 4 + 2? ¿Que pasa si a esa expresión le añadimos paréntesis de este modo 3 − (4 + 2)? En JAVA, ¿que significa i + j?, ¿es lo mismo que las variables i, j sean strings que...