Décidabilité de la langue de tous les LBA déterministes où tous les États sont accessibles

Question

J'ai une tâche d'examen avec 3 parties. (b) n'est pas un problème. J'ai une solution pour (a) mais le chemin (c) est demandé me fait me demander si j'ai même compris (a)

(un) L: = {<a> | A est un DFSA, où tous les États sont accessibles}. L est-il décidé? Pourquoi ou pourquoi pas?

(b) M est un DLBA et K est la longueur d'entrée. Il existe une fonction g (m, k) qui renvoie le nombre maximum d'étapes qu'un DLBA peut éventuellement faire, ce qui s'arrête sur une entrée de la taille de K. Pourquoi?

(c) L ': = {<m> | M est un DLBA, où tous les États sont accessibles}. Montrez que l 'est semi-décisif. Utilisez g (m, k) de (b)

---

Ma solution:

(b) quantité limitée de configurations. Je comprends ça.

Par exemple, comment je comprends (a): l est une langue et chaque mot de L est le codage d'une FSA. Mais seuls les FSA où chaque État peut en quelque sorte être atteint de l'état de départ ou est l'état de départ.

Alors, est-ce décidable?

Ma réponse: Oui, pour n'importe quel mot w, vous pourriez vérifier si c'est un codage FSA valide, sinon: rejetez, si c'est le cas: construisez une FSA à partir de cet encodage et vérifiez si vous pouvez atteindre tous les états comme ceci:

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

Ma question:

Est (c) juste semi-décidable et comment utiliser g (m, k) pour le montrer? Parce que je pense que je pourrais résoudre (c) exactement comme (a) et montrer qu'il est décidable (ce qui signifierait qu'il est également semi-décidable)

Éditer: Salut, si vous me donnez un vote Down, j'apprécierais un commentaire sur la façon d'améliorer mes questions. Je sais que c'est un long post, mais j'essaie simplement de définir comment je comprends que des questions comme celle-ci soient résolues afin que vous puissiez me corriger si j'ai des malentendus clés. J'ai maintenant réduit le nombre de questions que j'ai posées et la durée de mon message.