minimal DFA

Question

The minimal state DFA, accepting all strings over the alphabet {0,1} where the n^th symbol in every string from the right end is a 1, has

a) 2ⁿ states b) 2^n-1 states c) 2ⁿ⁺¹ states d) None of the above

 

Answer 1

Answer should be 2^n states i.e. option A.

Generalized Regular Expression for such a DFA will be: (0 + 1)*1 concatenated with a string of (n – 1) 0’s

Steps involved in drawing the DFA.

1. Draw the corresponding NFA – It can be drawn easily. THE NFA WILL ALWAYS CONTAIN “n + 1” STATES. (Why n + 1 states always? ? : because you have to COUNT from 1 to N+1, & each state will remember a count).                     NOTE – On drawing the NFA you will notice that on the whole NFA there is ONLY A SINGLE NON DETERMINISTIC TRANSITION. That non deterministic transition will be from the start state, on input 1.
2. Change the NFA to the minimal DFA – Subset Construction can be used in this step, to convert the NFA into a MINIMAL DFA (Subset Construction will give a minimal DFA for any value of n, you can check it by set partitioning etc.) Since it is known that there is only one Non Deterministic Transition for any value of n, we can guarantee that if the number of states in the NFA is x then number of states in the corresponding DFA HAVE TO BE 2^(x – 1).(Why ? ? : refer to CAUTION)

Summarizing:

For any value of n,

The number of states in the NFA have to be n+1.

In this question, if the NFA contains n + 1 states then the minimal DFA will have 2^((n + 1) – 1) = 2^n states.

Moreover The number of final states in the DFA will be 2^(n – 1).

Example: for n = 3,

The number of states in the NFA = 3 + 1 = 4, (say A (Initial state), B, C, D (Final State)).

The only non deterministic transition in this NFA will be delta(A, 1) = {A, B}.

The number of states in the minimal DFA = 2^((3 + 1) – 1) = 2^3 = 8.

The number of final states in the minimal DFA = 2^(3 – 1) = 4.

States in the minimal DFA: {A}(start state), {A, B}, {A, C}, {A, B, C}, {A, D}, {A, B, D}, {A, C, D}, {A, B, C, D}.

  Final States in the minimal DFA: {A, D}, {A, B, D}, {A, C, D}, {A, B, C, D}.

CAUTION: I have NO PROOFS for the argument & implication I made in Step 2 (i.e."Subset Construction will always lead to a MINIMAL DFA in this case" & "Since it is known that there is only one Non Deterministic Transition for any value of n, we can guarantee that if the number of states in the NFA is x then number of states in the corresponding DFA HAVE TO BE 2^(x – 1)").I concluded them by drawing DFAs for n = 1, 2, 3 and analyzing them, but my intuition says they must be true.

Answer 2

ans a)2^n

Comments

Always try to provide an explanation with your answer.

Answer 3

Answer is 2^n.

Check DFA construction on following question solved for N = 3.

https://gateoverflow.in/544/gate1991_17-b

Answer 4

Regular expressions will be $(0+1)^*1(0+1)^{(n-1)}$

No of states will be $n+1$..

(Minimum length is $n$. So $n+1$ states without a Dead/Trap state.)

Comments

so what do you suggest laser?? which option do you choose??

also arjun sir they are asking for minimal DFA ,i.e one dead state has to be there if all paths are not displayed so don't you think no of states will be N+1.

---

Here, we need to keep track of all possible paths for the last n symbols - actually not all possible, but the information whether that symbol is '1' or not and this has to be done for n states- 2ⁿ states. 

Similar one : https://gateoverflow.in/7373/what-number-states-minimal-input-symbols-where-last-symbol

---

https://gateoverflow.in/10695/build-that-accepts-language-strings-such-that-next-last-letter?show=10695#q10695