GRAMATICAS

GRAMATICAS

DEFINICION DE GRAMATICAS:

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

TIPOS DE GRAMATICAS:

• REGULARES:

También llamada "De contexto regular"
“α puede ser reemplazado por β si α pertenece a los símbolos No Terminales y β es uno de estos 3:

• Un símbolo Terminal no nulo seguido de un No Terminal.
• Un símbolo No Terminal seguido de un símbolo Terminal no nulo.
• Un símbolo Terminal pudiendo ser la cadena vacía.”

Máquinas que los aceptan: autómata finito, determinista o no determinista.

• LIBRES DE CONTEXTO

“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:

Máquinas que los aceptan: Autómata a Pila (Pushdown Automaton).

A CONTINUACION UN VIDEO..................