Bissoy.com
Doctors Medicines MCQs Q&A

Let w be any string of length n in {0, 1}*. Let L be the set of all substrings of w. What is the minimum number of states in a non-deterministic finite automaton that accepts L?

Let w be any string of length n in {0, 1}*. Let L be the set of all substrings of w. What is the minimum number of states in a non-deterministic finite automaton that accepts L? Correct Answer n + 1

Key Points

 Let w be any string of length n in {0, 1}*.  Let L be the set of all substrings of w. 

Here w is a string of length n, so it requires a minimum of n+1 states accepted by NFA.

Hence the correct answer is n+1.

Additional Information

  •  A minimum string length is k then number of states in minimum NFA is k+1 states.
  • A given regular language one minimum DFA exist or many minimum NFA are possible.
  • If minimum NFA contain n states number of states in minimized DFA is <= 2n.
  • If minimum DFA contain n states number of states in minimum NFA is <= 2n
  • Minimum NFA contain n states <= number of states in minimum DFA <=2n

Related Questions

A nondeterministic finite automation with ε-moves is an extension of nondeterministic finite automation.
Select the correct differences between char and varchar data types? i. varchar is non unicode and char is unicode character data type ii. char is ‘n’ bytes whereas varchar is actual length in bytes of data entered in terms of storage size iii. varchar is variable in length and char is the fixed length string iv. For varchar, if a string is less than the maximum length then it is stored in verbatim without any extra characters while for char if a string is less than the set length it is padded with extra characters to equalize its length to given length
Consider the string abbccddeee. Each letter in the string must be assigned a binary code satisfying the following properties: 1. For any two letters, the code assigned to one letter must not be a prefix of the code assigned to the other letter. 2. For any two letters of the same frequency, the letter which occurs earlier in the dictionary order is assigned a code whose length is at most the length of the code assigned to the other letter. Among the set of all binary code assignments which satisfy the above two properties, what is the minimum length of the encoded string? 
A deterministic finite automaton (DFA) D with alphabet ∑ = {a,b} is given below. Which of the following finite state machines is a valid minimal DFA which accepts the same language as D?
John is asked to make an automaton which accepts a given string for all the occurrence of ‘1001’ in it. How many number of transitions would John use such that, the string processing application works?
How many objects will be created? String a = new String("Examveda"); String b = new String("Examveda"); String c = "Examveda"; String d = "Examveda";
How many states are there in a minimum state deterministic finite automaton accepting the language L = {w | ∈ (0,1)*, number of 0's is divisible by 2, and number of 1's is divisible by 5, respectively}?
For every NFA a deterministic finite automaton (DFA) can be found that accepts the same language.
A finite automaton accepts which type of language:
Let A be a finite set having x elements and let B be a finite set having y elements. What is the number of distinct functions mapping B into A.