PUERTA | PUERTA CS 2018 | Pregunta 40

Dado un lenguaje L, defina L ⁱ de la siguiente manera:

L ⁰ = {ε}
L ⁱ = L ^i-1 ∙L para todo i>0

El orden de una lengua L se define como el k más pequeño tal que L ^k =L ^k+1 . Considere el lenguaje L ₁ (sobre el alfabeto 0) aceptado por el siguiente autómata.

El orden de L ₁ es ______.

Nota: esta fue una pregunta de tipo numérico.

(A) 2
(B) 3
(C) 1
(D) Ninguno

Respuesta: (A)
Explicación: L1 = ε + 0(00)*
L ⁰ = ε
L ¹ = ε . (ε + 0(00)*)
    = ε + 0(00)* = L1

L ² = L ¹ . L1 = L1 . L1
    = (ε + 0(00)*) (ε + 0(00)*)
    = ε + 0(00)* + 0(00)* + 0(00)* . 0(00)*
    = ε + 0(00)* + 0(00)* 0(00)* = 0*

El autómata dado contiene epsilon y un número par de ceros y un número impar de ceros.

L ³ = L ² . L1
    = {0*} . {ε + 0(00)*} = 0* 0(00)* = 0*
Entonces, L ² = L ³ = L ²⁺¹
Entonces, el valor más pequeño de k = 2
Cuestionario de esta pregunta