Si una máquina de estados finitos se define formalmente con un conjunto de estados $\{q_0, q_1, q_2\}$ donde $q_0$ es el estado inicial, ¿es una máquina válida si no hay camino desde $q_0$ a $q_1$ y ninguna ruta de $q_2$ a $q_1$ ? En otras palabras, no hay manera de llegar a $q_1$ en absoluto, pero sigue considerándose parte de la máquina.
Además, ¿y si $q_1$ es el único estado de aceptación de la máquina? ¿Sigue siendo una máquina de estados finitos válida?
No hay teórico razón para prohibirlo. Por otra parte, es posible que desee hacer la definición de tal manera que esta condición se cumpla - pero entonces siempre hay que demostrar para cada construcción (por ejemplo, la combinación de "subrutinas" en una máquina más grande) que la condición no se viola de repente. Por tanto, desde un punto de vista teórico, es más sencillo permitir estos estados redundantes.
Si $q_1$ es el único estado de aceptación, la máquina es equivalente a una máquina sin ningún estado de aceptación; lo cual no es problemático, sólo dice que la máquina acepta precisamente el lenguaje vacío.
Tal vez escriba una máquina que alcanza un estado de aceptación sólo cuando se introduce un número par $>2$ que no se puede escribir como suma de dos primos. ¿Estaría de acuerdo en que tal máquina es ¿Una máquina? ¿O me exigirías que demostrara que la conjetura de Goldbach es falsa antes de considerarla una máquina?
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
