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
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:
Escribe un comentario o lo que quieras sobre Gramática (autómata) (directo, no tienes que registrarte)
Comentarios
(de más nuevos a más antiguos)