Considere los siguientes idiomas:
L1 = {sw | w ∈ {a, b}* }
norte norte _
L3 = {un metro segundo norte do norte | m, n≥ 0}
¿Cuál de las siguientes afirmaciones es/son FALSA?
(A)
L 1 no está libre de contexto, pero L 2 y L 3 son deterministas libres de contexto.
(B)
Ni L 1 ni L 2 están libres de contexto.
(C)
L 2 , L 3 y L 2 ∩ L 3 son independientes del contexto.
(D)
Ni L 1 ni su complemento están libres de contexto.
Respuesta: (B) (C) (D)
Explicación:
Tanto L2 como L3 son DCFL ya que Push y Pops son obvios (en L2, comenzamos empujando a en la pila y comenzamos a sacar a tan pronto como comenzamos a obtener b, y en L3, primero pasamos a través de a y luego empujamos b) y comenzar a hacer estallar b tan pronto como comencemos a obtener c).
L1 requiere que realicemos una comparación de dos strings en forma de reenvío, lo que no es posible con una PDA, por lo que L1 no es CFL. Esto hace que la opción A sea verdadera.
L2 La intersección L3 es un m b n c n que es un CSL muy conocido. Esto hace que la opción C sea incorrecta. Dado que L2 no tiene contexto, la opción B también es incorrecta.
La opción D es incorrecta ya que el Complemento de WW es una LFC,
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