Given a finite automaton determine if it is deterministic and indicate regular expression

Question

Given the finite automaton:

1. Make the transition table and indicate if it is deterministic or not.
2. Indicate which of the following regular expressions corresponds to the language recognized by the automaton:
   • $0^\ast11\left(1^\ast+01\right)1^\ast$
   • $0^\ast11{\left(1+01\right)}^\ast$
   • $0^\ast11{\left(1^\ast01\right)}^\ast$

---

1. The state machine $M=(Q,V,\delta,q_0,F)$ where $Q=\{q_0,q_1,q_2\}$, $V=\{0,1\}$, $\delta:Q\times V\to Q$ and $F=\{q_2\}$ has the following table transition:
   $$\begin{array}{c|ccc}
   \delta&0&1\\\hline q_0&q_0&q_1\\q_1&-&q_2\\q_2&q_1&q_2
   \end{array}$$ This finite automaton is deterministic because it has at most one change of state for each letter of the alphabet.

2. Recall that each language has a single regular expression. Since we can go through the $q_2$ loop or go back and forth from $q_1$ to $q_2$ then the correct regular expression is $$0^\ast11{\left(1+01\right)}^\ast\text.$$

Is that correct?

Thank you!

Answer 1

"2. Recall that each language has a single regular expression."

This is very far from being true! A given regular language can actually have infinitely many regular expressions representing it.

It is indeed true that $0^*11(1+01)^*$ is a regular expression representing the language, but you did not prove that the two other expressions are not correct. Her are the missing arguments:

1. All words of $0^*11(1^*+01)1^*$ are accepted by the automaton but some words are missing, for instance $110101$.
2. Similarly, all words of $0^*11(1^*01)^*$ are accepted by the automaton but the word $111$ is missing.