Question

a. Draw a DFA for the language of all strings over Σ = {?, ?} that do not have two consecutive ?’s.

b. Define the transition function, ?, for the DFA in the previous question.

Answer 1

DFA: Deterministic Finite Automata

It is a tuple of 5 variables.

1.Set of states.

2.Set of Input symbols.

3.Transition function

4.Initial state

5.Final state/states.

DFA accpeted language L={e,a,b,ab,ba,aa,aab,aabab,......} (no consecutive b's).

This DFA does not accept any string that contains 2 consecutive b's.

Example: we see that

1. string1 'aabaabababa'

this string is accepted by the DFA.

2.string 2 'aaababababb'

This string does not accept by DFA it goes to Dead State D in the transition Diagram.

In the above Transition Function.

A is initial State and Final State too

B and C are also the Final States

D is dead State. If a string doesn't accept by the DFA it goes to dead state.