Jerarquía de Chomsky en teoría de la computación – Part 1

Según la jerarquía de Chomsky , la gramática se divide en 4 tipos de la siguiente manera: 

  1. El tipo 0 se conoce como gramática sin restricciones.
  2. El tipo 1 se conoce como gramática sensible al contexto.
  3. El tipo 2 se conoce como una gramática libre de contexto.
  4. 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   <strong>\alpha \to \beta         </strong>where 

\alpha         is ( V + T)* V ( V + T)* 
V : Variables 
T : Terminals. 
\beta         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 \to \beta         
|\alpha |<=|\beta |

Esa es la cuenta del símbolo en  \alpha         es menor o igual a \beta

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 \beta

|\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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *