Automatas

Gramáticas
Las gramáticas formales definen un lenguaje describiendo cómo se pueden generar las cadenas del
lenguaje.
Una gramática formal es una cuadrupla G = (N, T, P, S) donde
- N es unconjunto finito de símbolos no terminales
- T es un conjunto finito de símbolos terminales N
T = 
- P es un conjunto finito de producciones
Cada producción de P tiene la forma
  ,  = A y  = , ,  (N
T)* y A es S ó A N
- S es el símbolo distinguido o axioma S  (N
T)
Restringiendo los formatos de producciones permitidas en una gramática, se pueden especificar
cuatro tiposde gramáticas (tipo 0, 1, 2 y 3) y sus correspondientes clases de lenguajes.
Gramáticas regulares (Tipo 3)
Generan los lenguajes regulares (aquellos reconocidos por un autómata finito). Son lasgramáticas
más restrictivas. El lado derecho de una producción debe contener un símbolo terminal y, como
máximo, un símbolo no terminal. Estas gramáticas pueden ser:
- Lineales a derecha, si todas lasproducciones son de la forma
A N
{S}
A  aB ó A  a B N
a T
(en el lado derecho de las producciones el símbolo no terminal aparece a la derecha del símbolo
terminal)
- Lineales aizquierda, si todas las producciones son de la forma
A N
{S}
A  Ba ó A  a B N
a T
(en el lado derecho de las producciones el símbolo no terminal aparece a la izquierda del símbolo
terminal)En ambos casos, se puede incluir la producción S  , si el lenguaje que se quiere generar contiene
la cadena vacía.
Por ejemplo las siguientes gramáticas G1 y G2, son gramáticas regulareslineales a derecha y lineales
a izquierda respectivamente, que generan el lenguaje L = {a2n / n
0}
G1 = ({A, B}, {a}, P1, S1) G2 = ({C, D}, {a}, P2, S2)
donde P1 es el cjto. donde P2 es el cjto.
S1  S2  
S1  aA S2  Ca
A  aB C  Da
A  a C  a
B  aA D  Ca
CIENCIAS DE LA COMPUTACION I 2008
Algoritmo para obtener la gramática regular desde el autómata finito
Existe un algoritmo que...