Theory of Computation and Compiler Design Mock Test

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. Definition 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?

3. Consider the set of strings on {0,1} in which, every substring of 3 symbols has at most two zeros. For examples, 001110 and 011001 are in the language, but 100010 is not. All strings of length less than 3 are also in the language. A partially completed DFA that accepts this language is shown below. The missing arcs in the DFA are

4. Consider the following Finite State Automaton The language accepted by this automaton is given by the regular expression

5. A minimum state deterministic finite automation accepting the language L = {W |W EUR {0,1}* , number of 0's and 1's in W are divisible by 3 and 5 respectively has

6. Which of the following statements is false?

7. Let 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?

8. Which is True about SR and RR-conflict:

9. 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?

10. Incremental-Compiler is a compiler

11. Which one of the following is FALSE?

12. The regular grammar for the language L = {anbm | n + m is even} is given by

13. Which of the following statements in true?

14. The minimum state automaton equivalent to the above FSA has the following number of states

15. In a compiler, keywords of a language are recognized during

16. Debugger is a program that

17. Which of the following is true for the language {a^p} p is prine ?

18. The number of tokens in the following C statement is printf("i=%d, &i=%x", i&i);

19. Which of the following pairs have DIFFERENT expressive power?

20. Which one of the following statements is FALSE?

21. The grammar S ? aSa | bS | c is

22. Consider the regular language L =(111+11111)*. The minimum number of states

23. An LALR(1) parser for a grammar G can have shift-reduce (S-R) conflicts if and only if

24. From the given data below : a b b a a b b a a b which one of the following is not a word in the dictionary created by LZ-coding (the initial words are a, b)?

25. The grammar A ? AA | (A) | e is not suitable for predictive-parsing because the grammar is

26. Which of the following is essential for converting an infix expression to the postfix from efficiently?

27. 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)*?

28. Let L denotes the language generated by the grammar S OSO/00. Which of the following is true?

29. If s is a string over (0 + 1)* then let n0 (s) denote the number of 0s in s and n1 (s)the number of ls in s. Which one of the following languages is not regular?

30. Consider 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?

31. Let L = L1 \cap L2, where L1 and L2 are languages as defined below: 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

32. Consider 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?

33. Which of the following problems are decidable?
1) Does a given program ever produce an output?
2) If L is a context-free language, then is L’ (complement of L) also context-free?
3) If L is a regular language, then is L’ also regular?
4) If L is a recursive language, then, is L’ also recursive?

34. The language L = { 0^i 2 1 ^i i>-0 } over the alphabet (0,1,2) is

35. For 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?

36. Let 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?

37. Consider the following statements about the context free grammarG = {S - >SS, S - >ab, S - >ba, S - ε}I. G is ambiguousII. G produces all strings with equal number of a’s and b’sIII. G can be accepted by a deterministic PDA.Which combination below expresses all the true statements about G?

38. Let L1 be a regular language, L2 be a deterministic context-free language and L3 a recursively enumerable, but not recursive, language. Which one of the following statements is false?

39. Consider the languages: GATE[2005]L1 = {wwR w €{0, 1} *1L2 ={w#ww € {O,1}*},where # is a special symbolL3 ={www € {0,1}*}Which one of the following is TRUE?

40. Let L1 be a recursive language, and let L2 be a recursively enumerable but not a recursive language. Which one of the following is TRUE?

41. Consider 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?

42. Consider 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?

43. Let 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?

44. S –> aSa| bSb| a| b ; The language generated by the above grammar over the alphabet {a,b} is the set of

45. Match 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

46. Consider 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?

47. Which 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

48. Consider the CFG with {S,A,B) as the non-terminal alphabet, {a,b) as the terminal alphabet, S as the start symbol and the following set of production rules
S --> aB S --> bA
B --> b A --> a
B --> bS A --> aS
B --> aBB A --> bAA
Which of the following strings is generated by the grammar?

49. Which of the following are decidable?
I. Whether the intersection of two regular languages is infinite
II. Whether a given context-free language is regular
III. Whether two push-down automata accept the same language
IV. Whether a given grammar is context-free

50. In some programming languages, an identifier is permitted to be a letter followed by any number of letters or digits. If L and D denotes the set of letters and digit respectively. Which of the following expression defines an identifier?

Computer Science Engineering Mock Tests with Answers
Distributed Computing System Mock Test
Software Project Management Mock Test
Artificial Intelligence and Robotics Mock Test
Basics of Database Management Mock Test
C# Programming Mock Test
C#.NET Programming Mock Test
Cloud Computing Mock Test
Communication Network Mock Test
Computer Architecture Mock Test
Computer Architecture and Organization Mock Test
Computer Fundamentals Mock Test
Computer Networking Mock Test
Computer Networks Mock Test
CPP Programming Mock Test
Data Analysis Mock Test
Data Communication and Computer Network Mock Test
Data Compression and Data Retrieval Mock Test
Data Mining and Business Intelligence Mock Test
Data Mining and Data Warehouse Mock Test
Data Structure and Algorithms Mock Test
Data Structures Mock Test
DataBase Management System Mock Test
Design and Analysis of Algorithms Mock Test
Digital Electronics and Logic Design Mock Test
Digital Logic Circuits Mock Test
Digital Principles and System Design Mock Test
Discrete Mathematics Mock Test
Discrete Structure Mock Test
DotNet Technology Mock Test
Embedded Real Time Operating System Mock Test
Green Computing Mock Test
High Performance Computing Mock Test
Information Cyber Security Mock Test
Information and Network Security Mock Test
Information Retrival Techniques Mock Test
Information Systems and Engineering Economics Mock Test
Machine Learning Mock Test
Microprocessor and Interfacing Technique Mock Test
Microprocessors Mock Test
Muli core Architectures and Pro Mock Test
Multi core processors Mock Test
Network Security Mock Test
Neural Networks and Fuzzy Control
Object Oriented Programming Mock Test
Operating System Architecture Mock Test
Operating System Mock Test
Problem Solving and Python Programming Mock Test
Programming for Problem Solving Mock Test
Python Programming Mock Test
Soft Computing Mock Test
Software Design Modeling Mock Test
Software Engineering Mock Test
Software Testing Mock Test
Software Testing and Quality Assurance Mock Test
Theory of Computation and Compiler Design Mock Test
Theory of Computation Mock Test
Ubiquitous Computing System Mock Test