Geekforgeeks full length

Question

Let L = (0+1)*1(0+1)^(n−1) and following statements regrading language L:

1. The language L can be recognised by a non-deterministic automaton with (n+1) states. 
2. Deterministic automaton recognises this language must have at least 2^n states. 

(Assume n≥1).
Which of the following statement(s) is/are correct?

• A. 1 onlty
• B. 2 only
• C. Both 1 and 2
• D. neither 1 and 2

---------------------------------------

According to me, L can be written as (0+1)*1(0+1)* which makes option D most suitable.

Comments

According to your string, 1 belongs to the language in question which is incorrect

Answer 1

L = (0+1)*1(0+1)^(n−1)

     = { set of all strings such that the nth symbol from RHS is 1 }

This can be represented by NFA having n+1 states.

For DFA, it will take  2^n states.

So Option C is correct.

.