Considere el siguiente DFA en el que s0 es el estado inicial y s1, s3 son los estados finales. ¿Qué idioma reconoce este DFA? (A) Todas las strings de x e y (B) Todas las strings de x e y que tienen un número par de x y un número par de y o un número impar o x y un número impar de y (C) Todas las strings de x e y que tienen el mismo número de x e y (D) Todas las strings de x e y con un número par de x y un número impar de y o un número impar de x y un número par de y Respuesta: (D) Explicación:
El alfabeto x se movería a S1 y el alfabeto y se movería a S3 desde el estado S0. Por lo tanto, la string más pequeña aceptada por DFA es {x, y}. Otros movimientos posibles de S1 o S3 a los estados de aceptación pueden ser cualquier combinación de xey de longitud uniforme, es decir, cualquiera de {xx, xy, yx, yy} y sus combinaciones. Por lo tanto, el lenguaje aceptado por DFA puede reconocerse como (x+y) + (xx+xy+yx+yy)*, es decir, todas las strings de x e y con longitud impar (número par de x y número impar de y O número par de y y número impar de x).
Método de eliminación de opciones: (opción que tiene al menos un ejemplo que no es aceptado por DFA)
Opción (A): Falso ya que {xx, xy, etc.} no son aceptados por DFA.
Opción (B): Falso como incluso no. de x e incluso no. de y string {xxyy} no es aceptado por DFA.
Opción (C): Falso como string con igual no. de x e igual no. de y {xy} no es aceptado por DFA.
Opción (D): Se aceptan todas las strings con un número par de x y un número impar de y o un número impar de x y un número par de y.
Por lo tanto, la respuesta es la opción (D).
Esta solución es aportada por Yashika Arora
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