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;
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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.