TGPSC HMWSSB Manager Theory of Computation & Compilers previous year questions with answers
Every Theory of Computation & Compilers question asked in the TGPSC HMWSSB Manager (Engineering) papers on this site, grouped by topic. Answers come from TSPSC's final key; each has a short explanation (free here for a sample, all of them in the practice app).
Practise Theory of Computation & Compilers onlineRegular Languages & Finite Automata
The language represented by the regular expression 1*01* + 1* + 1*01*01* is
- All strings over {0,1} which contains exactly one zero
- All strings over {0,1} which contain at least two zeros.
- All strings over {0,1} which contain at most two zeros
- All strings over {0,1} containing exactly two zeros
Show answer
Answer: (3) All strings over {0,1} which contain at most two zeros
Explanation: open it in the practice app. It needs the ₹149 All-in-One Pass: one payment for every exam on the site.
Let L₁ = {ba, ab}, L₂ = {a, b} be two languages, then the length of the minimum string in L₁L₂* is
- 0
- 1
- 2
- 3
Show answer
Answer: (3) 2
Explanation: open it in the practice app. It needs the ₹149 All-in-One Pass: one payment for every exam on the site.
Number of strings in the language represented by the Regular expression (0 + 1)(0 + 1)1(0 + 1) is
- 4
- 6
- 8
- 16
Show answer
Answer: (3) 8
Explanation: open it in the practice app. It needs the ₹149 All-in-One Pass: one payment for every exam on the site.
Context-Free Languages & Turing Machines
Which of the following statements is incorrect?
- Every recursively enumerable language is recursive
- The union of two recursively enumerable languages is recursively enumerable
- The union of two recursive languages is recursive enumerable language
- If the language L and it's complement L' are recursively enumerable then L is recursive
Show answer
Answer: (1) Every recursively enumerable language is recursive
Explanation: open it in the practice app. It needs the ₹149 All-in-One Pass: one payment for every exam on the site.
Which of the following statement is true about Push Down Automata(PDA)?
- PDAs recognize Context-sensitive Languages
- PDAs recognize Context-free Languages
- PDAs recognize Type 1 Languages
- PDAs recognize Type 0 Languages
Show answer
Answer: (2) PDAs recognize Context-free Languages
Explanation: open it in the practice app. It needs the ₹149 All-in-One Pass: one payment for every exam on the site.
Consider the grammar G=(N,T,P,S), where N={S,A,B}, T={a,b}, P={(S → AB),(B → ab), (A → aa), (A → a), (B → b)}. Which of the following statement is true about the above grammar.
- It is Context Sensitive
- It is Context free
- It is type 0 grammar
- It is unrestricted language
Show answer
Answer: (2) It is Context free
Explanation: open it in the practice app. It needs the ₹149 All-in-One Pass: one payment for every exam on the site.
Compiler Design
A shift reduce parser generates actions specified in the braces following the corresponding rule of grammar S → xxS {PRINT "1"} S → y {PRINT "2"} S → Sz {PRINT "3"} What is the translation of xxxxyzz using the syntax directed translation?
- 23131
- 11231
- 33211
- none of these
Show answer
Answer: (1) 23131
Explanation: open it in the practice app. It needs the ₹149 All-in-One Pass: one payment for every exam on the site.
Which one of the following is the loader function accomplished by the programmer, in an absolute loading scheme? (i) Allocation (ii) Linking (iii) Reallocation
- Both (i) and (ii)
- (i) only
- (ii) only
- (iii) only
Show answer
Answer: (1) Both (i) and (ii)
Explanation: open it in the practice app. It needs the ₹149 All-in-One Pass: one payment for every exam on the site.
Which one of the following statements is correct?
- In operator precedence parsing precedence relations are defined for every pair of a non-terminal
- In operator precedence parsing, precedence relations are defined for every pair of a terminal
- In operator precedence parsing, precedence relations are defined to delimit the handle
- In operator precedence parsing precedence relations are defined to delimit a statement
Show answer
Answer: (3) In operator precedence parsing, precedence relations are defined to delimit the handle
Explanation: open it in the practice app. It needs the ₹149 All-in-One Pass: one payment for every exam on the site.
Which of the following statements is correct? (i) LR parsers can handle a larger range of languages and grammars than LL parsing (ii) LR parsers do not backtrack (iii) LR parser is a bottom-up parser
- (i) only
- (ii) only
- (iii) only
- (i), (ii) and (iii)
Show answer
Answer: (4) (i), (ii) and (iii)
Explanation: open it in the practice app. It needs the ₹149 All-in-One Pass: one payment for every exam on the site.
Which of the following is the most powerful parser?
- SLR
- LALR
- Canonical LR
- Operator-precedence
Show answer
Answer: (3) Canonical LR
Explanation: open it in the practice app. It needs the ₹149 All-in-One Pass: one payment for every exam on the site.
A top down parser generates ________
- Right-most derivation
- Right-most derivation in reverse
- Left-most derivation
- Left-most derivation in reverse
Show answer
Answer: (3) Left-most derivation
Explanation: open it in the practice app. It needs the ₹149 All-in-One Pass: one payment for every exam on the site.
Which one of the following statements is correct with respect to the grammar give below? S → 1A | 1B A → 1 B → 1
- LL(1) and LR(1)
- LL(1) but not LR(1)
- LR(1) but not LL(1)
- Neither LL(1) not LR(1)
Show answer
Answer: (4) Neither LL(1) not LR(1)
Explanation: open it in the practice app. It needs the ₹149 All-in-One Pass: one payment for every exam on the site.
Which one of the following statements is correct with respect to the grammar given below?
E → E + T F T → T * F F F → id
- Both + and * are right associative
- Both + and * are left associative
- + is left associative but * is right associative
- * is left associative but + is right associative
Show answer
Answer: (2) Both + and * are left associative
Explanation: open it in the practice app. It needs the ₹149 All-in-One Pass: one payment for every exam on the site.
Which of the following is a top-down parser?
- Predictive recursive descent
- Shift-reduce
- Canonical LR(1)
- LALR(1)
Show answer
Answer: (1) Predictive recursive descent
Explanation: open it in the practice app. It needs the ₹149 All-in-One Pass: one payment for every exam on the site.