Given the finite automaton:

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!

  • 1
    $\begingroup$ Looks correct to me. $\endgroup$ – Q the Platypus Aug 28 '18 at 0:17
  • $\begingroup$ @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)? $\endgroup$ – manooooh Aug 28 '18 at 0:19
  • 1
    $\begingroup$ Dash is better IMHO $\endgroup$ – 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.
  • $\begingroup$ Thanks! Can I ask you what other regular expressions would be since we have infinite of them? $\endgroup$ – manooooh Aug 28 '18 at 15:07
  • 1
    $\begingroup$ 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. $\endgroup$ – J.-E. Pin Aug 28 '18 at 15:25
  • $\begingroup$ ... where $r=0^\ast11{\left(1+01\right)}^\ast$? $\endgroup$ – manooooh Aug 28 '18 at 15:28
  • $\begingroup$ It could be any regular expression $r$. $\endgroup$ – J.-E. Pin Aug 28 '18 at 15:29
  • 1
    $\begingroup$ 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)^*$. $\endgroup$ – J.-E. Pin Aug 28 '18 at 15:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.