Draw a DFA Graph

Question

For each of the following languages, draw a DFA( as a graph) recognizing it:

1. All strings over ∑={x, y, z} with either contain an x or contain both a y and a z
2. All strings over ∑={a, b, c, ..., z} with either containing the substring aaa (e.g aaab and zazaaab but not ababa
3. All strings over ∑={a, b, c} whose symbols are in alphabetical order (e.g aaac and bcc but not aba and ca)

Answer 1

1. All strings over Σ={x, y, z} that either contain an x or contain both a y and a z:

1. Start with the initial state (q0).
2. Create two branches from q0 for each possible input: one for x and one for y or z.
3. For the x branch, create an accepting state (q1) where the DFA accepts the string.
4. For the y or z branch, create two more branches from the same state: one for y and one for z.
5. For the y and z branches, create an accepting state (q2) where the DFA accepts the string.

x ---(q1)---> (Accept)

/ \

q0 y,z ---(q2)---> (Accept)

\ /

y,z

2. All strings over Σ={a, b, c, ..., z} that contain the substring "aaa":

1. Start with the initial state (q0).
2. Create a branch for each input character a, b, c, ..., z from q0.
3. If the input is 'a', transition to a new state (q1).
4. If the input is 'a' again, stay in q1.
5. If the input is 'a' a third time, transition to an accepting state (q2).
6. For any other input, return to the initial state (q0).

a

(q0) -------> (q1) -------> (q2) (Accept)

| a | a |

other input

3. All strings over Σ={a, b, c} with symbols in alphabetical order:

1. Start with the initial state (q0).
2. Create a branch for each input character a, b, and c from q0.
3. If the input is 'a', stay in q0.
4. If the input is 'b', transition to a new state (q1).
5. If the input is 'c', transition to another new state (q2).
6. Create transitions from q1 to q2 for input 'c' to maintain alphabetical order.
7. The DFA accepts the string when it reaches the accepting state (q2).

a

(q0) -------> (q1) -------> (q2) (Accept)

| b | c |

other input