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
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA