Considere los siguientes idiomas.
L 1 = {una pag | p es un número primo}
L 2 = {a n b m c 2m | norte >= 0, metro >= 0}
L 3 = {un norte segundo norte C 2n | norte >= 0}
L 4 = {un norte segundo norte | norte >= 1}
Cuales de las siguientes son correctas ?
I. L 1 está libre de contexto pero no es regular.
II. L 2 no está libre de contexto.
tercero L 3 no está libre de contexto sino que es recursivo.
IV. L 4 está libre de contexto determinista.
(A) I, II y IV solamente
(B) II y III solamente
(C) I y IV solamente
(D) III y IV solamente
Respuesta: (D)
Explicación: L1 no es un lenguaje regular ni libre de contexto, sino sensible al contexto.
L2 es independiente del contexto, presione cualquier número de a y luego, para cada b, extraiga dos c hasta que todas las b hayan terminado y esto se puede hacer usando solo una pila.
L3 no está libre de contexto porque no estamos seguros de cuándo abrir b y presionar a, porque es una comparación entre tres terminales consecutivos.
Claramente, L4 está libre de contexto determinista porque estamos seguros de empujar a a la pila primero y al ver b estamos seguros de hacer estallar a.
Las afirmaciones III y IV son correctas, la opción (D) es verdadera.
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