# Decidability of the language of all deterministic LBA where all states are reachable

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.

After days of constantly refreshing this page in hope for an answer today I woke up and my very first thought might be it.

If all states are reachable and it is deterministic this means there has to be a set of inputs where every state will once be reached.

semi-decidable Algorithm:

Validate if DLBA-Encoding and reject if not;     # returns 'no' on bogus
k = 0;
Repeat until every state has been at least once been reached {
For every possible input w for the DLBA of the length of k {
Simulate DLBA with w for g(M,k) steps while keeping record of the reached states;
}
k++;
}
return 'yes'


It will accept if all states are reachable

It will reject if not a valid DLBA-Encoding

It will run forever if valid DLBA but not all states are reachable

I figured out, that DLBAs can have states where there are a series of transitions leading from the starting state to those but they still can never be reached. So just looking at transistions isn't enough