Recursividad de un lenguaje regular

Recursividad

En las Reglas de la Recursividad existen 2 tipos de recursividad:

a) Recursividad a la izquierda (Lo que debemos evitar)
b) Recursividad a la derecha

->
->
->Recursividad a la izquierda
->
->

-> α i | β i Expresión Regular

-> β i | β i Dejó de ser Recursiva si agregamos una sentencia Auxiliar
-> α i | α i

Levantar Recursividad
->α 1 | α 2 | α 3 | β 1 | β 2 | β 3
Donde β α є (N U T)*

1) Identificar los valores de αi
2) Identificar los valores de β i
3) Agregar una variable auxiliar o agregar una Sentenciano terminar auxiliar y aplicar el sgte método Algorítmico:

-> β 1 | β 2 | β 3 | β 1 | β 2 | β 3
-> α 1 | α 2 | α 3 | α 1 | α 2 | α 3

1. Se tienen las sgtes reglas.
R1 : -> ab
R2: -> bc
R3 : -> ac
R4 : -> cd | w

Solución:
-> ab | bc | ac | cd | w

α 1 α 2 α 3 β 1 β 2


-> cd | w | cd | w
-> ab | bc | ac | ab | bc | ac

2. Se tienen las sgtesreglas:
R1 : -> | | b
R2: -> cw | a | ab

-> | | b | cw | a | ab

α 1 α 2 α 3
-> b | cw | ab | b | cw | ab
-> | | a | | |a
Forma Normal de Greibach (FNG)

Lasreglas de Producción ‘P’ de la gramática de un lenguaje tienen la parte derecha como símbolo un “terminal” seguida de simboles que pertenecen a ambos vocabularios.

-> a α

Parte derecha terminalΑ є (N U T)*

Convertir FNG:

1. Deben de estar todas las reglas en las Forma FNC. (Formal normal de Chosmky: “debe haber dos no terminales o un terminal”).
2. Se hace un análisis de losindicen de reglas.
->
i < j cumple
i > j No cumple, se debe levantar la recursividad
3. Levantar la recursividad de aquellas reglas en la que los índices i > j
4. La variable transformada sereemplaza en las otras reglas.

Se tienen las siguientes reglas:

R1: ->
R2: -> | a
R3: -> | b
Solución:

1. Para las tres primeras reglas, se cumple con la forma FNC
2....