Question

Automata Theory and Formal Languages

Instructions:

Draw the DFA (Deterministic Finite Automaton) of the following:

1. DFA in which set of all strings can be accepted which end with ‘a’
2. DFA in which set of all strings can be accepted which start with ab
3. DFA in which set of all strings can be accepted which contain ab
4. DFA in which set of all strings can be accepted which ends with ab

Answer 1

Solution:

(a)

Explanation:

=>In the given DFA there are 3 states.

=>State A is the initial state, state B is the final state and state D is dead state.

=>At the final state only strings are accepted by the language otherwise rejected.

=>We can see that all strings ending with a is accepted at the final state B.

(b)

Explanation:

=>In the given DFA there are 4 states.

=>State A is the initial state, state C is the final state, state B is intermediate state and state D is dead state.

=>Strings are accepted at the final state only.

=>We can see that all the strings starting with ab will be accepted at the final state C.

(c)

Explanation:

=>In the given DFA there are 3 states.

=>State A is the initial state, state B is the final state and state C is the final state.

=>Strings are accepted at the final state only.

=>We can see that all the strings which contain ab as substring will be accepted.

(d)

Explanation:

=>In the given DFA there are 4 states.

=>State A is the initial state, state C is the final state, state B is the intermediate state and state D is the dead state.

=>Strings are accepted at the final state only.

=>We can see that all the strings which end with ab will be accepted at the final state C.

I have explained each and every part with the help of statements attached to it.