Quizsummary
0 of 37 questions completed
Questions:
 1
 2
 3
 4
 5
 6
 7
 8
 9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
Information
 37 Questions (Selected Randomly)
 55 Minutes of Time
This quiz consists of questions from the Theory of Computation for GATE 2019 preparation.
All The Best!
You must specify a text. 

You must specify a text. 
You have already completed the quiz before. Hence you can not start it again.
Quiz is loading...
You must sign in or sign up to start the quiz.
You have to finish following quiz, to start this quiz:
Results
0 of 37 questions answered correctly
Your time:
Time has elapsed
You have scored 0 of 0 points, (0)
Average score 

Your score 

Categories
 Not categorized 0%
 1
 2
 3
 4
 5
 6
 7
 8
 9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 Answered
 Review

Question 1 of 37
1. Question
2 pointsFor S € (0+1)* let d(s)denote the decimal value of s(e.g.d(101)= 5).Let L = {s € (0 + 1)  d (s) mod 5 = 2 and d (s) mod 7 != 4)}Which one of the following statements is true?

Question 2 of 37
2. Question
1 pointsLet L denotes the language generated by the grammar S – OSO/00. Which of the following is true?

Question 3 of 37
3. Question
2 pointsDefinition of a language L with alphabet {a} is given as following. L= { a^{nk}  k > 0, and n is a positive integer constant} What is the minimum number of states needed in a DFA to recognize L?

Question 4 of 37
4. Question
2 pointsLet 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 nondeterministic finite automaton that accepts L?

Question 5 of 37
5. Question
1 pointsWhich of the following problems is undecidable?

Question 6 of 37
6. Question
1 pointsConsider the following statements about the contextfree grammar
G = {S – >SS, S – >ab, S – >ba, S – ε}
I. G is ambiguous
II. G produces all strings with equal number of a’s and b’s
III. G can be accepted by a deterministic PDA.Which combination below expresses all the true statements about G?

Question 7 of 37
7. Question
2 pointsA minimum state deterministic finite automation accepting the language L = {W W € {0,1}* , number of 0’s and 1’s in W are divisible by 3 and 5 respectively has

Question 8 of 37
8. Question
2 pointsConsider the languages:
L1 = {wwR w €{0, 1} *1L2 ={w#ww € {O,1}*},
where # is a special symbol
L3 ={www € {0,1}*}Which one of the following is TRUE?

Question 9 of 37
9. Question
1 pointsWhich of the following problems are decidable?
1) Does a given program ever produce an output?
2) If L is a contextfree language, then is L’ (complement of L) also contextfree?
3) If L is a regular language, then is L’ also regular?
4) If L is a recursive language, then, is L’ also recursive? 
Question 10 of 37
10. Question
1 pointsWhich of the following is true for the language {a^p} p is prine ?

Question 11 of 37
11. Question
1 pointsConsider the following two statements:
S1: { 0^2n n >= l} is a regu1ar language
S2: { 0^m 0^n 0^(m+n) l m >= 1 and n >= 2} is a regu1ar language
Which of the following statements is correct? 
Question 12 of 37
12. Question
2 pointsThe language L = { 0^i 2 1 ^i i>0 } over the alphabet (0,1,2) is

Question 13 of 37
13. Question
2 pointsLet L = L1 \cap L2, where L1 and L2 are languages as defined below: [GATE 2009] L1 = {a^{m}b^{m}ca^{n}b^{n}  m, n >= 0 } L2 = {a^{i}b^{j}c^{k}  i, j, k >= 0 } Then L is

Question 14 of 37
14. Question
2 pointsConsider the following two problems on undirected graphs:
α: Given G(V,E), does G have an independent set of size v—4?
β: Given G(V,E), does G have an independent set of size 5?Which one of the following is TRUE?

Question 15 of 37
15. Question
1 pointsWhich of the following are decidable ?
1. whether the intersection of two regular language is infinite.
2. whether a give context free language is regular
3. whether two push down automata accept the same language.
4. whether a given grammar is context free 
Question 16 of 37
16. Question
1 pointsS –> aSa bSb a b ;The language generated by the above grammar over the alphabet {a,b} is the set of

Question 17 of 37
17. Question
2 pointsIf s is a string over (0 + 1)* then let n0 (s) denote the number of 0’s in s and n1 (s)the number of l’s in s. Which one of the following languages is not regular?

Question 18 of 37
18. Question
2 pointsLet L1 be a recursive language, and let L2 be a recursively enumerable but not a recursive language. Which one of the following is TRUE?

Question 19 of 37
19. Question
1 pointsLet S and T be language over ={a,b} represented by the regular expressions (a+b*)* and (a+b)*, respectively. Which of the following is true?

Question 20 of 37
20. Question
2 pointsLet L1 be a regular language, L2 be a deterministic contextfree language and L3 a recursively enumerable, but not recursive, language. Which one of the following statements is false?

Question 21 of 37
21. Question
1 pointsLet L1 be a recursive language. Let L2 and L3 be languages that are recursively enumerable but not recursive. Which of the following statements is not necessarily true?

Question 22 of 37
22. Question
1 pointsConsider the language L1, L2, L3 as given below.
L1={0^{p}1^{q}  p,q \in N}
L2={0^{p}1^{q}  p,q \in N and p=q}
L3={0^{p}1^{q}1^{r}  p,q,r \in N and p=q=r}
Which of the following statements is NOT TRUE?

Question 23 of 37
23. Question
1 pointsGiven an arbitrary nondeterministic finite automaton (NFA) with N states, the maximum number of states in an equivalent minimized DFA is at least.

Question 24 of 37
24. Question
1 pointsWhich one of the following languages over the alphabet {0,1} is described by the regular expression: (0+1)*0(0+1)*0(0+1)*?

Question 25 of 37
25. Question
2 pointsConsider the regular language L =(111+11111)*. The minimum number of states in any DFA accepting this languages is:

Question 26 of 37
26. Question
2 pointsThe minimum state automaton equivalent to the above FSA has the following number of states

Question 27 of 37
27. Question
1 pointsWhich of the following is TRUE?

Question 28 of 37
28. Question
1 pointsIf L and L¯ are recursively enumerable, then L is

Question 29 of 37
29. Question
2 pointsConsider the languages: L1 ={a^n b^n c^m  n,m >01 and L2 ={a^n b^m c^m n,m> o) Which one of the following statements is FALSE?

Question 30 of 37
30. Question
1 pointsThe problem 3SAT and 2SAT are

Question 31 of 37
31. Question
1 pointsWhich of the following pairs have DIFFERENT expressive power?

Question 32 of 37
32. Question
2 pointsLet L={w \in (0 + 1)*w has even number of 1s}, i.e. L is the set of all bit strings with even number of 1s. Which one of the regular expression below represents L?

Question 33 of 37
33. Question
2 pointsWhich of the following languages is regular?

Question 34 of 37
34. Question
1 pointsWhich of the following statements in true?

Question 35 of 37
35. Question
1 pointsLet SHAM3 be the problem of finding a Hamiltonian cycle in a graph G =(V,E)with V divisible by 3 and DHAM3 be the problem of determining if a Hamiltonian cycle exists in such graphs. Which one of the following is true?

Question 36 of 37
36. Question
1 pointsWhich one of the following is FALSE?

Question 37 of 37
37. Question
2 pointsConsider the languages
L1={0^{i}1^{j}i != j},
L2={0^{i}1^{j}i = j}
L3 = {0^{i}1^{j}i = 2j+1}
L4 = {0^{i}1^{j}i != 2j}
Which one of the following statements is true?