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:
donde Según Padilla las gramáticas se clasifican de acuerdo a las reglas de sustitución y nunca se pasa autómatas 2: “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" “α puede ser reemplazado por β si la longitud de α es menor o igual a la longitud de β, siendo α un símbolo Terminal o una cadena vacía z1, seguido de un símbolo No Terminal X, seguido de otro símbolo Terminal o una cadena vacía z2.
En el caso de β, z1 debe ser el mismo símbolo z1 de α seguido de un símbolo No Terminal o Terminal sin ser la cadena vacía, seguido del símbolo z2.” “x puede ser reemplazado por y si x pertenece a los símbolos No Terminales e y es un Terminal o No Terminal, incluyendo la cadena vacía.” Máquinas que los pueden leer: También llamada "De contexto regular" “α puede ser reemplazado por β si α pertenece a los símbolos No Terminales y β es uno de estos 3: