THEORY OF COMPUTATION MCQ SET 3

This entry was posted in THEORY OF COMPUTATION MCQ on by

 

  1. Given the language L-{ab, aa, baa}, which of the following strings are in L*?

1) abaabaaabaa

2) aaaabaaaa

3) baaaaabaaaab

4) baaaaabaa

 

  1,2 and 3
  2,3 and 4
  1,2 and 4
  1,3 and 4

      _____________________________________________________________________________________
2.  Push down machine represents

  Type 0 Grammar
  Type 1 grammar
  Type-2 grammar
  Type-3 grammar

      _____________________________________________________________________________________
3. The behavior of a NFA can be stimulated by DFA 

  always
  sometimes
  never
  depend on NFA

  
4. Which of the following is not primitive recursive but partially recursive? 

  Carnot function
  Rieman function
  Bounded function
  Ackermann function

      _____________________________________________________________________________________
 

5. Consider the following grammar.

S ::= AB

A ::= a

A ::= BaB

B ::= bbA

Which of the following is false?

 

  No string produced by the grammar has four consecutive b s
  No string produced by the grammar has three consecutive a s
  No string produced by the grammar has an odd number of consecutive b s
  The length of every string produced by the grammar is even.

      _____________________________________________________________________________________
6. Set of regular languages over a given alphabet set,is not closed under 

  Union
  Complementation
  Intersection
  None of the above

      _____________________________________________________________________________________
7. Consider the regular expression (a + b) (a + b) … (a + b) (n-times). The minimum number of states in finite automaton that recognizes the language represented by this regular expression contains

  n states
  n + 1 states
  n + 2 states
  2n states

      _____________________________________________________________________________________
8. The logic of pumping lemma is a good example of 
  The pigeon hole principle
  Divide and conquer method
  Iteration
  Recursion

      _____________________________________________________________________________________
9. If every string of a language can be determined whether it is legal or illegal in finite time the language is called 

  Decidable
  Undecidable
  Interpretive
  Non deterministic

      _____________________________________________________________________________________
10. Context free language can be recognized by 

  Finite State Automaton
  Linear bounded automaton
  Pushdown automaton
  Both B and C

      _____________________________________________________________________________________
11. Fred created a new automaton model which is a push down automaton but with two stacks and the added ability of having commands which do not read input tape but which can pop from one stack and push into the other.This new automaton can recognize (choose strongest result)

  Context free language
  Context sensitive language
  Regular language
  Languages recognizable by Turing machine

      _____________________________________________________________________________________
 

12. Given the following productions of a grammar :

 

  The language corresponding to the given grammar is a set of even number of a s.
  The language corresponding to the given grammar is a set of odd number of a s.
  The language corresponding to the given grammar is a set of even number of a’s followed by odd number of b s.
  The language corresponding to the given grammar is a set of odd number of a’s followed by even number of b s.

      _____________________________________________________________________________________
13. FSM can recognize 

  Any grammar
  Only CFG
  Any unambiguous grammar
  Only regular grammar

      _____________________________________________________________________________________
 

14. Assume statements S1 and S2 defined as :

S1 : L2-L1 is recursive enumerable where L1 and L2 are recursive and recursive enumerable respectively.

S2 : The set of all Turing machines is countable. 

Which of the following is true ?

 

  S1 is correct and S2 is not correct.
  Both S1 and S2 are correct.
    Both S1 and S2 are not correct.
S1 is not correct and S2 is correct.

      _____________________________________________________________________________________
15. Which of the following is the most general phase structured grammar ?

  Regular
  Context-sensitive
  Context free
  None of the above

      _____________________________________________________________________________________
16. A FSM can be used to add how many given integers? 

  1
  3
  4
  5

      _____________________________________________________________________________________
17. Consider the following statements :
I. Recursive languages are closed under complementation.
II. Recursively enumerable languages are closed under union.
III. Recursively enumerable languages are closed under complementation.
Which of the above statements are true ?

  I only
  I and II
  I and III
  I and III

      _____________________________________________________________________________________
18.  6 Files F1,F2,F3,F4,F5 and F6 have 100,200,50,80,120,150 records repectively.

In what order should they be sorted so as to optimize activity? Assume each file is accessed with the same frequency.

 

  F3,F4,F1,F5,F6,F2
  F2,F6,F5,F1,F4,F3
  F1,F2,F3,F4,F5,F6
  Ordering is immaterial as all files are accessed with the same frequency

      _____________________________________________________________________________________
19. Following grammar

S-> bS

S -> b

S -> aA

A -> bA

 

  Type -3 grammar
  Type -2 grammar
  Type -1 grammar
  Type -0 grammar

      _____________________________________________________________________________________
 

20. Which of the following problems are decidable?

1) Does a given program ever produce an output?

2) If L is context-free language, then, is ~L also context-free?

3) If L is regular language, then, is ~L also regular?

4) If L is recursive language, then, is ~L also recursive?

 

  1,2,3,4
  1,2
  2,3,4
  3,4

      _____________________________________________________________________________________
21. The language L={ak bk|k>=1} is

  Type -3 Grammar
  Type -2 Grammar
  Type -1 Grammar
  Type -0 Grammar

      _____________________________________________________________________________________
22. All strings having equal number of a and b can be recognized by 

  DFA
  NDFA
  PDA
  All of these

      _____________________________________________________________________________________
23. The basic limitation of a FSM is that 

  It cannot remember arbitrary large amount of information
  It sometimes recognizes grammar that are not regular
  It sometimes fails to recognize grammars that are regular
  All of the above

      _____________________________________________________________________________________
24. How many states can a process be in ?

  2
  3
  4
  5

      _____________________________________________________________________________________
25. Which one of the following statement is false ?

  Context-free languages are closed under union
  Context-free languages are closed under concatenation
  Context-free languages are closed under intersection
  Context-free languages are closed under Kleene closure

      _____________________________________________________________________________________
26. Given the language L = {ab, aa, baa}, which of the following strings are in L*?
1) abaabaaabaa
2) aaaabaaaa
3) baaaaabaaaab
4) baaaaabaa

  1, 2 and 3
  2, 3 and 4
  1, 2 and 4
  1, 3 and 4

      _____________________________________________________________________________________
27. Which is not the correct statement(s) ?
(i) Every context sensitive language is recursive.
(ii) There is a recursive language that is not context sensitive.

  (i) is true, (ii) is false.
  (i) is true and (ii) is true.
  (i) is false, (ii) is false.
  (i) is false and (ii) is true.

      _____________________________________________________________________________________
28. A formal grammar is a___________for rewriting strings. 

  Set of rules
  Set of functions
  Both A and B
  None of the above

      _____________________________________________________________________________________
29. Finite automata are used for pattern matching in text editors for 

  Compiler lexical analysis
  Programming in localized application
  Both A and B
  None of the above

      _____________________________________________________________________________________
30.Two finite states are equivalent if they 

  Have same number of states
  Have same number of edges
  Have same number of states and edges
  Recognize same set of tokens

      _____________________________________________________________________________________
31. A PDM behaves like a TM when the number of auxiliary memory it has is 

  Zero
  One or more
  Two or more
  None of these

      _____________________________________________________________________________________
32. Which of the following permanent database that has an entry for each terminal symbol ?

  Literal table
  Identifier table
  Terminal table
  Source table

      _____________________________________________________________________________________
33. The language accepted by finite automata is 

  Context free
  Regular
  Non regular
  None of these

      _____________________________________________________________________________________
34. The following CFG
S®aB|bA, A®a|as|bAA, B®b|bs|aBB
generates strings of terminals that have

  Odd number of a’s and odd number of b’s
  Even number of a’s and even number of b’s
  Equal number of a’s and b’s
  Not equal number of a’s and b’s

      _____________________________________________________________________________________
35. An FSM can be used to add two given integers.This remark is 

  True
  False
  May be true
  None of the above

      _____________________________________________________________________________________
36. Context free languages are not closed under 

  Union
  Concatenation
  Closure
  Iteration

      _____________________________________________________________________________________
37. Which of the following is most powerful? 
  DFA
  NDFA
  2PDA
  DPDA

      _____________________________________________________________________________________
38. Which of the following statements is/are FALSE?
(1) For every non-deterministic Turing machine, there exists an equivalent deterministic Turing machine.
(2) Turing recognizable languages are closed under union and complementation.
(3) Turing decidable languages are closed under intersection and complementation
(4) Turing recognizable languages are closed under union and intersection.

  1 and 4 only
  1 and 3 only
  2 only
  3 only

      _____________________________________________________________________________________
39. Finite state machine___________recognize palindromes. 

  Can
  Cannot
  May
  May not

      _____________________________________________________________________________________
40. Given L1=L(a*baa*) and L2=L(ab*). The regular expression corresponding to language L3 = L1/L2 (right quotient) is given by

  a*b
  a*baa*
  a*ba*
  None of the above

      _____________________________________________________________________________________
41. If two finite state machines are equivalent they should have the same number of 

  States
  Edges
  States and edges
  None of these

 

Leave a comment