Quiznetik

Theory of Computation | Set 1

1. = ∈{ } w has at least as many occurrences of (110)’s as (011)’s}. Let L {w 0,1 * 2 = ∈{ } w has at least as many occurrence of (000)’s as (111)’s}. Which one of the following is TRUE?

A. L1 is regular but not L2

B. L2 is regular but not L1

C. Both L1 and L2 are regular

D. Neither L1 nor L2 are regular

Correct : B. L2 is regular but not L1

2. A spanning tree for a simple graph of order 24 has

A. 12 edges

B. 6 edges

C. 23 edges

D. None of above.

Correct : C. 23 edges

3. If G is a simple connected 3-regular planar graph where every region is bounded by exactly 3 edges, then the edges of G is

A. 3

B. 4

C. 6

D. 5

Correct : C. 6

4. If G is a connected planar graph of v vertices e edges and r regions then

A. v-e+r=2

B. e-v+r=2

C. v+e-r=2

D. None of above.

Correct : A. v-e+r=2

5. A Hamiltonian cycle in a Hamiltonian graph of order 24 has

A. 12 edges.

B. 24 edges

C. 23 edges

D. None of above.

Correct : B. 24 edges

6. If G is a simple connected 3-regular planar graph where every region is bounded by exactly 3 edges, then the edges of G is

A. 3

B. 4

C. 6

D. 5

Correct : C. 6

7. The following grammar G = (N, T, P, S) N = {S, A, B} T = {a, b, c} P : S → aSa S → aAa A → bB B → bB B → c is

A. is type 3

B. is type 2 but not type 3

C. is type 1 but not type 2

D. is type 0 but not type 1

Correct : B. is type 2 but not type 3

8. The following grammar G = (N, T, P, S) N = {S, A, B, C, D, E} T = {a, b, c} P : S → aAB AB → CD CD → CE C → aC C → b bE → bc is

A. is type 3

B. is type 2 but not type 3

C. is type 1 but not type 2

D. is type 0 but not type 1

Correct : C. is type 1 but not type 2

9. The following grammar G = (N, T, P, S) N = {S, A, B, C} T = {a, b, c} P : S → aS A → bB B → cC C → a is

A. is type 3

B. is type 2 but not type 3

C. is type 1 but not type 2

D. is type 0 but not type 1

Correct : A. is type 3

10. P, Q, R are three languages. If P & R are regular and if PQ=R, then

A. Q has to be regular

B. Q cannot be regular

C. Q need not be regular

D. Q has to be a CFL

Correct : C. Q need not be regular

11. Which of the following is true with respect to Kleene’s theorem? 1 A regular language is accepted by a finite automaton. 2 Every language is accepted by a finite automaton or a turingmachine.

A. 1 only

B. 2 only

C. Both 1 and 2 are true statements

D. None is true

Correct : C. Both 1 and 2 are true statements

12. Automaton accepting the regular expression of any number of a ' s is:

A. a*

B. ab*

C. (a/b)*

D. a*b*c

Correct : A. a*

13. Grammars that can be translated to DFAs:

A. Left linear grammar

B. Right linear grammar

C. Generic grammar

D. All of these

Correct : B. Right linear grammar

14. Two strings x and y are indistinguishable if:

A. δ*(s, x) = δ* (s, y), i.e. the state reached by a DFA M on input x is the same as the state reached by M on input y

B. if for every string z Є ∑* either both xz and yz are in language A on ∑* or both xz and yz are not in A

C. Both above statements are true

D. None of the above

Correct : C. Both above statements are true

15. Given an arbitrary non-deterministic finite automaton NFA with N states, the maximum number of states in an equivalent minimized DFA is at least:

A. N2

B. 2N

C. 2N

D. N!

Correct : C. 2N

16. Regular expressions are

A. Type 0 language

B. Type 1 language

C. Type 2 language

D. Type 3 language

Correct : A. Type 0 language

17. The regular expression 0(10) denotes the same set as

A. (1*0)*1*

B. 0+(0+10)*

C. (0+1)*10(0+1)*

D. None of the above

Correct : B. 0+(0+10)*

18. Consider the NFA M shown below. Let the language accepted by M be L. Let L1 be the language accepted by the NFA M1, obtained by changing the accepting state of M to a non-accepting state and by changing the non-accepting state of M to accepting states. Which of the following statements is true?

A. L1 = {0,1}* − L

B. L1 = {0,1}*

C. L1 is a subset of L

D. L1 = L

Correct : A. L1 = {0,1}* − L

19. Which of the statements is true:

A. The complement of a regular language is always regular.

B. Homomorphism of a regular language is always regular.

C. Both of the above are true statements

D. None of the above

Correct : C. Both of the above are true statements

20. The regular sets are closed under:

A. Union

B. Concatenation

C. Kleene closure

D. All of the above

Correct : D. All of the above

21. Any given transition graph has an equivalent:

A. regular

B. DFSM (Deterministic Finite State Machine)

C. NDFSM

D. All of them

Correct : D. All of them

22. A language is regular if and only if

A. Accepted by DFA

B. Accepted by PDA

C. Accepted by LBA

D. Accepted by Turing machine

Correct : A. Accepted by DFA

23. Which of the following is not a regular expression?

A. [(a+b)*-(aa+bb)]*

B. [(0+1)-(0b+a1)*(a+b)]*

C. (01+11+10)*

D. (1+2+0)*(1+2)*

Correct : B. [(0+1)-(0b+a1)*(a+b)]*

24. Consider the regular language L = (111+111111)*. The minimum number of states inany DFA accepting this language is

A. 3

B. 5

C. 8

D. 9

Correct : D. 9

25. How many strings of length less than 4 contains the language described by the regular expression (x+y)y(a+ab)?

A. 7

B. 10

C. 12

D. 11

Correct : D. 11

26. Which of the following is TRUE?

A. Every subset of a regular set is regular

B. Every finite subset of a non-regular set is regular

C. The union of two non-regular sets is not regular

D. Infinite union of finite sets is regular

Correct : B. Every finite subset of a non-regular set is regular

27. The minimum state automaton equivalent to the above FSA has the following number of states

A. 1

B. 2

C. 3

D. 4

Correct : B. 2

28. Which one of the following languages over the alphabet {0,1} is described by the regular expression: (0+1)0(0+1)0(0+1)*?

A. The set of all strings containing the substring 00.

B. The set of all strings containing at most two 0’s.

C. The set of all strings containing at least two 0’s.

D. The set of all strings that begin and end with either 0 or 1.

Correct : C. The set of all strings containing at least two 0’s.

29. Let w be any string of length n is {0,1}*. Let L be the set of all substrings of w. What is the minimum number of states in a non-deterministic finite automaton that accepts L?

A. n-1

B. n

C. n+1

D. 2n-1

Correct : C. n+1

30. Which of the following are regular sets?

A. I and IV only

B. I and III only

C. I only

D. IV only

Correct : A. I and IV only

31. A minimum state deterministic finite automation accepting the language L={W W ε {0,1}*, number of 0s and 1s in are divisible by 3 and 5, respectively} has

A. 15 states

B. 11 states

C. 10 states

D. 9 states

Correct : A. 15 states

32. Let P be a regular language and Q be context-free language such that Q ∈ P. (For example, let P be the language represented by the regular expression pq and Q be {pnqn n∈ N}). Then which of the following is ALWAYS regular?

A. P ∩ Q

B. P – Q

C. ∑* – P

D. ∑* – Q

Correct : C. ∑* – P

33. Given a Non-deterministic Finite Automation (NFA) with states p and r as initial and final states respectively and transition table as given below: A B P - Q q R S r R S s R S The minimum number of states required in Deterministic Finite Automation (DFA) equivalent to NFA is

A. 5

B. 4

C. 3

D. 2

Correct : C. 3

34. Which one of the following statement is true for a regular language L over {a} whose minimal finite state automation has two states?

A. L must be either {an I n is odd} or {an I n is even}

B. L must be {an I n is odd}

C. L must be {an I n is even}

D. L must be {an I n = 0}

Correct : A. L must be either {an I n is odd} or {an I n is even}

35. The …………. is said to be ambiguous if there exist at least one word of its language that can be generated by the different production tree .

A. CFL

B. CFG

C. GTG

D. None of the given

Correct : B. CFG

36. Type-1 Grammar is known as_____________

A. CFG

B. CSG

C. REGULAR

D. All

Correct : B. CSG

37. If G is “S → a S/a”, then L(G) = ?

A. a*

B. ^

C. {a}+

D. Both (a) & (c)

Correct : C. {a}+

38. “S →a S”, what is the type of this production?

A. Type 0

B. Type 1

C. Type 2

D. Type 3

Correct : D. Type 3

39. A→abA a type __________productions

A. Type 0

B. Type 1

C. Type 2

D. Type 3

Correct : B. Type 1

40. The following CFG is in S → ABspaceB → CDspaceB → ADspaceB → bspaceD → ADspaceD → dspaceA → a**spaceC → a

A. Chomsky normal form but not strong Chomsky normal form

B. Weak Chomsky normal form but not Chomsky normal form

C. Strong Chomsky normal form

D. Greibach normal form

Correct : C. Strong Chomsky normal form

41. The language accepted by a Push down Automata:

A. Type0

B. Type1

C. Type2

D. Type3

Correct : C. Type2

42. Which of the following problems is undecidable?

A. Membership problem for CFGs

B. Ambiguity problem for CFGs

C. Finiteness problem for Finite state automata FSAs

D. Equivalence problem for FSAs

Correct : B. Ambiguity problem for CFGs

43. Which one of the following statement is FALSE?

A. context-free languages are closed under union

B. context-free languages are closed under concatenation

C. context-free languages are closed under intersection

D. context-free languages are closed under Kleene closure

Correct : C. context-free languages are closed under intersection

44. Which of the following statement is wrong?

A. Any regular language can be generated by a context-free grammar

B. Some non-regular languages cannot be generated by any CFG

C. the intersection of a CFL and regular set is a CFL

D. All non-regular languages can be generated by CFGs.

Correct : D. All non-regular languages can be generated by CFGs.

45. Which of the following strings is not generated by the following grammar? S → SaSbS ε

A. aabb

B. abab

C. aababb

D. aaabb

Correct : D. aaabb

46. Which of the following regular expression identity is true?

A. r(*) = r*

B. (r*s*)* = (r + s)*

C. (r + s)* = r* + s*

D. r*s* = r* + s*

Correct : B. (r*s*)* = (r + s)*

47. A language L is accepted by a FSA iff it is

A. CFL

B. CSL

C. Recursive

D. Regular

Correct : D. Regular

48. Consider the following CFG S → aB S → bAspaceB → b A → aspaceB → bS A → aSspaceB → aBB A → bAAspace Consider the following derivation spaceS ⇒aBspace⇒aaBBspace⇒aaBbspace⇒aabSbspace⇒aabbAbspace⇒aabbab**space This derivation is

A. A leftmost derivation

B. A rightmost derivation

C. Both leftmost and rightmost derivation

D. Neither leftmost nor rightmost derivation

Correct : D. Neither leftmost nor rightmost derivation

49. Consider the following language L = {anbncndn n ≥ 1} L is

A. CFL but not regular

B. CSL but not CFL

C. Regular

D. Type 0 language but not type 1

Correct : B. CSL but not CFL

50. A language is represented by a regular expression (a)*(a + ba). Which of the following strings does not belong to the regular set represented by the above expression?

A. aaa

B. aba

C. abab

D. aa

Correct : C. abab

51. Which of the following denotes Chomskianhiearchy?

A. REG ⊂ CFL ⊂ CSL ⊂ type0

B. CFL ⊂ REG ⊂ type0 ⊂ CSL

C. CSL ⊂ type0 ⊂ REG ⊂ CFL

D. CSL ⊂ CFL ⊂ REG ⊂ type0

Correct : A. REG ⊂ CFL ⊂ CSL ⊂ type0

52. The concept of FSA is much used in this part of the compiler

A. Lexical analysis

B. Parser

C. Code generation

D. Code optimization

Correct : A. Lexical analysis

53. The following grammar G = (N, T, P, S)spaceN = {S, A, B, C, D, E}spaceT = {a, b, c}spaceP : S → aABspaceAB → CDspaceCD → CEspaceC → aCspaceC → bspacebE → bc is

A. is type 3

B. is type 2 but not type 3

C. is type 1 but not type 2

D. is type 0 but not type 1

Correct : C. is type 1 but not type 2

54. The following CFG is in S → aBBspaceB → bAAspaceA → a**spaceB → b

A. Chomsky normal form but not strong Chomsky normal form

B. Weak Chomsky normal form but not Chomsky normal form

C. Strong Chomsky normal form

D. Greibach normal form

Correct : D. Greibach normal form

55. Which of the following statements is wrong?

A. The regular sets are closed under intersection

B. The class of regular sets is closed under substitution

C. The class of regular sets is closed under homomorphism

D. Context Sensitive Grammar(CSG) can be recognized by Finite State Machine

Correct : D. Context Sensitive Grammar(CSG) can be recognized by Finite State Machine

56. Context free grammar is not closed under

A. Product operation

B. Union

C. Complementation

D. kleene star

Correct : C. Complementation

57. Let the class of language accepted by finite state machine be L1 and the class of languages represented by regular expressions be L2 then

A. L1

B. L1>=L2

C. L1 U L2 = .*

D. L1=L2

Correct : D. L1=L2

58. Which of the following statement is wrong?

A. Any regular language has an equivalent context-free grammar.

B. Some non-regular languages can’t be generated by any context-free grammar

C. Intersection of context free language and a regular language is always context-free

D. All languages can be generated by context- free grammar

Correct : D. All languages can be generated by context- free grammar

59. Grammar that produce more than one Parse tree for same sentence is:

A. Ambiguous

B. Unambiguous

C. Complementation

D. Concatenation

Correct : A. Ambiguous

60. The language accepted by a Push down Automata:

A. Type 0

B. Type 1

C. Type 2

D. Type 3

Correct : C. Type 2

61. The PDA is called non-deterministic PDA when there are more than one out going edges from……… state:

A. START or READ

B. POP or REJECT

C. READ or POP

D. PUSH or POP

Correct : C. READ or POP

62. Let L be a language defined over an alphabet ∑,then the language of strings , defined over ∑, not belonging to L denoted by LC or L. is called :

A. Non regular language of L

B. Complement of the language L

C. None of the given

D. All of above

Correct : B. Complement of the language L

63. All NonNull words of the CFL can be generated by the corresponding CFG which is in CNF i.e the grammar in CNF will generate the same language except the:

A. String

B. Regular language

C. Null string

D. None of the above

Correct : C. Null string

64. Let L={w (0 + 1)* w has even number of 1s}, i.e. L is the set of all bit strings with even number of 1s. Which one of the regular expression below represents L?

A. (0*10*1)*

B. 0*(10*10*)*

C. 0*(10*1*)*0*

D. 0*1(10*1)*10*

Correct : B. 0*(10*10*)*

65. Consider the following Finite State Automaton The language accepted by this automaton is given by the regular expression

A. b*ab*ab*ab

B. (a+b)*

C. b*a(a+b)*

D. b*ab*ab

Correct : C. b*a(a+b)*

66. Let L1 be a recursive language. Let L2 and L3 be languages that are recursively enumerable but not recursive. Which of the following statements is not necessarily true?

A. L2-L1 is recursively enumerable

B. L1-L3 is recursively enumerable

C. L2 intersection L1 is recursively enumerable

D. L2 union L1 is recursively enumerable

Correct : B. L1-L3 is recursively enumerable

67. Let L denotes the language generated by the grammar S – OSO/00. Which of the following is true?

A. L = O

B. L is regular but not O

C. L is context free but not regular

D. L is not context free

Correct : B. L is regular but not O

68. Let S and T be language over ={a,b} represented by the regular expressions (a+b) and (a+b)*, respectively. Which of the following is true?

A. ScT (S is a subset of T)

B. TcS (T is a subset of S)

C. S=T

D. SnT=Ø

Correct : C. S=T

69. Which of the following pairs have DIFFERENT expressive power?

A. Deterministic finite automata (DFA) and Non-Deterministic finite automata(NFA)

B. Deterministic push down automata (DPDA) and Non-deterministic pushdown automata

C. Deterministic single-tape Turing machine and Non-deterministic single-tape Turing Machine

D. Single-tape Turing machine and multi-tape Turing machine

Correct : B. Deterministic push down automata (DPDA) and Non-deterministic pushdown automata

70. Match all items in Group 1 with correct options from those given in Group 2. List I List IIspaceP. Regular Expression 1. Syntax analysisspaceQ. Push down automata 2. Code GenerationspaceR. Dataflow analysis 3. Lexical analysisspaceS. Register allocation 4. Code optimization

A. P-4, Q-1, R-2, S-3

B. P-3, Q-1, R-4, S-2

C. P-3, Q-4, R-1, S-2

D. P-2, Q-1, R-4, S-3

Correct : B. P-3, Q-1, R-4, S-2

71. A minimum state deterministic finite automation accepting the language L = {W W € {0,1}* , number of 0's and 1's in W are divisible by 3 and 5 respectively has

A. 15 states

B. 11 states

C. 10 states

D. 9 states

Correct : A. 15 states

72. Any Language generated by an unrestricted grammar is:

A. Recursive

B. Recursively Enumerable

C. Not Recursive

D. None of the above

Correct : A. Recursive

73. The Family of recursive language is not closed under which of the following operations:

A. Union

B. Intersection

C. Complementation

D. None of the above.

Correct : D. None of the above.

74. PCP is:

A. Decidable

B. Undecidable

C. Sometimes Decidable

D. None of the

Correct : B. Undecidable

75. If PCP is decidable then MPCP is

A. Decidable

B. Undecidable

C. Can’t Say

D. None of the

Correct : C. Can’t Say

76. Consider a language L for which there exists a Turing machine ™, T, that accepts every word in L and either rejects or loops for every word that is not in L. The language L is

A. NP hard

B. NP complete

C. Recursive

D. Recursively enumerable

Correct : D. Recursively enumerable

77. 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 statement are TRUE?

A. I only

B. I and II

C. I and III

D. II and III

Correct : B. I and II

78. Recursively enumerable languages are not closed under

A. Union

B. homomorphism

C. complementation

D. concatenation

Correct : C. complementation

79. Which of the following problem is undecidable?

A. Membership problem for CFL

B. Membership problem for regular sets

C. Membership problem for CSL

D. Membership problem for type 0 languages

Correct : D. Membership problem for type 0 languages

80. Recursive languages are

A. A proper superset of CFL

B. Always recognized by PDA

C. Are also called type 0 languages

D. Always recognized by FSA

Correct : A. A proper superset of CFL

81. Consider the following problem x. Given a Turing machine M over the input alphabet Σ, any state q of M. And a word w Є Σ*, does the computation of M on w visit the state q? Which of the following statements about x is correct?

A. X is decidable

B. X is undecidable but partially decidable

C. X is undecidable and not even partially decidable

D. X is not a decision problem

Correct : A. X is decidable

82. 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. yx

B. xyx

C. x

D. xyxyx

Correct : D. xyxyx

83. Given A = {0,1} and L = A*. If R = (0n1n, n > 0), then language L ∪ R and R are respectively

A. Regular, regular

B. Not regular, regular

C. Regular, not regular

D. Context free, not regular

Correct : D. Context free, not regular

84. If L1 and L2 are context free language and R a regular set, then which one of the languages below is not necessarily a context free language?

A. L1 L2

B. L1 ∩ L2

C. L1 ∩ R

D. L1 ∪ L2

Correct : B. L1 ∩ L2

85. The logic of pumping lemma is a good example of

A. Pigeon-hole principle

B. Divide-and-conquer technique

C. Recursion

D. Iteration

Correct : A. Pigeon-hole principle

86. For two regular languages L1 = (a + b)* a and L2 = b (a + b ) *, the intersection of L1 and L2 is given by

A. (a + b ) * ab

B. ab (a + b ) *

C. a ( a + b ) * b

D. b (a + b ) * a

Correct : D. b (a + b ) * a

87. Pumping lemma is generally used for proving that

A. Given grammar is regular

B. Given grammar is not regular

C. Whether two given regular expressions are equivalent or not

D. None of these

Correct : B. Given grammar is not regular

88. What is the highest type number which can be applied to the following grammar? S —>Aa, A —> Ba, B —>abc

A. Type 0

B. Type 1

C. Type 2

D. Type 3

Correct : C. Type 2

89. Following syntax-directed translation scheme is used with a shift reduction (bottom up) parser that perform the action in braces immediately after a reduction by the corresponding production A —>aB {print “(1)” A —> c {print “1”), B —>Ab {print *2”}. When parser is aaacbbb, then string printed

A. 0202021

B. 1202020

C. 1020202

D. None of these

Correct : A. 0202021

90. FSM can recognize

A. Any grammar

B. Only CG

C. Both (a) and ( b )

D. Only regular grammar

Correct : D. Only regular grammar

91. Basic limitation of FSM is that it

A. Cannot remember arbitrary large amount of information

B. Sometimes fails to recognize grammars that are regular

C. Sometimes recognizes grammars are not regular

D. None of these

Correct : A. Cannot remember arbitrary large amount of information

92. Which of the following are decidable? 1) Whether the intersection of two regular language is infinite. 2) Whether a given context free language is regular. 3) Whether two push down automata accept the same language. 4) Whether a given grammar is context free.

A. 1 and 2

B. 1 and 4

C. 2 and 3

D. 2 and 4

Correct : B. 1 and 4

93. If L and L¯ are recursively enumerable, then L is

A. Regular

B. Context free

C. Context sensitive

D. Recursive

Correct : D. Recursive

94. Which of the following problems is undecidable?

A. Membership problem for CFGs

B. Ambiguity problem for CFGs.

C. Finiteness problem for FSAs.

D. Equivalence problem for FSAs.

Correct : B. Ambiguity problem for CFGs.

95. 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)

A. Context Free Language

B. Context sensitive language

C. Regular language

D. Languages recognizable by Turing machine

Correct : D. Languages recognizable by Turing machine

96. 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.

A. 1 and 4 only

B. 1 and 3 only

C. 2 only

D. 3 only

Correct : C. 2 only

97. Consider a string s over (0+1)*. The number of 0’s in s is denoted by no(s) and the number of 1’s in s is denoted by n1(s). The language that is not regular is

A. L = {s ε (0+1)* I for every prefix s’ of s, I no(s’)-n1(s’) I ≤ 2}

B. L = {s ε (0+1)* I no(s) mod 7 = n1(s) mod 5 = 0}

C. L = {s ε (0+1)* I no(s) is a 3 digit prime}

D. L = {s ε (0+1)* I no(s)-n1(s) I ≤ 4

Correct : D. L = {s ε (0+1)* I no(s)-n1(s) I ≤ 4

98. Which one of the following is true regarding FOTRAN?

A. It is a context free language

B. It is a context sensitive language

C. It is a regular language

D. None of the above

Correct : B. It is a context sensitive language

99. Which statement is true?

A. The PDA must have one accept state and one reject state

B. The PDA must have one accept state and two reject state

C. The PDA must have two accept state and two reject state

D. There is no reject state in the PDA.

Correct : D. There is no reject state in the PDA.

100. TM is more powerful than FSM because

A. The tape movement is confined to one direction

B. It has no finite state control

C. It has the capability to remember arbitrary long sequences of input symbols

D. None of these

Correct : B. It has no finite state control

Quiznetik

Theory of Computation | Set 1

1. = ∈{ } w has at least as many occurrences of (110)’s as (011)’s}. Let L {w 0,1 * 2 = ∈{ } w has at least as many occurrence of (000)’s as (111)’s}. Which one of the following is TRUE?

2. A spanning tree for a simple graph of order 24 has

3. If G is a simple connected 3-regular planar graph where every region is bounded by exactly 3 edges, then the edges of G is

4. If G is a connected planar graph of v vertices e edges and r regions then

5. A Hamiltonian cycle in a Hamiltonian graph of order 24 has

6. If G is a simple connected 3-regular planar graph where every region is bounded by exactly 3 edges, then the edges of G is

7. The following grammar G = (N, T, P, S) N = {S, A, B} T = {a, b, c} P : S → aSa S → aAa A → bB B → bB B → c is

8. The following grammar G = (N, T, P, S) N = {S, A, B, C, D, E} T = {a, b, c} P : S → aAB AB → CD CD → CE C → aC C → b bE → bc is

9. The following grammar G = (N, T, P, S) N = {S, A, B, C} T = {a, b, c} P : S → aS A → bB B → cC C → a is

10. P, Q, R are three languages. If P & R are regular and if PQ=R, then

11. Which of the following is true with respect to Kleene’s theorem? 1 A regular language is accepted by a finite automaton. 2 Every language is accepted by a finite automaton or a turingmachine.

12. Automaton accepting the regular expression of any number of a ' s is:

13. Grammars that can be translated to DFAs:

14. Two strings x and y are indistinguishable if:

15. Given an arbitrary non-deterministic finite automaton NFA with N states, the maximum number of states in an equivalent minimized DFA is at least:

16. Regular expressions are

17. The regular expression 0*(10)* denotes the same set as

18. Consider the NFA M shown below. Let the language accepted by M be L. Let L1 be the language accepted by the NFA M1, obtained by changing the accepting state of M to a non-accepting state and by changing the non-accepting state of M to accepting states. Which of the following statements is true?

19. Which of the statements is true:

20. The regular sets are closed under:

21. Any given transition graph has an equivalent:

22. A language is regular if and only if

23. Which of the following is not a regular expression?

24. Consider the regular language L = (111+111111)*. The minimum number of states inany DFA accepting this language is

25. How many strings of length less than 4 contains the language described by the regular expression (x+y)*y(a+ab)*?

26. Which of the following is TRUE?

27. The minimum state automaton equivalent to the above FSA has the following number of states

28. Which one of the following languages over the alphabet {0,1} is described by the regular expression: (0+1)*0(0+1)*0(0+1)*?

29. Let w be any string of length n is {0,1}*. Let L be the set of all substrings of w. What is the minimum number of states in a non-deterministic finite automaton that accepts L?

30. Which of the following are regular sets?

31. A minimum state deterministic finite automation accepting the language L={W W ε {0,1}*, number of 0s and 1s in are divisible by 3 and 5, respectively} has

32. Let P be a regular language and Q be context-free language such that Q ∈ P. (For example, let P be the language represented by the regular expression p*q* and Q be {pnqn n∈ N}). Then which of the following is ALWAYS regular?

33. Given a Non-deterministic Finite Automation (NFA) with states p and r as initial and final states respectively and transition table as given below: A B P - Q q R S r R S s R S The minimum number of states required in Deterministic Finite Automation (DFA) equivalent to NFA is

34. Which one of the following statement is true for a regular language L over {a} whose minimal finite state automation has two states?

35. The …………. is said to be ambiguous if there exist at least one word of its language that can be generated by the different production tree .

36. Type-1 Grammar is known as_____________

37. If G is “S → a S/a”, then L(G) = ?

38. “S →a S”, what is the type of this production?

39. A→abA a type __________productions

40. The following CFG is in S → AB**spaceB → CD**spaceB → AD**spaceB → b**spaceD → AD**spaceD → d**spaceA → a**spaceC → a

41. The language accepted by a Push down Automata:

42. Which of the following problems is undecidable?

43. Which one of the following statement is FALSE?

44. Which of the following statement is wrong?

45. Which of the following strings is not generated by the following grammar? S → SaSbS ε

46. Which of the following regular expression identity is true?

47. A language L is accepted by a FSA iff it is

48. Consider the following CFG S → aB S → bA**spaceB → b A → a**spaceB → bS A → aS**spaceB → aBB A → bAA**space Consider the following derivation **spaceS ⇒aB**space⇒aaBB**space⇒aaBb**space⇒aabSb**space⇒aabbAb**space⇒aabbab**space This derivation is

49. Consider the following language L = {anbncndn n ≥ 1} L is

50. A language is represented by a regular expression (a)*(a + ba). Which of the following strings does not belong to the regular set represented by the above expression?

51. Which of the following denotes Chomskianhiearchy?

52. The concept of FSA is much used in this part of the compiler

53. The following grammar G = (N, T, P, S)**spaceN = {S, A, B, C, D, E}**spaceT = {a, b, c}**spaceP : S → aAB**spaceAB → CD**spaceCD → CE**spaceC → aC**spaceC → b**spacebE → bc is

54. The following CFG is in S → aBB**spaceB → bAA**spaceA → a**spaceB → b

55. Which of the following statements is wrong?

56. Context free grammar is not closed under

57. Let the class of language accepted by finite state machine be L1 and the class of languages represented by regular expressions be L2 then

58. Which of the following statement is wrong?

59. Grammar that produce more than one Parse tree for same sentence is:

60. The language accepted by a Push down Automata:

61. The PDA is called non-deterministic PDA when there are more than one out going edges from……… state:

62. Let L be a language defined over an alphabet ∑,then the language of strings , defined over ∑, not belonging to L denoted by LC or L. is called :

63. All NonNull words of the CFL can be generated by the corresponding CFG which is in CNF i.e the grammar in CNF will generate the same language except the:

64. Let L={w (0 + 1)* w has even number of 1s}, i.e. L is the set of all bit strings with even number of 1s. Which one of the regular expression below represents L?

65. Consider the following Finite State Automaton The language accepted by this automaton is given by the regular expression

66. Let L1 be a recursive language. Let L2 and L3 be languages that are recursively enumerable but not recursive. Which of the following statements is not necessarily true?

67. Let L denotes the language generated by the grammar S – OSO/00. Which of the following is true?

68. Let S and T be language over ={a,b} represented by the regular expressions (a+b*)* and (a+b)*, respectively. Which of the following is true?

69. Which of the following pairs have DIFFERENT expressive power?

70. Match all items in Group 1 with correct options from those given in Group 2. List I List II**spaceP. Regular Expression 1. Syntax analysis**spaceQ. Push down automata 2. Code Generation**spaceR. Dataflow analysis 3. Lexical analysis**spaceS. Register allocation 4. Code optimization

71. A minimum state deterministic finite automation accepting the language L = {W W € {0,1}* , number of 0's and 1's in W are divisible by 3 and 5 respectively has

72. Any Language generated by an unrestricted grammar is:

73. The Family of recursive language is not closed under which of the following operations:

74. PCP is:

75. If PCP is decidable then MPCP is

76. Consider a language L for which there exists a Turing machine ™, T, that accepts every word in L and either rejects or loops for every word that is not in L. The language L is

77. 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 statement are TRUE?

78. Recursively enumerable languages are not closed under

17. The regular expression 0(10) denotes the same set as

25. How many strings of length less than 4 contains the language described by the regular expression (x+y)y(a+ab)?

28. Which one of the following languages over the alphabet {0,1} is described by the regular expression: (0+1)0(0+1)0(0+1)*?

32. Let P be a regular language and Q be context-free language such that Q ∈ P. (For example, let P be the language represented by the regular expression pq and Q be {pnqn n∈ N}). Then which of the following is ALWAYS regular?

40. The following CFG is in S → ABspaceB → CDspaceB → ADspaceB → bspaceD → ADspaceD → dspaceA → a**spaceC → a

48. Consider the following CFG S → aB S → bAspaceB → b A → aspaceB → bS A → aSspaceB → aBB A → bAAspace Consider the following derivation spaceS ⇒aBspace⇒aaBBspace⇒aaBbspace⇒aabSbspace⇒aabbAbspace⇒aabbab**space This derivation is

53. The following grammar G = (N, T, P, S)spaceN = {S, A, B, C, D, E}spaceT = {a, b, c}spaceP : S → aABspaceAB → CDspaceCD → CEspaceC → aCspaceC → bspacebE → bc is

54. The following CFG is in S → aBBspaceB → bAAspaceA → a**spaceB → b

68. Let S and T be language over ={a,b} represented by the regular expressions (a+b) and (a+b)*, respectively. Which of the following is true?

70. Match all items in Group 1 with correct options from those given in Group 2. List I List IIspaceP. Regular Expression 1. Syntax analysisspaceQ. Push down automata 2. Code GenerationspaceR. Dataflow analysis 3. Lexical analysisspaceS. Register allocation 4. Code optimization