PUERTA | Cuestionario para Sudo GATE 2021 | Pregunta 49

Considere las siguientes gramáticas G1 y G2 respectivamente.

Gramática – G1:

A1 → A2A3
A2 → A3A1 | b
A3 → A1A1 | a

Gramática – G2:

S → AA | 0
A → SS | 1

Considere las siguientes declaraciones con respecto a las gramáticas anteriores:

(I): Esta gramática no se deja recursiva y equivalente a la gramática – G1:

A1 → A2A3
A2 →  A3A1 | b
A3 → a | bA3A1 | aK | bA3A1K 
k → A1A3A1 | A1A3A1K

(II): Esta gramática no se deja recursiva y equivalente a la gramática – G2:

S → A A | 0
A → 0S | 1 | 0SK | 1K
K → AS | ASK

Nota: esta pregunta es de selección múltiple (MSQ).
(A) La afirmación (I) es correcta
(B) La afirmación (II) es correcta
(C) La afirmación (I) no es correcta
(D) La afirmación (II) no es correcta

Respuesta: (A) (B)
Explicación: Gramática – G1:

A1 → A2A3
A2 → A3A1 | b
A3 → A1A1 | a

Reemplace A3 → A1 A1 por A3 → A2A3A1 y luego reemplácelo por A3 → A3A1A3A1 y A3 → bA3A1.

Eliminando la recursión directa a la izquierda en lo anterior, se obtiene:

A3 → a | bA3A1 | aK | b A3A1K 
k → A1 A3 A1 | A1 A3 A1K

La gramática resultante es entonces:

A1 → A2A3
A2 →  A3A1 | b
A3 → a | bA3A1 | aK | bA3A1K 
k → A1A3A1 | A1A3A1K

Gramática – G2:

S → AA | 0
A → SS | 1

Considerando el ordenamiento S, A, obtenemos:

S → AA | 0
A → AAS | 0S | 1

y eliminando la recursión izquierda inmediata, obtenemos

S → A A | 0
A → 0S | 1 | 0SK | 1K
K → AS | ASK

Entonces, ambas afirmaciones (I) y (II) son correctas.
Cuestionario de esta pregunta
Comente a continuación si encuentra algo incorrecto en la publicación anterior