Let L be a decidable language. Show that the language L′ is also decidable, where
L′ = {w | w · w^r ∈ L},
and w · w^r is the concatenation of the word w with its inverse.
Can anyone help me with this?
(2 votes)
Loading...You can simply make multiple requests instead of grouping something.
Hi, I'm currently programming something small and need to clear the console. Does anyone know how to do this? (in Java)
Hi, I wanted to know if you know of any jobs similar to office clerk? For training.
I'd like to know what's wrong with the following code. I want to program a kind of bank account. The problem is that the else condition doesn't work for me. So, if I want to make a deposit instead of a withdrawal, only the withdrawal is recognized, and the corresponding amount is deducted. Here is…
Hello everyone, I'm currently training to become an IT specialist for systems integration and am wondering how my salary might develop in this field after about 10 years of professional experience. Does anyone here have experience or information on this that could help me, as a prospective IT specialist? LG Tobi
What if you inverted the TM itself and 'merged' it with the original one?
Thus, the final state of the original TM is also the starting state of the inverted TM. The original starting state is then accepted by the inverted TM. The transitions are reversed, as is the tape direction.
Consider whether such a construction is feasible.
(This is just a spontaneous idea, maybe there is another way)
PS: The tape direction should not be inverted, of course, I shot too quickly….