¿Cuál de los siguientes conjuntos puede ser reconocido por un autómata determinista de estado finito?
(A) El número 1, 2, 4, 8……,2^n,………. escrito en binario.
(B) El número 1, 2, 4,….., 2^n,………. escrito en unario.
(C) El conjunto de strings binarias en las que el número de ceros es el mismo que el número de unos.
(D) El conjunto {1, 101, 11011, 1110111,…….}
Respuesta: (A)
Explicación:Si hay un idioma infinito y para ese idioma si no existe ningún patrón, entonces podemos decir con seguridad que el idioma dado no es regular, pero si existe un patrón para ese idioma, entonces puede ser o no un lenguaje regular y para garantizar un el idioma dado es regular, si podemos dibujar DFA para ese idioma, seguramente será regular, de lo contrario no regular,
Por lo tanto, la opción (A) es un lenguaje normal, ya que puede escribirse en binario, es decir,
L = {1, 10, 100, 1000, 10000, …}
La expresión regular es (10*), ya que para esta expresión podemos dibujar DFA.
Entonces, la opción (A) es correcta.
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