×
Detail Form
We will send your result on your email id and phone no. please fill detail
1.
Let w be any string of length n is {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?
2.
Which one of the following languages over the alphabet {0,1} is described by the regular expression: (0+1)*0(0+1)*0(0+1)*?
3.
Which of the following problems is undecidable?
4.
Consider three decision problems P1, P2 and P3. It is known that P1 is decidable and P2 is undecidable. Which one of the following is TRUE?
5.
Consider the following decision problems:
(P1) Does a given finite state machine accept a given string
(P2) Does a given context free grammar generate an infinite number of stings
Which of the following statements is true?
(P1) Does a given finite state machine accept a given string
(P2) Does a given context free grammar generate an infinite number of stings
Which of the following statements is true?
6.
Consider the following statements:
1. The complement of every Turning decidable language is Turning decidable
2. There exists some language which is in NP but is not Turing decidable
3. If L is a language in NP, L is Turing decidable Which of the above statements is/are True?
1. The complement of every Turning decidable language is Turning decidable
2. There exists some language which is in NP but is not Turing decidable
3. If L is a language in NP, L is Turing decidable Which of the above statements is/are True?
7.
Which one of the following is not decidable?
8.
Which of the following statements is false?
9.
Which of the following statement is false?
10.
Let S be an NP-complete problem. Q and R are other two problems not known to be NP. Q is polynomial time reducible to S and S is polynomial time reducible to R. Which of the following statements is true?