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

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!

• Looks correct to me. – Q the Platypus Aug 28 '18 at 0:17
• @QthePlatypus thanks! A little question: $\delta$ is a function. In the table transition is it correct to write $(q_1,0)=\;-$ or it is better to write $(q_1,0)=\varnothing$ (or with another symbol, you know what I mean)? – manooooh Aug 28 '18 at 0:19
• Dash is better IMHO – Q the Platypus Aug 28 '18 at 1:26

"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.
• Thanks! Can I ask you what other regular expressions would be since we have infinite of them? – manooooh Aug 28 '18 at 15:07
• For instance, if $r$ is a regular expression, then $r^*$, $1+ rr^*$, $1 + r + rrr^*$, etc. represent the same language. And if $\varepsilon$ is the empty word, then $r$, $r\varepsilon$, $r\varepsilon\varepsilon$, etc. represent the same language. – J.-E. Pin Aug 28 '18 at 15:25
• ... where $r=0^\ast11{\left(1+01\right)}^\ast$? – manooooh Aug 28 '18 at 15:28
• It could be any regular expression $r$. – J.-E. Pin Aug 28 '18 at 15:29
• I am just saying that my comment holds for any regular expression. Now, if you want to apply it to your case, you would get for instance the following equivalent regular expressions: $0^*11(1+01)^*$, $0^*11(1+01)(\varepsilon + (1+01)(1+01)^*)$, $0^*11(\varepsilon + (1+01) + (1+01) (1+01)(1+01)^*)$, $\varepsilon^n 0^*11(1+01)^*$. – J.-E. Pin Aug 28 '18 at 15:35