# THEORY OF COMPUTATION MCQ SET-5

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={abk|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