- S es el símbolo distinguido o axioma
Gramáticas
regulares (Tipo 3)
Generan los lenguajes regulares
(aquellos reconocidos por un autómata finito). Son las gramá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 las producciones son de la forma
(en el lado derecho de las
producciones el símbolo no terminal aparece a la derecha del símbolo
terminal)
- Lineales a izquierda, si
todas las producciones son de la forma
(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 ,
si el lenguaje que se quiere generar contiene la cadena vacía.
Algoritmo
para obtener la gramática regular desde el autómata finito
Existe un algoritmo que
permite obtener una gramática regular que genera un lenguaje regular
dado a partir del autómata finito que reconoce ese lenguaje. Los
pasos a seguir son los siguientes:
1) Asociar al estado inicial
el símbolo distinguido S.
2) Asociar a cada estado
del autómata (menos el estado inicial) un símbolo no terminal.
Si al estado inicial llega algún arco asociar también un
símbolo no terminal (además del símbolo distinguido).
3) Para cada transición
definida ,
agregar al conjunto de producciones, la producción A -> aB, siendo
A y B los símbolos no terminales asociados a ei y ej respectivamente.
Si ej es un estado final, agregar también la producción A
-> a. Si ej es el estado inicial (tiene dos símbolos asociados,
el distinguido y un no terminal), utilizar el símbolo no terminal
(de esta manera se evita que el símbolo distinguido aparezca a la
derecha de una producción).
4) Si el estado inicial
es también final agregar la producción .