Time Left - 12:00 mins
ISRO CS 2019 : TOC Booster Quiz 1
Attempt now to get your rank among 696 students!
Question 1
After converting following NFA into DFA, the states in the final DFA will be
Question 2
If the parse tree of a word w generated by a Chomsky normal form grammar has no path of length greater than i, then the word w is of length
Question 3
Consider the regular language L =(111 +11111)*. The minimum number of states in any DFA accepting this language is:
Question 4
Define languages L0 and L1 as follows:
L0 = {<M, w, 0> | M halts on w}
L1 = {<M, w, 1> | M does not halt on w}
Here <M, w, i> is a triplet, whose first component, M, is an encoding of a Turing
Machine, second component, w, is a string, and third component, i, is a bit.
Let L = L0∪ L1. Which of the following is true?
L0 = {<M, w, 0> | M halts on w}
L1 = {<M, w, 1> | M does not halt on w}
Here <M, w, i> is a triplet, whose first component, M, is an encoding of a Turing
Machine, second component, w, is a string, and third component, i, is a bit.
Let L = L0∪ L1. Which of the following is true?
Question 5
The complement of a recursive Language is recursive
Question 6
Consider the following NFA -
The number of states and the number of final states in the DFA are-
The number of states and the number of final states in the DFA are-
Question 7
Identify the language generated by the following unrestricted grammar.
S→aASccc|ε
Aa→aA
Ac→bbc
Ab→bbb
Question 8
The finite state machine described by the following state diagram with a as starting state, where an arc label isand x stands for 1-bit input and y stands for 2-bit output
Question 9
Consider the following statements :
Which option is correct ?
Question 10
Which of the following problems is NP-problem but not P-problem.
- 696 attempts
- 2 upvotes
- 1 comment
Mar 5GATE & PSU CS