Question

Construct finite-state automata that recognize these sets.

\(\begin{array}{l}a){{\bf{0}}^*}{({\bf{10}})^*}\\b){(01 \cup 111)^*}{10^*}(0 \cup 1)\\c){({\bf{001}} \cup {({\bf{11}})^*})^*}\end{array}\)

Short answer

a) Let \({s_0}\) be the start state of the finite-state automata. Since the Kleene closures contain the empty string \(\lambda \), you need to make \({s_0}\) a final state.

b) Let \({s_0}\) be the start state of the finite-state automata.

You first create \({(01)^*}\) by creating a loop: input 0 at state \({s_0}\) moves us to state \({s_1}\) and input 1 at state \({s_1}\) moves us back to state \({s_0}\).

c) Let \({s_0}\) be the start state of the finite-state automata. Since the Kleene closures contain the empty string \(\lambda \), you need to make \({s_0}\) a final state.

Step-by-step solution

Definition 

Kleene closure of A: Set consisting of concatenations of any number of strings from A

\({A^*} = \bigcup\limits_{k = 0}^{ + \infty } {{A^k}} \)

(a) Constructing the finite-state automata 

\({0^*}{(10)^*}\)

Let \({s_0}\) be the start state of the finite-state automata. Since the Kleene closures contain the empty string \(\lambda \), you need to make \({s_0}\) a final state.

You add a loop with input 0 at the state \({s_0}\) to represents the strings \({0^*}\) (such that any string of \(0'\) will be accepted).

Next, you still need to include \({(10)^*}\) in the automata, which are basically blocks of 10. The state \({s_1}\) will represents the 1 in the block, while the state \({s_2}\) represents the 0 in the block. Note that \({s_2}\) needs to be a final state such that it recognizes the strings with the blocks 10 (preceded by possible \(0's\)).

If you are at the starting state \({s_0}\) with input 1, then you will move to the state \({s_1}\) as you have then started the blocks of 10.

Constructing the finite-state automata

If you are at the state \({s_1}\) with input 0, then you will move to the state \({s_2}\) as you have then completed a 10 block. If you are at state \({s_2}\) with input 1, then you move back to state \({s_1}\) as you have then started a new 10 block. However, if the inputs is 1 at \({s_1}\) or 0 when you are at state \({s_2}\), then you will move to state \({s_3}\) which will contain all left-over strings (while you won't leave \({s_3}\) once you get there).

Hence, \({s_0}\) be the start state of the finite-state automata. Since the Kleene closures contain the empty string \(\lambda \), you need to make \({s_0}\) a final state.

(b) Constructing the finite-state automata

\({(01 \cup 111)^*}{10^*}(0 \cup 1)\)

Let \({s_0}\) be the start state of the finite-state automata.

You first create \({(01)^*}\) by creating a loop: input 0 at state \({s_0}\) moves us to state \({s_1}\) and input 1 at state \({s_1}\) moves us back to state \({s_0}\).

You next create \({(111)^*}\) by creating a loop: input 1 at state \({s_0}\) moves us to state \({s_2}\) and input 1 at state \({s_2}\) moves us to state \({s_3}\) and input 1 at state \({s_3}\) moves us back to state \({s_0}\). The combination with the previous part of the automata will then result in \({(01 \cup 111)^*}\)

Constructing the finite-state automata 

Next, the input 1 moves us from state \({s_0}\) to state \({s_4}\), while there is a loop with input 0 at state \({s_4}\) (to represents \(1{0^*}\)).

Finally, you add an arrow with input 0 and input 1 to a final state \({s_5}\). Only strings in \({(01 \cup 111)^*}{10^*}(0 \cup 1)\) will then be accepted by the automata

Hence, \({s_0}\) be the start state of the finite-state automata.

You first create \({(01)^*}\) by creating a loop: input 0 at state \({s_0}\) moves us to state \({s_1}\) and input 1 at state \({s_1}\) moves us back to state \({s_0}\).

(c) Constructing the finite-state automata 

\({({\bf{001}} \cup {({\bf{11}})^*})^*}\)

Let \({s_0}\) be the start state of the finite-state automata. Since the Kleene closures contain the empty string \(\lambda \), you need to make \({s_0}\) a final state.

You first create \({(001)^*}\) by creating a loop: input 0 at state \({s_0}\) moves us to state \({s_1}\) and input 0 at state \({s_1}\) moves us to state \({s_2}\) and input 1 at state \({s_2}\) moves us back to state \({s_0}\)

You next create \({(11)^*}\) by creating a loop: input 1 at state \({s_0}\) moves us to state \({s_2}\) while input 1 at state \({s_2}\) already moves us back to state \({s_0}\). The combination with the previous part of the automata will then result in \({({\bf{001}} \cup {({\bf{11}})^*})^*}\).

Hence, \({s_0}\) be the start state of the finite-state automata. Since the Kleene closures contain the empty string \(\lambda \), you need to make \({s_0}\) a final state.