Si s es una string sobre (0 + 1)*, entonces sea n 0 (s) el número de 0 en s y n 1 (s) el número de 1 en s. ¿Cuál de los siguientes lenguajes no es regular?
7″ />
(A) A
(B) B
(C) C
(D) D
Respuesta: (C)
Explicación: Los idiomas en la opción (A) y (D) son finitos, por lo que se eliminan ambas opciones.
Para la opción A:
Hay un número finito. de números primos de 3 dígitos. Existe un FA para cada conjunto finito. Por lo tanto, FA es posible.
Para la opción D:
los restos posibles para 7 son 0 a 6, y para 5 son 0 a 4. Usando 35 estados, se puede hacer FA.
Para la opción B:
podemos tener 6 estados (incluido 1 estado de rechazo)
estado 1: la diferencia es 0
estado 2: la diferencia es 1 (más 1)
estado 3: la diferencia es 1 (más 0)
estado 4: la diferencia es 2 (más 1 ) )
estado 5: la diferencia es 2 (más 0)
estado 6: estado de rechazo por diferencia >= 3
Supongamos que la string es 000101
Escanear 0 -> estado 3
Escanear 0 -> estado 5
Escanear 0 -> rechazar (ya que la diferencia es 3 ahora)
De manera similar, si intentamos con la string: 010100, esto será aceptado.
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