Preguntas etiquetadas con automata

9
Si

Estoy atrapado resolviendo el siguiente ejercicio: Argumenta que si tiene contexto y es regular, entonces (es decir, el cociente correcto ) no tiene contexto.R L / R = { w ∣ ∃ x ∈ RLLLRRRL / R = { w ∣ ∃ x ∈ RS tw x ∈ L }L/R={w∣∃x∈Rs.twx∈L}L / R = \{ w \mid \exists x \in R \;\text{s.t}\; wx \in L\}...

9
¿Es el no determinismo en una máquina de turing no determinista diferente de la de los autómatas finitos y los autómatas de empuje?

Deje una cadena de entrada como . Luego, si un NFA se encuentra actualmente en el estado r (y ha leído la entrada hasta el alfabeto w i ), antes de leer el siguiente símbolo de entrada, el NFA se divide en dos NFA, uno en el estado r y otro en s , si hay una transición del tipo r ϵ → s . Si hay un...