Gramáticas formales Flashcards
¿Qué es una gramática formal?
Es una estructura que genera todas las palabras de un lenguaje formal
Además, es un conjunto de producciones que genera determinado lenguaje formal, que es único.
¿Qué es una PRODUCCIÓN?
Una producción es una regla de reescritura que se aplica para obtener las palabras de un lenguaje formal.
Ejemplo :
Sea L={ab,ac}, se puede escribir como :
S → ab
S → ac
¿Cómo se construyen las producciones?
Con 3 tipos de símbolos.
- Símbolos productores : S,T,R,etc.
- Símbolos que forman palabras del lenguaje, como : a,b,c.
- Metasímbolos : Ejemplo : →
¿Cómo se lee una producción?
El lado izquierdo significa : “PRODUCE”.
El lado derecho significa : “EQUIVALE A”.
¿Qué es la producción-épsilon?
Es aquella producción que genera la palabra vacía.
Es decir : S → épsilon.
¿Qué es un NOTERMINAL?
Es un vocabulario finito de productores.
Se los representa con la letra mayúscula.
¿Qué es un TERMINAL?
Son los caracteres sobre el cual se construyen las palabras del Lenguaje Formal.
Se los representa con letras minúsculas y dígitos.
¿Qué es un axioma?
Es un NOTERMINAL a partir del cual deben comenzar a aplicarse las producciones que generan las palabras de un LF.
¿Un noterminal puede tener más de una producción?
Sí, y se lo representa con el carácter : |
Ejemplo : S –> a|b (Se produce a A y S produce a B).
