Chomsky hierarchy

Las gramáticas de tipo 3 generan los lenguajes regulares . Dicha gramática restringe sus reglas a un único no terminal en el lado izquierdo y un lado derecho que consta de un único terminal, posiblemente seguido de un único no terminal, en cuyo caso la gramática es regular por la derecha . Alternativamente, todas las reglas pueden tener sus lados derechos consistiendo en un único terminal, posiblemente precedido por un único no terminal ( regular por la izquierda ). Estas generan los mismos lenguajes. Sin embargo, si se combinan reglas regulares por la izquierda y reglas regulares por la derecha, el lenguaje ya no tiene por qué ser regular. La regla${\displaystyle S\rightarrow \varepsilon }$También está permitido aquí si${\displaystyle S}$No aparece en el lado derecho de ninguna regla. Estos lenguajes son precisamente todos los lenguajes que puede determinar un autómata de estados finitos . Además, esta familia de lenguajes formales se puede obtener mediante expresiones regulares . Los lenguajes regulares se utilizan comúnmente para definir patrones de búsqueda y la estructura léxica de los lenguajes de programación.

Por ejemplo, el lenguaje regular${\displaystyle L=\{a^{n}\mid n>0\}}$es generado por la gramática de tipo 3${\displaystyle G=(\{S\},\{a\},P,S)}$con las producciones${\displaystyle P}$siendo lo siguiente.

S → aS

S → a

En lingüística , un lenguaje que no es regular se denomina supraregular . ^{[ 8 ] [ 9 ]}

Las gramáticas de tipo 2 generan los lenguajes libres de contexto . Estos se definen mediante reglas de la forma${\displaystyle A\rightarrow \alpha }$con${\displaystyle A}$ser un no terminal y${\displaystyle \alpha }$siendo una cadena de terminales y/o no terminales. Estos lenguajes son exactamente todos los lenguajes que puede reconocer un autómata de pila no determinista . Los lenguajes libres de contexto —o más bien su subconjunto de lenguajes libres de contexto deterministas— son la base teórica de la estructura de frases de la mayoría de los lenguajes de programación , aunque su análisis semántico incluye la resolución de nombres sensible al contexto debido a las declaraciones y el ámbito . A menudo se utiliza un subconjunto de gramáticas para facilitar el análisis sintáctico, como por ejemplo mediante un analizador LL .

Por ejemplo, el lenguaje libre de contexto ${\displaystyle L=\{a^{n}b^{n}\mid n>0\}}$es generado por la gramática de tipo 2${\displaystyle G=(\{S\},\{a,b\},P,S)}$con las producciones${\displaystyle P}$siendo lo siguiente.

S → aSb

S → ab

El lenguaje es libre de contexto pero no regular (según el lema de bombeo para lenguajes regulares ).

Todo lenguaje libre de contexto puede generarse mediante una gramática en forma normal de Chomsky .

Las gramáticas de tipo 1 generan lenguajes sensibles al contexto . Estas gramáticas tienen reglas de la forma${\displaystyle \alpha A\beta \rightarrow \alpha \gamma \beta }$con${\displaystyle A}$un no terminal y${\displaystyle \alpha }$,${\displaystyle \beta }$y${\displaystyle \gamma }$cadenas de terminales y/o no terminales. Las cadenas${\displaystyle \alpha }$y${\displaystyle \beta }$puede estar vacío, pero${\displaystyle \gamma }$debe no estar vacío. La regla${\displaystyle S\rightarrow \epsilon }$está permitido si${\displaystyle S}$No aparece en el lado derecho de ninguna regla. Los lenguajes descritos por estas gramáticas son precisamente todos los lenguajes que puede reconocer un autómata lineal acotado (una máquina de Turing no determinista cuya cinta está limitada por una constante multiplicada por la longitud de la entrada).

Por ejemplo, el lenguaje sensible al contexto ${\displaystyle L=\{a^{n}b^{n}c^{n}\mid n>0\}}$es generado por la gramática de tipo 1${\displaystyle G=(\{S,A,B,C,W,Z\},\{a,b,c\},P,S)}$con las producciones${\displaystyle P}$siendo lo siguiente.

S → aBC

S → aSBC

CB → CZ

CZ → WZ

WZ → WC

WC → BC

aB → ab

bB → bb

bC → bc

cC → cc

El lenguaje es sensible al contexto pero no libre de contexto (por el lema de bombeo para lenguajes libres de contexto ). Una prueba de que esta gramática genera${\displaystyle L=\{a^{n}b^{n}c^{n}\mid n>0\}}$se esboza en el artículo sobre gramáticas sensibles al contexto .

Las gramáticas de tipo 0 incluyen todas las gramáticas formales. No hay restricciones en las reglas de producción. Generan exactamente todos los lenguajes que pueden ser reconocidos por una máquina de Turing , por lo que cualquier lenguaje que sea posible generar puede ser generado por una gramática de tipo 0. ^{[ 10 ]} Estos lenguajes también se conocen como lenguajes recursivamente enumerables o reconocibles por Turing . ^{[ 10 ]} Nótese que esto es diferente de los lenguajes recursivos , que pueden ser decididos por una máquina de Turing que siempre se detiene .