Computer science: Theory Of computation MCQs
36. Question
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
Answer
37. Question
If L and L’ are recursively enumerable then L is
Answer
38. Question
Which of the following statements is false?
Answer
39. Question
Which of the following statements are true?
I. Every left-recursive grammar can be converted to a right-recursive grammar and vice-versa
II. All e-productions can be removed from any context-free grammar by suitable transformations
III. The language generated by a context-free grammar all of whose productions are of the form X → w or X → wY (where, w is a string of terminals and Y is a non-terminal), is always regular
IV. The derivation trees of strings generated by a context-free grammar in Chomsky Normal Form are always binary trees
Answer
40. Question
Match the following:
A.Checking that identifiers are declared before their use.
B. Number of formal parameters in the declaration of a function agrees with the number of actual parameters in use of that function
C. Arithmetic expressions with matched pairs of parentheses
D. Palindromes
1. L={anbmcndm|n>=1,m>=1}
2.X → XbX | XcX | dXf | g
3.L = {wcw | w ϵ (a b) *}
4.X → bXb | cXc | ε
Answer
4 thoughts on “Computer science: Theory Of computation MCQs”