VU Final Term Past Papers
274 solved final term past paper MCQs for CS402 (Theory of Automata) at Virtual University, each with the correct answer marked. Use them to learn the VU question style and test your recall. An independent study tool — not affiliated with VU.
Prefer a summary first? Read the CS402 final term handout.
Q1. According to 1st part of the Kleene‟s theorem, If a language can be accepted by an FA then it can be accepted by a ________ as well.
Q2. Even-palindrome is a _______ language.
Q3. If L is a regular language then, Lc is also a _ language.
Q4. Pumping lemma is generally used to prove that:
Q5. In CFG, the symbols that can’t be replaced by anything are called .
Q6. Which of the following is a regular language?
Q7. An alphabet of Σ is valid if
Q8. We can also represent an FA using different states e.g Accept state; Reject state, Read state etc. The state behaves as final state of an FA
Q9. The first rule of converting the given “CFG in CNF”, is
Q10. We cannot write regular expressions for all .
Q11. For every Context Free Grammar (CFG), we can make the corresponding ______.
Q12. Pumping Lemma II says that length(x) + length(y) should be .
Q13. Chomsky normal form (CYK) algorithm was proposed by .
Q14. The language of Palindromes defined over an alphabet set {a, b} can be recognized by ______.
Q15. Which of the following is the first phase of compiler on the basis of functionality?
Q16. (Σ* - L) represent the _ of a language L.
Q17. If L1 and L2 are expressed by regular languages then L1 + L2 is also a Language.
Q18. A read state can have _ outgoing edge/ edges.
Q19. Who did not invent the Turing machine?
Q20. Which statement is true?
Q21. Every regular expression can be expressed as CFG but every CFG cannot be expressed as a regular expression. This statement is:
Q22. The word „formal‟ in formal languages means
Q23. Choose the correct statement.
Q24. TM is more powerful than FSM because
Q25. Like TG, a PDA can also be non-deterministic
Q26. Which of the following is NOT a regular language?
Q27. Left hand side of a production in CFG consists of:
Q28. PDA is only used to represent a regular language.
Q29. A production of the form non-terminal string of two non- terminal is called a live Production.
Q30. We can find a CFG corresponding to a DFA.
Q31. START, READ, HERE and ACCEPTS are conversions of the machine
Q32. A CFG is said to be ambiguous if there exists at least one word of its language that can be generated by different production trees
Q33. Syntax tree or Generation tree or Derivation tree are same tree
Q34. The symbols that cannot be replaced by anything are called terminals
Q35. The production of the form non-terminal one non-terminal is called unit production
Q36. DFA and PDA are equal in power.
Q37. A production of the form non-terminal non-terminal is called a dead Production.
Q38. Semi-word is a string having some terminals and one non- terminal at the right of string.
Q39. Two FAs are equivalent if they have same no. of states.
Q40. There exist exactly two different derivations in an ambiguous CFG for a word.
Q41. Regular languages are closed under Union, Concatenation and Kleene star.
Q42. CFG may also represent a regular language.
Q43. PDA is stronger than FA.
Q44. A Total Language Tree has
Q45. Set of all palindromes over {a,b}is regular
Q46. In CFG, the symbols that cannot be replaced by anything are called
Q47. The grammatical rules which involves meaning of words are called:
Q48. Two languages are said to belong to same class if they end in the same state when they run over an FA, that state
Q49. In pref(Q in R) Q is to (than) R
Q50. According to Myhill Nerode theorem, if L generates finite no. of classes then L is_____
Q51. If the intersection of two regular languages is regular then the complement of the intersection of these two languages is also regular
Q52. In pumping lemma theorem (x y^n z) the range of n is
Q53. For a non regular language there exist FA
Q54. The strings or words which do not belong to a language is called _____ of that language
Q55. A non regular language can be represented by
Q56. For language L defined over {a, b},then L partitions {a, b}* into classes
Q57. If an FA accept a word then there must exist a path from
Q58. Which of the following statement is true about NFA with Null String?
Q59. FA corresponding to an NFA can be built by introducing an empty state for a letter having
Q60. Let FA3 be an FA corresponding to FA1FA2, then the initial state of FA3 must correspond to the initial state of
Q61. A PDA consists of the following:
Q62. The CFG S --> aSa | bSb | a | b | ^ represents the language
Q63. Halt states are
Q64. Choice of path can be determined by left most derivation of the string belonging to CFL at _____ state
Q65. Identify the TRUE statement about following CFG: S -> SB|AB A -> CC B -> b C -> a
Q66. The structure given below is called S -> aA|bB A -> aS|a B -> bS|b
Q67. Which of the following states is not part of PDA
Q68. The production of the form: nonterminal --> one nonterminal is called the
Q69. A is the one for which every input string has a unique path through the machine.
Q70. In the null production N --> ^ , N is a
Q71. The major problem in the earliest computers was
Q72. In polish notation, (o-o-o) is the abbreviation of?
Q73. The CFG is said to be ambiguous if there exist at least one word of its language that can be generated by the _____ production trees
Q74. The input string is placed, before it runs, in
Q75. The production S --> SS | a | b | ^ can be expressed by RE
Q76. The locations into which we put the input letters on "Input Tap" are called _
Q77. "CFG" stands for
Q78. In a CFG the nonterminal that occurs first from the left in the working string, is said to be _
Q79. The unit production is
Q80. A operator adds a new letter at the top of STACK
Q81. The production of the form: Nonterminal-> ^ is said to be production
Q82. For a given input, it provides the compliment of Boolean AND output.
Q83. It delays the transmission of signal along the wire by one step (clock pulse).
Q84. The current in the wire is indicated by 1 and 0 indicates the absence of the current.
Q85. For the given input, AND box provides the Boolean AND output.
Q86. Let L be a language defined over an alphabet Σ, then the language of strings, defined over Σ, not belonging to L, is called Complement of the language L, denoted by Lc or L‟.
Q87. To describe the complement of a language, it is very important to describe the ------------ of that language over which the language is defined.
Q88. For a certain language L, the complement of Lc is the given language L i.e. (Lc)c = Lc
Q89. If L is a regular language then, --------- is also a regular language.
Q90. Converting each of the final states of F to non-final states and old non-final states of F to final states, FA thus obtained will reject every string belonging to L and will accept every string, defined over Σ, not belonging to L. is called
Q91. If L1 and L2 are two regular languages, then L1 U L2 is not a regular.
Q92. If L1 and L2 are regular languages, then these can be expressed by the corresponding FAs.
Q93. The language that can be expressed by any regular expression is called a Non regular language.
Q94. The languages --------------- are the examples of non regular languages.
Q95. Let L be any infinite regular language, defined over an alphabet Σ then there exist three strings x, y and z belonging to Σ* such that all the strings of the form xy z n for n=1,2,3, are the words in L. called.
Q96. Languages are proved to be regular or non regular using pumping lemma.
Q97. If, two strings x and y, defined over Σ, are run over an FA accepting the language L, then x and y are said to belong to the same class if they end in the same state, no matter that state is final or not.
Q98. Myhill Nerode theorem is consisting of the followings,
Q99. The language Q is said to be quotient of two regular languages P and R, denoted by--- if PQ=R.
Q100. If two languages R and Q are given, then the prefixes of Q in R denoted by Pref(Q in R).
Q101. Let Q = {aa, abaaabb, bbaaaaa, bbbbbbbbbb} and R = {b, bbbb, bbbaaa, bbbaaaaa} Pref (Q in R) is equal to,
Q102. If R is regular language and Q is any language (regular/ non regular), then Pref (Q in R) is ------- --.
Q103. The part of an FA, where the input string is placed before it is run, is called
Q104. In new format of an FA (discussed in
Q105. If an effectively solvable problem has answered in yes or no, then this solution is called ---------
Q106. The following problem(s) ------------- is/are called decidable problem(s).
Q107. To examine whether a certain FA accepts any words, it is required to seek the paths from ------- state.
Q108. The high level language is converted into assembly language codes by a program called compiler.
Q109. Grammatical rules which involve the meaning of words are called
Q110. Grammatical rules which do not involve the meaning of words are called -
Q111. The symbols that must be replaced by other things are called
Q112. The grammatical rules are often called
Q113. The terminals are designated by _ letters, while the non- terminals are designated by letters.
Q114. The language generated by _ is called Context Free Language (CFL).
Q115. S → aXb|bXa X → aX|bX|Λ The given CFG generates the language in English _
Q116. The CFG is not said to be ambiguous if there exists atleast one word of its language that can be generated by the different production trees,
Q117. The language generated by that CFG is regular if
Q118. The production of the form no terminal → Λ is said to be null production.
Q119. CNF is stands for
Q120. Null production is a
Showing the first 120 of 274 MCQs.