Jerarquia De La Computacion
Páginas: 3 (552 palabras)
Publicado: 2 de agosto de 2011
Jerarquía de Chomsky
Dentro del campo de informática, específicamente en el área de lenguajes formales, Jerarquía de Chomsky (referido de vez en cuando como Jerarquía de Chomsky-Schützenberger) esa jerarquía de la contención de clases de gramáticas formales.
Esta jerarquía de gramáticas fue descrita por Noam Chomsky en 1956. También se nombra después Marcel-Paul Schützenberger quiéndesempeñó un papel crucial en el desarrollo de la teoría lenguajes formales.
La jerarquía
La jerarquía de Chomsky consiste en los niveles siguientes:
* Gramáticas Type-0 (gramáticas sin restricción)incluya todas las gramáticas formales. Generan exactamente todas las idiomas que se puedan reconocer por a Máquina de Turing. Estas idiomas también se conocen como idiomas recurrentemente enumerable.Hay que observar que esto es diferente de idiomas recurrentes cuál puede ser decidido por máquina de Turing siempre-que para.
* Gramáticas del Type- 1 (gramáticas sensibles al contexto) genereidiomas sensibles al contexto. Estas gramáticas tienen reglas de la forma con A un no terminal y α, β y γ cadenas de terminales y de nonterminals. Las secuencias α y β puede ser vacío, pero γ debe serno vacío. La regla se permite si S no aparece en el derecho de ninguna regla. Las idiomas descritas por estas gramáticas son exactamente todas las idiomas que se pueden reconocer por a autómatalimitado linear (una máquina no determinista de Turing que cinta es limitada por las épocas constantes la longitud de la entrada.)
* Gramáticas Type-2 (gramáticas independientes del contexto) genereidiomas context-free. Éstos son definidos por las reglas de la forma con A un no terminal y γ una cadena de terminales y de nonterminals. Estas idiomas son exactamente todas las idiomas que se puedenreconocer por un no determinista autómata del pushdown. Las idiomas libres del contexto son la base teórica para el sintaxis de la mayoría lenguajes de programación.
* Gramáticas Type-3...
Dentro del campo de informática, específicamente en el área de lenguajes formales, Jerarquía de Chomsky (referido de vez en cuando como Jerarquía de Chomsky-Schützenberger) esa jerarquía de la contención de clases de gramáticas formales.
Esta jerarquía de gramáticas fue descrita por Noam Chomsky en 1956. También se nombra después Marcel-Paul Schützenberger quiéndesempeñó un papel crucial en el desarrollo de la teoría lenguajes formales.
La jerarquía
La jerarquía de Chomsky consiste en los niveles siguientes:
* Gramáticas Type-0 (gramáticas sin restricción)incluya todas las gramáticas formales. Generan exactamente todas las idiomas que se puedan reconocer por a Máquina de Turing. Estas idiomas también se conocen como idiomas recurrentemente enumerable.Hay que observar que esto es diferente de idiomas recurrentes cuál puede ser decidido por máquina de Turing siempre-que para.
* Gramáticas del Type- 1 (gramáticas sensibles al contexto) genereidiomas sensibles al contexto. Estas gramáticas tienen reglas de la forma con A un no terminal y α, β y γ cadenas de terminales y de nonterminals. Las secuencias α y β puede ser vacío, pero γ debe serno vacío. La regla se permite si S no aparece en el derecho de ninguna regla. Las idiomas descritas por estas gramáticas son exactamente todas las idiomas que se pueden reconocer por a autómatalimitado linear (una máquina no determinista de Turing que cinta es limitada por las épocas constantes la longitud de la entrada.)
* Gramáticas Type-2 (gramáticas independientes del contexto) genereidiomas context-free. Éstos son definidos por las reglas de la forma con A un no terminal y γ una cadena de terminales y de nonterminals. Estas idiomas son exactamente todas las idiomas que se puedenreconocer por un no determinista autómata del pushdown. Las idiomas libres del contexto son la base teórica para el sintaxis de la mayoría lenguajes de programación.
* Gramáticas Type-3...
Leer documento completo
Regístrate para leer el documento completo.