Según la jerarquía de Chomsky , la gramática se divide en 4 tipos de la siguiente manera:
- El tipo 0 se conoce como gramática sin restricciones.
- El tipo 1 se conoce como gramática sensible al contexto.
- El tipo 2 se conoce como una gramática libre de contexto.
- Tipo 3 Gramática Regular.
Tipo 0: Gramática sin restricciones:
Las gramáticas de tipo 0 incluyen toda la gramática formal. Los lenguajes de gramática tipo 0 son reconocidos por la máquina de turing. Estos lenguajes también se conocen como lenguajes recursivamente enumerables.
Gramática Producción en forma de 
where
\alpha is ( V + T)* V ( V + T)* V : Variables T : Terminals.
is ( V + T )*.
En el tipo 0 debe haber al menos una variable en el lado izquierdo de la producción.
Por ejemplo:
Sab --> ba A --> S
Aquí, las Variables son S, A y las Terminales a, b.
Tipo 1: gramática sensible al contexto
Las gramáticas de tipo 1 generan lenguajes sensibles al contexto. El lenguaje generado por la gramática es reconocido por Linear Bound Automata
En Tipo 1
- En primer lugar, la gramática de tipo 1 debería ser de tipo 0.
- Gramática Producción en forma de
|\alpha |<=|\beta |
Esa es la cuenta del símbolo en 
es menor o igual a 
También β ∈ (V + T) +
es decir, β no puede ser ε
Por ejemplo:
S --> AB AB --> abc B --> b
Tipo 2: gramática libre de contexto: las gramáticas de tipo 2 generan lenguajes libres de contexto. El lenguaje generado por la gramática es reconocido por un autómata Pushdown . En Tipo 2:
- En primer lugar, debe ser Tipo 1.
- El lado izquierdo de la producción solo puede tener una variable y no hay restricción en
|\alfa | = 1.
Por ejemplo:
S --> AB A --> a B --> b
Tipo 3: gramática regular: las gramáticas de tipo 3 generan lenguajes regulares. Estos lenguajes son exactamente todos los lenguajes que pueden ser aceptados por un autómata de estado finito. El tipo 3 es la forma de gramática más restringida.
El tipo 3 debe estar en la forma dada solamente:
V --> VT / T (left-regular grammar) (or) V --> TV /T (right-regular grammar)
Por ejemplo:
S --> a
La forma anterior se llama gramática estrictamente regular.
Hay otra forma de gramática regular llamada gramática regular extendida. Ene sta forma:
V --> VT* / T*. (extended left-regular grammar) (or) V --> T*V /T* (extended right-regular grammar)
Por ejemplo :
S --> ab.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA