Theory of Computation and Compiler Design MCQs | Page - 3

Q. 21) 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?

Q. 22) 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?

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

Q. 24) In a compiler, keywords of a language are recognized during

Q. 25) The lexical analysis for a modern computer language such as Java needs the power of which one of the following machine models in a necessary and sufficient sense?

Q. 26) Consider the following statements:
(I) The output of a lexical analyzer is groups of characters.
(II) Total number of tokens in printf("i=%d, &i=%x", i, &i); are 11.
(III) Symbol table can be implementation by using array and hash table but not tree.
Which of the following statement(s) is/are correct?

Q. 27) Which one of the following statements is FALSE?

Q. 28) A lexical analyzer uses the following patterns to recognize three tokens T1, T2, and T3 over the alphabet {a,b,c}. T1: a?(b∣c)*a T2: b?(a∣c)*b T3: c?(b∣a)*c Note that ‘x?’ means 0 or 1 occurrence of the symbol x. Note also that the analyzer outputs the token that matches the longest possible prefix. If the string bbaacabc is processes by the analyzer, which one of the following is the sequence of tokens it outputs?

Q. 29) Consider the following statements related to compiler construction :
I. Lexical Analysis is specified by context-free grammars and implemented by pushdown automata.
II. Syntax Analysis is specified by regular expressions and implemented by finite-state machine. Which of the above statement(s) is/are correct?

Q. 30) 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.