Question

Draw the NFA for language L2 = { w | w ends in 12}. Alphabet {0,1,2}

Answer 1

Answer: - Draw the NFA for language L2 = { w | w ends in 12}. Alphabet {0,1,2}

Now we have to draw a state diagram of a NFA with recognise the above language.

NFA (Non deterministic finite automata) is as follows:-

Formal Definition, an NFA is a 5-tuple NFA= (Q, Σ, q0, F, δ) where Q=set of Possible total states, Σ=input alphabets, q0 =initial states, F=set of final states, δ= transition function mapping between (Q*Σ--->2^Q).

NFA basically gives two outputs for giving single inputs. So it is called NFA.

For example

Here in above figure of NFA if we give input 0 to the state Q0 we will reach to Two states Q0 as well as Q1 it means that we have two choices .it means that we are not able to decides in which   state we have to move either Q0 or Q1 so that there is no uniqueness is there in above figure. So that it is called NFA. Here Q1 is the final states, Q0 is the initial state, a is the input alphabet.

       Transition Table of above NFA

Present State	Input	Output State
-->Q0	a	(Q0,Q1)
Q1	a	Q1

Now consider our given problem of NFA Here we have given the Language

Draw the NFA for language L2 = { w | w ends in 12}. Alphabet {0,1,2}

Note: We are assuming that we have to make a NFA of the above condition with three states.

So first of all we have to identify which strings are the parts of our given Language.

First of all we have to draw Regular expression for the above problems:-

Regular Expression: -        (0+1+2)*12

So in above problem it is clearly mentioned that Our NFA will accept such kind of strings which is always ended with 12. It means that before 12 it could be any string are possible of 0, 1, and 2.

Meanwhile   last two strings is fixed

Here in above figure first position could be any string of 0,1,2 that is all the possible combination of 0,1,2   so it can be represented by Regular expression    (0,1,2)*

And for fulfilling the our condition of a given Language we must ended with our string of 12. So 12 is concatenate with Regular expression    (0, 1, 2)*.

So final Regular expression of the above Language is as follow:-

Regular expression RE = (0+1+2)*12

L = {12, 112, 1112, 1112..., 012, 0112, 0212, 00012, 11112, 101012,.....}

In given Language L it could accept 12 if we put * as null we will get 12 only string, it can accept 112, it can accept 1112, it can accept 11112, it can accept 00110012 and many more strings.

Note:- Here in above Regular Expression 12 is the minimal String of a given Langauge.because if we Put (0+1+2)* as a Null then we will get only 12 which is called Minimal String.

In summary we can say that in Given Language L =( it can accept such kind of strings of all the possible combination of 0,1,2 followed by 12).

So keeping in mind all such condition we are going to construct NFA for the given Language

L2 = { w | w ends in 12}. Alphabet {0,1,2}

Here from above NFA all the valid strings is accepted by given NFA

And rejected all invalid states.

L = {12, 112, 1112, 1112..., 012, 0112, 0212, 00012, 11112, 101012,.....}

Here in above Fig “2” Q0 is initial state where input is processed Q1 is intermediary state and Q2 is last state which is final state. And we have input alphabet is Σ (Sigma) over the (0, 1).

Present State	Input	Output State
--->Q0	0	Q0
Q0	1	Q0,Q1
Q0	2	Q0
Q1	2	Q2

                                               Transition Table of Fig “2”

Justify why your NFA rejects the String   “11”           

We have String   “11” we have to processed it one by one from state Q0.

Here in given Input Processing Q0 states give input 1 we will reach to state Q0 now give Q0 to input 1 we will reach to Q0 as will Q1. Now there is no transition is there on    (Q0, Q1) due to end of string in Fig “2”. Machine will halt on such a non final state and move to in deadlock. So that string “11” is rejected by the NFA.

However machine accepting string   “012”.

Here in given Input Processing Q0 states give input 1 we will reach to state Q0 now give Q0 to input 1 we will reach to Q0 as will Q1. Now there is no transition is there on    (Q0, Q1) due to end of string in Fig “2”. Machine will halt on such a non final state and move to in deadlock. So that string “11” is rejected by the NFA.

However machine accepting string   “012”.

Here machine will stop on input 012 and reach on final state Q2 which is a final state so that input “012” is accepted by NFA.

Note: - one important point is that we are building NFA so it may be possible that we will reach to multiple states with giving single input. For example in accepting “012” string       (Q0, 0)-->Q0, (Q0, 1) --->(Q0, Q1) if we take Q0 state than (Q0, 2)--->Q0 which is non final state. And if we take (Q1,2)--->Q2 which is final state.

          End of Answer.