Decidability of the language of all deterministic LBA where all states are reachable
-
06-11-2019 - |
Pergunta
I have a exam task with 3 parts. (b) is no problem. I got a solution for (a) but the way (c) is asked makes me wonder if I even understood (a)
(a) L := { < A > | A is a DFSA, where all states are reachable }. Is L decidable? Why or why not?
(b) M is a DLBA and k is the input length. There exists a function g(M,k) which returns the maximum number of steps a DLBA can possibly do, which halts on an input the size of k. Why?
(c) L' := { < M > | M is a DLBA, where all states are reachable }. Show that L' is semi-decidable. Use g(M,k) from (b)
My solution:
(b) Limited amount of configurations. I get that.
For example how I understand (a): L is a language and every word of L is the encoding of a FSA. But only FSAs where every state can somehow be reached from the starting state or is the starting state.
So is it decidable?
My answer: Yes, for any word w you could check if its a valid FSA-encoding, if not: reject, if it is: Construct a FSA from this encoding and check if you can reach all states like this:
Mark the starting state;
Repeat until no new marked states:
Mark all states you can reach from the marked states.
Check if all states are marked.
Reject or Accept
My Question:
Is (c) just semi-decidable and how do I use g(M,k) to show this? Because I would think I could solve (c) exactly like (a) and show that it is decidable (which would mean it is also semi-decidable)
Edit: Hi, if you give me a downvote I would appreciate a comment on how to improve my questioning. I know it is a long post but I just try to lay out how I understand questions like this to be solved so you can correct me if I have key misunderstandings. I now reduced the amount of questions I asked and the length of my post.
Nenhuma solução correta