DFA (Deterministic Finite Automata)

[Apprentice123]

DFA M = ({q_0, q_1, q_2}, {0,1}, delta, q_0, {q_1}), delta is:

delta | 0 1
q_0 | q_0 q_1
q_1 | q_0 q_2
q_2 | q_2 q_1

a) What graphic transition?

My solution:

q_0 ->1 0<- q1 ->1 1<- q2 0<-

b) This automaton accepts the word 01, 101, 00111, 11001?

My solution:

Yes

c) Find two words that the automaton rejects

My solution:

10 and 110


Are correct ?

[bobdark]

seems correct even though a) is not clear

[Apprentice123]

seems correct even though a) is not clear

Thanks.

I do not know how to make a table here


Please see if this is correct:

Do a DFA that recognizes all strings with prefix ab, on the alphabet {a,b}

My solution:

q_o => go "a" to q_2 => go "b" to q_1 => go "a,b" to q_1
M = ({q_0, q_1, q_2}, {a,b}, delta, q_0, {q_1})

[bobdark]

yeah its correct

[John]

Thanks.

I do not know how to make a table here


Please see if this is correct:

Do a DFA that recognizes all strings with prefix ab, on the alphabet {a,b}

My solution:

q_o => go "a" to q_2 => go "b" to q_1 => go "a,b" to q_1
M = ({q_0, q_1, q_2}, {a,b}, delta, q_0, {q_1})

I believe what you described is an NFA. Your "DFA" does not account for the string "ba" for example.

delta | a b
q0 | q1 q3
q1 | q3 q2
q2 | q2 q2
q3 | q3 q3

M = ({q0, q1, q2, q3}, {a,b}, delta, q0, {q2})

[bobdark]

No he's fine, because when you don't specify what does the DFA do in a specific state on a specific input, its interpreted as entering a "pit" state - one from which the automata can not accept any word.

[Apprentice123]

I believe what you described is an NFA. Your "DFA" does not account for the string "ba" for example.

delta | a b
q0 | q1 q3
q1 | q3 q2
q2 | q2 q2
q3 | q3 q3

M = ({q0, q1, q2, q3}, {a,b}, delta, q0, {q2})

The problem need to begin the prefix "ab" so I can not begin to "ba"

[Apprentice123]

yeah its correct

Thank you. Please look this:

Find a DFA that recognizes all strings over the alphabet {01}, except those containing the substring 001

My solution:

q0 => go "1" to q0 and "0" to q1
q1 => go "1" to q0 and "0" to q2
q2 => go "0" to q1 and "1" to q3
q3 => go "0,1" to q3
M = ({q0, q1, q2, q3}, {01}, delta, q0, {q0, q1, q2})

is correct ?

[John]

No he's fine, because when you don't specify what does the DFA do in a specific state on a specific input, its interpreted as entering a "pit" state - one from which the automata can not accept any word.

Perhaps this is a shortcut you may take, but your assumption is not part of the formal definition. Q is the set of all states, therefore your "pit" state (my q3) must be an element of Q (which you did not formally define), and for each pair of state an input symbol, there is one transition to the next state. Therefore there _must_ be a transition for (q0, b) and (q1, a) and your "pit" state must also have a ("pit", a) and ("pit", b) all of which do not exist. You may interpret it however you would like, but formally, it is wrong.

The problem need to begin the prefix "ab" so I can not begin to "ba"

Right, your DFA is suppose to accept strings that begin with "ab" and reject strings that begin with aa, or b. However, your DFA does not accept nor reject strings that begin with aa or b - it just fails. Your professor may allow the shortcut bobdark suggested, but formally it is wrong.

Thank you. Please look this:

Find a DFA that recognizes all strings over the alphabet {01}, except those containing the substring 001

My solution:

q0 => go "1" to q0 and "0" to q1
q1 => go "1" to q0 and "0" to q2
q2 => go "0" to q1 and "1" to q3
q3 => go "0,1" to q3
M = ({q0, q1, q2, q3}, {01}, delta, q0, {q0, q1, q2})

is correct ?

Yes. (although I am assuming your alphabet is {0,1} not {01})

[Apprentice123]

Perhaps this is a shortcut you may take, but your assumption is not part of the formal definition. Q is the set of all states, therefore your "pit" state (my q3) must be an element of Q (which you did not formally define), and for each pair of state an input symbol, there is one transition to the next state. Therefore there _must_ be a transition for (q0, b) and (q1, a) and your "pit" state must also have a ("pit", a) and ("pit", b) all of which do not exist. You may interpret it however you would like, but formally, it is wrong.


Right, your DFA is suppose to accept strings that begin with "ab" and reject strings that begin with aa, or b. However, your DFA does not accept nor reject strings that begin with aa or b - it just fails. Your professor may allow the shortcut bobdark suggested, but formally it is wrong.


Yes. (although I am assuming your alphabet is {0,1} not {01})

Thank you.

I find it odd, because the exercise is {01}