MCQ | Theory of Computation (TOC) Part 2

Theory of Computation - TOC

« Previous Next »

1. If L be a language recognizable by a finite automaton, then language front {L} = { w such that w is prefix of v where v ∈ L }, is a

A) Context-free language
B) Regular language
C) Context-sensitive language
D) Recursive enumeration language

... Answer is B)
Regular language

2. If a language is denoted by a regular expression L = ( x )* (x | y x ) , then which of the following is not a legal string within L ?

A) xyx
B) x
C) xyxyx
D) yx

... Answer is C)
xyxyx

3. Finite automatarequires minimum number of stacks.

A) 0
B) 1
C) 3
D) 4

... Answer is A)
0

4. Number of final state require to accept Φ in minimal finite automata.

A) 1
B) 2
C) 3
D) None of these

... Answer is D)
None of these

5. How many DFA’s exits with two states over input alphabet {a,b} ?

A) 64
B) 32
C) 16
D) 26

... Answer is A)
64

6. A Language for which no DFA exist is a

A) Non-Regular Language
B) Regular Language
C) May be Regular
D) None of these

... Answer is A)
Non-Regular Language

7. Which of the following option is correct?

A) NFA is slower to process and its representation uses less memory than DFA
B) NFA is slower to process and its representation uses more memory than DFA
C) DFA is faster to process and its representation uses less memory than NFA
D) DFAis slowertoprocessandits representationuses less memory thanNFA

... Answer is A)
NFA is slower to process and its representation uses less memory than DFA

8. Concatenation Operation refers to which of the following set operations

A) Dot
B) Union
C) Kleene
D) None of these

... Answer is A)
Dot

9.RR* can be expressed in which of the forms

A) R
B) R+ U R-
C) R-
D) R+

... Answer is D)
R+

10.What kind of expressions do we used for pattern matching?

A) Regular Expression
B) Rational Expression
C) Regular and RationalExpression
D) None of these

... Answer is C)
Regular and RationalExpression

11. If L1′ and L2′ are regular languages, then L1.L2 will be

A) may be regular
B) non regular
C) regular
C) None of these

... Answer is C)
regular

12. If L is a regular language, then (L’)’ U L will be

A) L*
B) L’
C) L
D) F

... Answer is C)
L

13. Generate a regular expression for the given language: L(x): {xÎ{0,1}*| x ends with 1 nd does not contain a substring 01}

A) (0+01)*1
B) (0+01)*
C) (0+01)*(1+01)
C) (1+01)*0

... Answer is C)
(0+01)*(1+01)

14. The entity which generate Language is termed as:

A) Automata
B) Tokens
C) Grammar
D) Data

... Answer is C)
Grammar

15. Which of the following statement is false?

A) Context sensitive language is a subset of context freelanguage
B) Context free language is the subset of context sensitive language
C) Recursively ennumerable language is the super set of regular language
C) Regular language is the subset of context sensitive language

... Answer is A)
Context sensitive language is a subset of context freelanguage

16. The Grammar can be defined as: G=(V, ∑, p, S) In the given definition, what does S represents?

A) Starting Variable
B) Accepting State
C) Sensitive Grammar
D) All the above

... Answer is A)
Starting Variable

17. Which among the following cannot be accepted by a regular grammar?

A) L is a set of numbers divisible by 2
B) L is a set of binary complement
C) L is a set of 0n1n
D) L is a set of string with odd number of 0

... Answer is C)
L is a set of 0n1n

18. A multi track turing machine can described as a 6-tuple (Q, X, S, d, q0, F) where X represents:

A) input alphabet
B) tape alphabet
C) shift symbols
D) None of these

... Answer is B)
tape alphabet

19. A turing machine has number of states in a CPU.

A) May be finite
B) finite
C) infinte
D) Not Known

... Answer is B)
finite

20. Which of the following is false for an abstract machine?

A) Turing machine
B) theoretical model of computer
C) assumes a discrete time paradigm
D) all of the mentioned

... Answer is D)
all of the mentioned

21.Turing machine can be represented using the following tools

A) Queue and Input tape
B) Transition table
C) Transition graph
D) all of the mentioned

... Answer is D)
all of the mentioned

22. The ability for a system of instructions to simulate a Turing Machine is called

A) Turing Completeness
B) Simulation
C) Turing Halting
D) None of these

... Answer is A)
Turing Completeness

23. A turing machine is a

A) more than one option is correct
B) real machine
C) abstract machine
D) hypothetical machine

... Answer is A)
more than one option is correct

24. There is a linear grammar that generates a context free grammar

A) always
B) sometimes
C) never
D) None of these

... Answer is B)
sometimes

25. A is context free grammar with atmost one non terminal in the right handside of the production.

A) linear grammar
B) linear bounded grammar
C) regular grammar
D) All of these

... Answer is A)
linear grammar

26. Context free languages are not closed under:

A) Complement
B) Intersection with Regular Language
C) Intersection
D) All of the mentioned

... Answer is D)
All of the mentioned

27. What does NP stands for in complexity classes theory?

A) Non-deterministic polynomial
B) Non polynomial
C) Both (a) and (b)
D) None of these

... Answer is A)
Non-deterministic polynomial

28. A generalization of P class can be:

A) NP
B) PTIME
C) DTIME
D) None of these

... Answer is A)
NP

29. The complexity class P consist of all the decision problems that can be solved by using polynomial amount of computation time.

A) Deterministic Turing machine
B) NDFA
C) DFA
D) PDA

... Answer is A)
Deterministic Turing machine

30. Which of the following cannot be solved using polynomial time?

A) Linear Programming
B) Greatest common divisor
C) Maximum matching
D) None of the mentioned

... Answer is D)
None of the mentioned

31. Which of the functions can a turing machine not perform?

A) Inserting a symbol
B) Accepting a pal
C) Deleting a symbol
D) Copying a string

... Answer is A)
Inserting a symbol

32. Which of the following can accept even palindrome over {a,b}

A) Push down Automata
B) Turing machine
C) NDFA
D) All of the mentioned

... Answer is C)
NDFA

33. An algorithm is called efficient if it runs in time on a serial computer

A) polynomial
B) non polynomial
C) logarithmic
D) None of these

... Answer is A)
polynomial

34. The decision problem is the function from string to

A) int
B) char
C) boolean
D) None of these

... Answer is C)
boolean

35. Grammar is checked by which component of compiler

A) Both Scanner and Sementic Analyser
B) Scanner
C) Parser
D) Semantic Analyzer

... Answer is A)
Both Scanner and Sementic Analyser

36. ______ is the acyclic graphical representation of a grammar.

A) Parse tree
B) Binary tree
C) Oct tree
D) Btree

... Answer is A)
Parse tree

37. A grammar with more than one parse tree is called

A) Regular
B) Unambiguous
C) Ambiguous
D) Reputed

... Answer is C)
Ambiguous

38. Which among the following is the root of the parse tree

A) Starting Variable S
B) Production P
C) Terminal T
D) Variable V

... Answer is A)
Starting Variable S

39. In which order are the children of any node ordered

A) Arbitrarily
B) From the right
C) From the left
D) None of these

... Answer is C)
From the left

40. The most suitable data structure used to represent the derivations in compiler

A) Tree
B) Queue
C) Linked List
D) Hash Tables

... Answer is A)
Tree

41. The entity which generate Language is termed as

A) Data
B) Tokens
C) Automata
D) Grammar

... Answer is D)
Grammar

« Previous Next »