Conversão entre ER e GR

Conversão de ER para GR

É suficiente obter a GR para as ER primitivas e aplicar as operações regulares sobre a GR

A GR para a ER a, qualquer que seja o a, é dada por:

• S -> a

Vamos exemplificar com a ER e = (a jb)*a

1. Primeiro definimos regras para os símbolos terminais:

   1. S1 -> a

   2. S2 -> b

2. Para reconhecer (a | b) temos (S = S3):

   1. S3 -> S1 | S2

   2. S1 -> a

   3. S2 -> b

3. Para reconhecer (a | b)* temos (S = S3):

   1. 
4. Por fim para reconhecer a ER (a | b)*a temos (S = S4):

   1. 

Conversão de GR para ER

Seja G1 = (T1;N1;S1;P1) uma gramática regular qualquer.

Uma ER que represente a mesma linguagem que a gramática G pode ser obtida por um processo de transformação de equivalência:

1. Converte-se a gramática G no conjunto de triplos seguinte:

   1. 
2. Removem-se, por transformações de equivalência, um a um, todos os símbolos de N, até se obter um único triplo da forma:

   1. 

Remoção dos símbolos de N:

Vamos exemplificar com a seguinte GR: