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

  1. Pingback: ugg france pas cher
  2. Pingback: bottes filles chipie

Leave a Reply