FOR FREE CONTENT

Design a DFA for Language: “Starting with ‘a’ “

∑ = {a, b}

Answer:

Procedure to design a machine form given Language:

1. First write some set of strings accepted by the machine: L = {a, aa, aab, aabb, ….}.

2. Design the machine for the smallest accepted string (Here ‘a’).

3. Here we will design DFA so, every input move is compulsory for all states. Now assign the rest of the inputs moves to corresponding states as per the language given.

L(${\mathit{M}}_{\mathbf{1}}$) = a(a + b)* (Regular expression)

Now we calculate grammar from the above machine:

Taking a variable name for each node like for ${\mathit{q}}_{\mathbf{0}}$ we assign S and ${\mathit{q}}_{\mathbf{1}}$ as A. We cannot consider trap state at time of grammar construction.

Now we check from S ($q_0$)  where we can go. From S we can go A ($q_1$)  by input a.

So, we can write S → aA.

From S ($q_0$) we can go $q_t$ by input b. But we do not consider this move as grammar because it is a trap state.

Now, same way we can calculate all moves of A ($q_1$).

From A ($q_1$) we can go A ($q_1$) itself by input self-loop a. So, A → aA.

From A ($q_1$) we can go A ($q_1$) itself by input self-loop b. So, A → bA. 

And because of A ($q_1$) is the final state λ is also allowed to remember all final states accept λ.

So, A → λ.

All together we can write production for A:

A → aA | bA | λ

Now grammar of the above machine:

S → aA

A → aA | bA | λ