Gramática (autómata)

Una gramática ("G") desde el punto de vista de la teoría de autómatas es un conjunto finito de reglas que describen toda la secuencia de símbolos pertenecientes a un lenguaje específico L. Dos gramáticas que describan el mismo lenguaje se llaman gramáticas equivalentes.

Una gramática es una estructura algebraica formada por cuatro elementos fundamentales:

G = { NT, T, S, P }

donde

  • NT es el conjunto de elementos No Terminales
  • T es el conjunto de elementos Terminales
  • S es el Símbolo inicial de la gramática
  • P es el conjunto de Reglas de Producción

Clasificación de las gramáticas según Padilla

Según Padilla las gramáticas se clasifican de acuerdo a las reglas de sustitución y nunca se pasa autómatas 2

Tipo 0 o "No restringida o recursivamente enumerables"

Chomsky grammar 0.png

x puede ser sustituido por y si x está, ya sea, en los símbolos No Terminales o los símbolos Terminales, sin incluir la cadena vacía e y está en los símbolos No Terminales o Terminales, incluyendo la cadena vacía.”

Los lenguajes generados por este tipo de gramáticas se llaman "lenguajes sin restricciones"

Nota: "+" significa "sin incluir la cadena vacía" y "*" significa "incluyendo la cadena vacía". "/" significa "o"

Estos lenguajes también son denominados "recursivamente enumerables"

Las máquinas que los aceptan son las máquinas de Turing (y equivalentes no deterministas)
Other Languages