Home > Computer Engineering > Quizzes > Theory of Computation and Compiler Design Practice Test
Theory of Computation and Compiler Design Practice Test
Fast practice, instant feedback. Timer auto-submits when time’s up.
Avg score: 0% • Most missed: “Which of the following describes a handle (as applicable to LR-parsing) appropri…”

Automata theory (also known as Theory Of Computation) is a theoretical branch of Computer Science and Mathematics, which mainly deals with the logic of computation with respect to simple machines, referred to as automata. Automata* enables scientists to understand how machines compute the functions and solve problems.
Theory of Computation is very important in compiler design as it helps in writing efficient algorithms, which help make efficient compiler construcion.

Theory of Computation and Compiler Design Practice Test
Time left 00:00
25 Questions

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. The grammar whose productions are
→ if id then
→ if id then else
→ id := id is ambiguous because
a) the sentence if a then if b then c:= d has two parse trees
b) the left most and right most derivations of the sentence if a then if b then c:= d give rise to different parse trees
c) the sentence if a then if b then c:= d else c:= f has more than two parse trees
d) the sentence if a then if b then c:= d else c:= f has two parse trees
3. Debugger is a program that
4. The language L = { 0^i 2 1 ^i i>-0 } over the alphabet (0,1,2) is
5. 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)?
6. 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?
7. Consider the grammar shown below S → i E t S S' | a S' → e S | ε E → b In the predictive parse table. M, of this grammar, the entries M[S', e] and M[S', $] respectively are
8. 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?
9. Consider the grammar S → (S) | a Let the number of states in SLR(1), LR(1) and LALR(1) parsers for the grammar be n1, n2 and n3 respectively. The following relationship holds good
10. Assume that the SLR parser for a grammar G has n1 states and the LALR parser for G has n2 states. The relationship between n1 and n2 is:
11. Which of the following is essential for converting an infix expression to the postfix from efficiently?
12. Which of the following describes a handle (as applicable to LR-parsing) appropriately?
13. A language L allows declaration of arrays whose sizes are not known during compilation. It is required to make efficient use of memory. Which of the following is true?
14. The minimum state automaton equivalent to the above FSA has the following number of states
15. Consider the intermediate code given below:
1. i = 1
2. j = 1
3. t1 = 5 * i
4. t2 = t1 + j
5. t3 = 4 * t2
6. t4 = t3
7. a[t4] = –1
8. j = j + 1
9. if j <= 5 goto(3)
10. i = i + 1
11. if i < 5 goto(2)
The number of nodes and edges in the control-flow-graph constructed for the above code, respectively, are
16. Consider the following two statements:
P: Every regular grammar is LL(1)
Q: Every regular set has a LR(1) grammar
Which of the following is TRUE?
17. The number of strings of length 4 that are generated by the regular expression (0+1+|2+3+)*, where | is an alternation character and {+, *} are quantification characters, is:
18. Which of the following statement(s) regarding a linker software is/are true?
I. A function of a linker is to combine several object modules into a single load module.
II. A function of a linker is to replace absolute references in an object module by symbolic references to locations in other modules.
19. Consider the following context free languages:
L1 = {0^i 1^j 2^k | i+j = k}
L2 = {0^i 1^j 2^k | i = j or j = k}
L3 = {0^i 1^j | i = 2j+1}
Which of the following option is true?
20. 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
21. Consider the following translation scheme. S → ER R → *E{print('*');}R | ε E→ F + E {print('+');} | F F → (S) | id {print(id.value);} Here id is a token that represents an integer and id.value represents the corresponding integer value. For an input '2 * 3 + 4', this translation scheme prints
22. The grammar A → AA | (A) | ε is not suitable for predictive-parsing because the grammar is
23. 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?
24. A canonical set of items is given below
S ..> L. > R
Q ..> R.
On input symbol < the set has
25. In a compiler, keywords of a language are recognized during

⚡ Recently practiced quizzes in this topic
Live quiz activity
Information Technology Knowledge Test Computational Thinking Concepts Computer Fundamentals Practice Test: Secondary Storage Devices Computer Network MCQs General CS (Computer Science) Knowledge Test Big Data: NoSQL Green Computing Practice Test Natural Language Processing: Word Level Analysis Computer Fundamentals Practice Test Operating Systems Practice Test: Introduction to OS
 
❤ If you liked Fatskills, consider supporting us by checking out The Life Manuals You Never Got.

🌈  Our mission is to help improve your scores in any subject and exam withonline quizzes, practice tests, study guides, & advice for students. Since 2018.
About | Explore | User Guide | Topics | Subjects | Doubt Solver | Career Aptitude Test | Answers | Free Tools | OSHA Basics Quiz | What Should We Know?
Privacy | Terms |
Without work one finishes nothing. - Ralph Waldo Emerson
© 2026 Fatskills.com

All trademarks, logos and brand names are the property of their respective owners. All company, product and service names used in this website are for identification purposes only. Use of these names, trademarks and brands does not imply endorsement.