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 pointsThe minimum state automaton equivalent to the above FSA has the following number of states

Question 2 of 37
2. 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 3 of 37
3. Question
1 pointsWhich of the following problems is undecidable?

Question 4 of 37
4. 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?

Question 5 of 37
5. 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 6 of 37
6. Question
1 pointsWhich of the following statements in true?

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

Question 8 of 37
8. 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 9 of 37
9. 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 10 of 37
10. 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 11 of 37
11. Question
1 pointsWhich of the following is true for the language {a^p} p is prine ?

Question 12 of 37
12. 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 13 of 37
13. 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 14 of 37
14. 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 15 of 37
15. 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 16 of 37
16. Question
1 pointsThe problem 3SAT and 2SAT are

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

Question 18 of 37
18. 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 19 of 37
19. 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 20 of 37
20. 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 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
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 23 of 37
23. Question
1 pointsMatch all items in Group 1 with correct options from those given in Group 2.
List I List II
P. Regular Expression 1. Syntax analysis
Q. Push down automata 2. Code Generation
R. Dataflow analysis 3. Lexical analysis
S. Register allocation 4. Code optimization 
Question 24 of 37
24. 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 25 of 37
25. Question
1 pointsWhich of the following pairs have DIFFERENT expressive power?

Question 26 of 37
26. Question
2 pointsThe language L = { 0^i 2 1 ^i i>0 } over the alphabet (0,1,2) is

Question 27 of 37
27. 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 28 of 37
28. 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 29 of 37
29. Question
1 pointsS –> aSa bSb a b ;The language generated by the above grammar over the alphabet {a,b} is the set of

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

Question 31 of 37
31. 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 32 of 37
32. 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 33 of 37
33. 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 34 of 37
34. Question
1 pointsWhich of the following is TRUE?

Question 35 of 37
35. 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 36 of 37
36. Question
1 pointsWhich one of the following is FALSE?

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