Hola.
Por lo que entiendo, el asterisco * representa "repetición del caracter/estado anterior".
Más precisamente, el * quiere decir:
Aceptar como válida cualquier cadena que comience con una cantidad finita de "1"s y termine con exactamente un solo "0".
Entonces, las cadenas válidas serían estas: 10, 110, 1110, 11110, 11111111110.
Según el gráfico de tu amigo, el árbol empieza con un nodo inicial \( S_0 \), que imagino que representa la cadena vacía (o sea, "nada aún"). Luego, las flechas hacia la derecha indican que se va hacia el nodo \( S_1 \), que contiene el caracter "1". De allí hay dos flechas posibles: o bien "el asunto termina ahí y se avanza hacia \( S_2 \)", o bien "se vuelve a repetir \( S_1 \)".
Una vez que se ha repetido el nodo \( S_1 \), vuelven a aparecer de nuevo las dos opciones: o bien vamos hacia \( S_2 \), o bien repetimos \( S_1 \).
Al llegar a \( S_2 \), vemos que hay un "0", y que ahí termina todo.
La "S" imagino que significa "State", o sea: "estado", así que \( S_1 \) será el estado en el momento \( t = 1 \). \( S_0 \) sería el estado inicial, y \( S_2 \) es el último estado.
Adentro del último estado tu amigo dibujó un círculo.
Interpreto que eso indica que el proceso terminó, o que se llegó al estado final.
Sería, me parece, una señal de "fin de trabajo" para la máquina.
Lo que muestra el gráfico es bastante claro de descifrar.
La máquina comienza en un estado inicial \( S_0 \).
Luego pasa al estado \( S_1 \), en que hay dos caminos posibles: obtener un 1, con lo cual vuelve al estado \( S_1 \), o bien obtener un 0, con lo cual cambia al estado \( S_2 \).
El 1 aparece escrito sobre la flecha circular que vuelve sobre \( S_1 \).
El 0 aparece sobre la flecha que va del estado \( S_1 \) al \( S_2 \).
Esto me da a entender que la máquina cambia su estado, según qué entrada le hayas pasado. (Es lo que se llama, función de transición).
Desde un estado dado, y con una entrada específica, se pasa a un estado determinado.
Si en el estado \( S_1 \) le pasaste un 1, la máquina vuelve a ese "estado".
Si no, si le pasaste un 0, se mueve al estado siguiente.
Ahora bien.
El autómata arranca en el estado \( S_0 \), y lee uno a uno los caracteres de la cadena.
Esto lo hace hasta que la cadena termina.
Si la cadena terminó de ser leída, y la máquina quedó en el/un estado final (o de aceptación), es que la cadena era correcta (pertenece a la expresión regular analizada).
Si no, no .
----------
En cuanto al ejercicio 9, se me habían ocurrido 3 opciones, de las cuales descarto las primeras dos:
(a) (10)*: La descarto porque no se puede generar 1.
(b) 1(01)*: La descarto porque no permite generar 10.
(c) 1(0(10)*|(01)*): Permite 1, 10, 101, 1010, 10101, etc.
Si interpreté bien el enunciado, es la opción (c).
Saludos.
