Design an NFA for a language that accepts all strings over {0,1} in which the second last symbol is always '1', then convert it to it's equivalent DFA.

 Design an NFA for a language that accepts all strings over {0,1} in which the second last symbol is always '1', then convert it to it's equivalent DFA.

Solution:

Here, L={set of all strings whose second last symbol is always '1'}

            ={010 , 0111...........}

Here, A is the initial state and C is the final state.

Now, we can make the transition table as follows:

	0	1
A	A	A,B
B	C	C
C	φ	φ

From the transition table of NFA, we can make the transition table of DFA

	0	1
A	A	AB
AB	AC	ABC
AC	A	AB
ABC	AC	ABC

Here, from A after receiving 1 as input, we are going to two different states A and B, in DFA, we have to combine both the states to get a new states AB. Now, from AB after receiving input as 0, it will go to another state AC in DFA as AB is the combination of A and B and transition of AB will also be the combination of A and B. 

The final states of the DFA will be the states which contains C: AC and ABC.

So, We got the diagram of the DFA as: