37126678
Description
Mind Map by Boris Roque, updated more than 1 year ago
|
Created by Boris Roque
over 2 years ago
|
|
Clasificación de Gramática y
Lenguajes de Chomsky
- Llamada también Jerarquía de Chomsky es una
clasificación jerárquica de distintos tipos de gramáticas
formales que generan lenguajes formales.
- Esta jerarquía fue descrita por Noam Chomsky en 1956
- La jerarquía de Chomsky consta de 4 niveles
- Gramáticas de tipo 0
- que incluye a todas las gramáticas formales. Estas gramáticas generan
todos los lenguajes capaces de ser reconocidos por una máquina de Turing.
Los lenguajes son conocidos como lenguajes recursivamente enumerables.
Nótese que esta categoría es diferente de la de los lenguajes recursivos,
cuya decisión puede ser realizada por una máquina de Turing que se
detenga.
- que incluye a todas las gramáticas formales. Estas gramáticas generan
todos los lenguajes capaces de ser reconocidos por una máquina de Turing.
Los lenguajes son conocidos como lenguajes recursivamente enumerables.
Nótese que esta categoría es diferente de la de los lenguajes recursivos,
cuya decisión puede ser realizada por una máquina de Turing que se
detenga.
- Gramáticas de tipo 1
- Generan los lenguajes sensibles al contexto. Los lenguajes
descritos por estas gramáticas son exactamente todos
aquellos lenguajes reconocidos por una máquina de Turing
determinista cuya cinta de memoria está acotada por un
cierto número entero de veces sobre la longitud de entrada,
también conocidas como autómatas linealmente acotados.
- Generan los lenguajes sensibles al contexto. Los lenguajes
descritos por estas gramáticas son exactamente todos
aquellos lenguajes reconocidos por una máquina de Turing
determinista cuya cinta de memoria está acotada por un
cierto número entero de veces sobre la longitud de entrada,
también conocidas como autómatas linealmente acotados.
- Gramáticas de tipo 2
- Generan los lenguajes independientes del contexto. Estos
lenguajes son aquellos que pueden ser reconocidos por un
autómata con pila.
- Generan los lenguajes independientes del contexto. Estos
lenguajes son aquellos que pueden ser reconocidos por un
autómata con pila.
- Gramáticas de tipo 3
- Generan los lenguajes regulares. Estas gramáticas se restringen a aquellas
reglas que tienen en la parte izquierda un no terminal, y en la parte derecha
un solo terminal, posiblemente seguido de un no terminal. Estos lenguajes
son aquellos que pueden ser aceptados por un autómata finito. También
esta familia de lenguajes pueden ser obtenidas por medio de expresiones
regulares.
- Generan los lenguajes regulares. Estas gramáticas se restringen a aquellas
reglas que tienen en la parte izquierda un no terminal, y en la parte derecha
un solo terminal, posiblemente seguido de un no terminal. Estos lenguajes
son aquellos que pueden ser aceptados por un autómata finito. También
esta familia de lenguajes pueden ser obtenidas por medio de expresiones
regulares.
- Cada lenguaje regular es a su vez libre del contexto, asimismo un lenguaje libre del contexto es
también dependiente del contexto, este es recursivo y a su vez, recursivamente enumerable. Las
inclusiones son, sin embargo, propias, es decir, existen en cada nivel lenguajes que no están en
niveles anteriores.
- Gramáticas Tipo 0
- Recursivamente Enumerable
- Autómata Turing
- Autómata Turing
- Recursivamente Enumerable
- Gramáticas Tipo 1
- Dependiente del Contexto
- Autómata Linealmente
Acotado
- Autómata Linealmente
Acotado
- Dependiente del Contexto
- Gramáticas Tipo 2
- Independiente del Contexto
- Autómata con Pila
- Autómata con Pila
- Independiente del Contexto
- Gramáticas Tipo 3
- Regular
- Autómata Finito
- Autómata Finito
- Regular
- Gramáticas Tipo 0
- Gramáticas de tipo 0
Media attachments
Want to create your own Mind Maps for free with GoConqr? Learn more.