Sofia University State Diagrams of DFAs Recognizing the Languages Questions

Diagrams may be drawn by hand or JFLAP.

Give the state diagrams of DFAs recognizing the following languages over ? = {0,1}:

L?

L?

{?, 1, 001}

Give the state diagrams of DFAs recognizing the following languages over ? = {0,1}:

{w : w contains exactly two 1’s}

{w : |w| ? 5}

Give the state diagrams of DFAs recognizing the following languages over ? = {0,1}:

{w : w has prefix 110}

{w : w has suffix 110}

{w : w contains the substring 110}

Give the state diagrams of DFAs recognizing the following languages over ? = {0,1}:

{w : w does not contain substring 11}

{w : every odd position of w is a 0}

Give the state diagrams of DFAs recognizing the following languages over ? = {x, y, z}:

{w : w contains at least two x’s and at most two y’s}

{w : w begins with prefix xy and ends with suffix yz}

Give the state diagrams of NFAs with the specified number of states recognizing the following languages over ? = {0, 1}:

{w : every odd position of w is a 0} with two states

{w : w begins and ends with the same symbol} with five states

{w : w does not contain the substring 011} with four states