edited by
14,895 views
1 votes
1 votes

Give state diagrams of $\text{NFA's}$ with the specified number of states recognizing each of the following languages. In all parts, the alphabet is $\{0,1\}.$

  1. $\text{The language \{w| w ends with 00\} with three states}$
  2. $\text{\{w| w contains the substring 0101 (i.e., w = x0101y for some x and y)\} with five states}$
  3. $\text{\{w| w contains an even number of 0s, or contains exactly two 1s\} with six states}$ 
  4. $\text{The language \{0\} with two states}$
  5. $\text{The language $0^{*}1^{*}0^{+}$ with three states}$
  6. $\text{The language $1^{*}(001^{+})^{*}$ with three states}$
  7. $\text{The language}$ $\{\epsilon\}$ $\text{with one state}$
  8. $\text{The language 0* with one state}$ 
edited by

1 Answer

1 votes
1 votes

a. The language {w| w ends with 00} with three states

b. {w| w contains the substring 0101 (i.e., w = x0101y for some x and y)} with five states

d. The language {0} with two states

e. The language 0*1*0+ with three states

f. The language 1*(001+)* with three states

g. The language {ϵ} with one state

h. The language 0* with one state

edited by

Related questions

0 votes
0 votes
1 answer
1
admin asked Apr 21, 2019
4,535 views
Use the construction in the proof of $\text{Theorem 1.45}$ to give the state diagrams of $\text{NFA’s}$ recognizing the union of the languages described in$L_{1}=\text{...
0 votes
0 votes
0 answers
4
admin asked Apr 21, 2019
773 views
The formal description of a $\text{DFA}$ $\text{M}$ is $({q1, q2, q3, q4, q5}, {u, d}, δ, q3, {q3}),$ where $\text{δ}$ is given by the following table. Give the state ...