Lenguajes formales y automatas

GRAMATICAS REGULARES
USN
LETICIA MENDOZA VELEZ
09IRT8702140185 INGENIERÍA EN REDES Y TELECOMUNICACIONES

GRAMATICAS REGULARES
Para entender el tema deGramáticas regulares primero explicaré que es una

GRAMATICA.

Las Gramáticas formales definen un lenguaje describiendo cómo se pueden generar las cadenas del lenguaje.
Una Gramática formal es una cuádrupla G= (N, T, P, S) donde N es un conjunto de símbolos no terminales, T es un conjunto de símbolos terminales, P es un conjunto finito de producciones, S es el símbolo distinguido axioma S (N T).GRAMATICAS REGULARES

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 ycomo máximo un símbolo no terminal.

Estas Gramáticas pueden ser:
* Lineales a la izquierda sí todas las producciones son de la forma:

A
N
{S}
A
aB ó A
a B
N
a
A
N
{S}
A
aB óA
a B
N
a

A
N
{S}
A
aB ó A
a B
N
a

Debemos ser observadores y notar que en el lado derecho de las producciones el símbolo no terminal aparece a la izquierda del símboloterminal.

* Lineales a la derecha sí todas las producciones son de la forma:

A N {S}
A Ba ó A a BN
A T

Existe un algoritmo para obtener la gramáticaregular desde el autómata finito, 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 elsímbolo distinguido S.
2) Asociar a cada estado del autómata (menos el estado inicial) un símbolo no terminal (además del símbolo distinguido). No asociar símbolo no terminal a aquellos estadosfinales de los que no salen arcos.
3) Sí el estado final es S

Expresiones Regulares

Sea Σ un alfabeto. Una expresión regular α sobre Σ se define con las siguientes reglas (inductivas):

1. a) ∅...