PUERTA | GATE-CS-2017 (Conjunto 1) | Pregunta 42

Considere la siguiente gramática sobre el alfabeto {a,b,c} dado a continuación, S y T no son terminales.

G1: S-->aSb|T
T--> cT|∈

G2: S-->bSa|T
T--> cT|∈

El lenguaje L1(G1) ∩ L2(G2).
(A) Finito
(B) No finito pero regular
(C) Libre de contexto pero no regular
(D) Recursivo pero no libre de contexto

Respuesta: (B)
Explicación: El lenguaje generado por la gramática G1 es a ⁿ c*b ⁿ donde n>=0

El lenguaje generado por la gramática G2 es b ⁿ c*a ⁿ donde n>=0

La intersección de dos idiomas será c* (poniendo n=0 en ambos idiomas)

Sabemos que c* es un lenguaje regular e infinito, por lo que la opción b es correcta.

Solución alternativa
$G1: \ S\rightarrow \ aSb \ |T, \\ T\rightarrow cT|\epsilon \\ L(G1)=\left \{ a^{m}c^{n}b^{m} \ | \ m,n \geq 0 \right \} \\ G2: \ S\rightarrow bSa \ |T \\ T\rightarrow cT|\epsilon \\ L(G2)=\left \{ b^{m}c^{n}a^{m} \ | \ m,n \geq 0 \right \} \\ Both \ L(G1) \ and \ L(G2) \ are \ CFL. \\ L(G1) \ \cap \ L(G2) = c^{*} \\ Hence, \ regular \ but \ not \ finite.$

Esta solución es aportada por Sumouli Chaudhary.

Cuestionario de esta pregunta

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

Deja una respuesta Cancelar la respuesta