CS402 Solved MCQs FINAL TERM PDF

CS402-Theory of Automata (Solved MCS’s) LECTURE FROM (23 to 45) [email protected] FOR MORE VISIT JUNAID MALIK [email protected] VULMSHELP....

CS402-Theory of Automata (Solved MCS’s) LECTURE FROM (23 to 45) [email protected] FOR MORE VISIT JUNAID MALIK [email protected] VULMSHELP.COME 0304-1659294 AL-JUNAID INSTITUTE GROUP 1. If Σ = {aa, bb} , then Σ* will not contain aaabbb aabbbb aabbaa bbaabbbb 2. “One language can have _ TG‟s”. Only one Only two More than one Only three 3. 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. FA CFG GTG TG 4. Even-palindrome is a _ language. Non-regular Regular Regular but infinite Regular but finite 5. If L is a regular language then, Lc is also a _ language. Regular (Page 66) Non-regular Regular but finite AL-JUNAID INSTITUTE GROUP None of the given 6. Pumping lemma is generally used to prove that: A given language is infinite A given language is not regular Whether two given regular expressions of a regular language are equivalent or not None of these 7. the FA has N states, then test the words of length less than N. If no word is accepted by this FA, then it will word/words. accept all accept no (Page 85) accept some reject no 8. In CFG, the symbols that can’t be replaced by anything are called. Terminal (Page 87) Non-Terminal Production All of given 9. Which of the following is a regular language? String of odd number of zeroes Set of all palindromes made up of 0‟s and 1‟s String of 0‟s whose length is a prime number All of these 10. Which of the following pairs of regular expressions are equivalent? 1(001)* and (10)*10 x(xx)* and (x)*x X + and X* X + and X* X + 11. An alphabet of Σ is valid if AL-JUNAID INSTITUTE GROUP No letter of Σ appears in middle of any other letter No letter of Σ appears at end of any other letter No letter of Σ appears at start of any other letter No letter of Σ appears at end or middle of any other letter 12. Which of the following statement is true The length of the output string is greater than length of input string in moore machine. The length of the output string is greater than length of input string in mealy machine. The length of the output string is equal to length of input string in moore machine. The length of the output string is less than length of input string in mealy machine. 13. If a CFG has only productions of the form nonterminal → string of two nonterminals or nonterminal → one terminal then the CFG is said to be in _ Chomsky Normal Form Ambiguous Form Left Aligned Form Right Aligned Form 14. 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 Accept (Page 105) Pop Push Reject 15. where the input string is placed before it is run, is called _ Date tape Input Tape (Page 105) Output Tape AL-JUNAID INSTITUTE GROUP Magnetic tape 16. An FSM can be considered as TM Of finite tape length, rewinding capability and unidirectional tape movement Of finite tape length, without rewinding capability and bidirectional tape movement Of finite tape length, rewinding capability and bidirectional tape movement Of finite tape length, without rewinding capability and unidirectional tape movement 17. The process of finding the derivation of the word generated by particular grammar is called Processing Parsing (Page 136) Programming Planning 18. The first rule of converting the given “CFG in CNF”, is CNK algorithm CYK algorithm (Page 135) Algorithm 4 (The CYK algorithm) CKY algorithm KYC algorithm 19. Alphabet Σ = {a, bc, cc} has number of letters One Two Three Four 20. We cannot write regular expressions for all. FA‟s TG‟s NFA‟s CFG’s (Page 97) AL-JUNAID INSTITUTE GROUP 21. For every Context Free Grammar (CFG), we can make the corresponding _. FA TG PDA Regular Grammar 22. Pumping Lemma II says that length(x) + length(y) should be. Less than number of states (Page 75) Equal to number of states Greater than number of states Greater than or equal to number of states 23. Chomsky normal form (CYK) algorithm was proposed by. John cock (Page 135) James Cock Daniel I.A. John Weiss 24. The language of Palindromes defined over an alphabet set {a, b} can be recognized by. FA NFA TG PDA 25. Which of the following is the first phase of compiler on the basis of functionality? Parser Lexical analyzer Scanner Interpreter 26. (Σ* - L) represent the _ of a language L. AL-JUNAID INSTITUTE GROUP Complement (Page 66) Kleene‟s closure Union intersection 27. If we have two transition graphs then their union will be expressed by taking a common start state and joining them by two null transitions (Page 65) just connecting both start states by null transitions connecting final state of first TG to the initial state of second TG connecting the final state of first TG to the final state of second TG 28. and are removed in order to make a CFG in Chomsky Normal Form(CNF). Null, nullable productions Nullable , unit productions Null, unit productions (Page 102) String of length 0, null 29. If L1 and L2 are expressed by regular languages then L1 + L2 is also a Language. Regular (Page 10) Ir-regular PDA Hybrid 30. Which of the following is a regular Context Free Grammar: S → abS| baS | ^ ab(ab+ba)*ba + ba(ab+ba)*ab S → aSb| baS | ^ S → abS| bSa | ^ S → aSb| Sa | ^ 31. A read state can have _ outgoing edge/ edges. 1 2 AL-JUNAID INSTITUTE GROUP 3 Any number of (Page 111) 32. Who did not invent the Turing machine? Alan Turing A. M. Turing (Page 140) Turing None of these 33. Which statement is true? The tape of turing machine is infinite. (Page 140) The tape of turing machine is finite. The tape of turing machine is infinite when the language is regular The tape of turing machine is finite when the language is nonregular. 34. Every regular expression can be expressed as CFG but every CFG cannot be expressed as a regular expression. This statement is: Depends on the language None of the given options True (Page 97) False 35. Consider the language L of strings, defined over Σ = {a,b}, ending in a There are finite many classes generated by L, so L is regular (Page 76) There are infinite many classes generated by L, so L is regular There are finite many classes generated by L, so L is non-regular There are infinite many classes generated by L, so L is non-regular 36. The word „formal‟ in formal languages means ► The symbols used have well defined meaning ► They are unnecessary, in reality ► Only the form of the string of symbols is significant AL-JUNAID INSTITUTE GROUP ► None of these 37. Let A = {0, 1}. The number of possible strings of length „n‟ that can be formed by the elements of the set A is ► n! ► n2 ► nm ► 2n 38. Choose the correct statement. ► A Mealy machine generates no language as such ► A Moore machine generates no language as such ► A Mealy machine has no terminal state ► All of these 39. TM is more powerful than FSM because ► The tape movement is confined to one direction ► It has no finite state control ► It has the capability to remember arbitrary long sequences of input symbols ► None of these 40. Like TG, a PDA can also be non-deterministic True (Page 111) False 41. The language of all words (made up of a‟s and b‟s) with at least two a‟s can not be described by the regular expression. a(a+b)*a(a+b)*(a+b)*ab* AL-JUNAID INSTITUTE GROUP (a+b)* ab* a(a+b)* b*ab* a(a+b)* none of these 42. If L is a regular language then, Lc is also a _ language. Regular (Page 66) rep Non-regular Regular but finite None of the given 43. In CFG, the symbols that can‟t be replaced by anything are called _ Terminal (Page 87) rep Non-Terminal Production All of given 44. Which of the following is NOT a regular language? String of 0‟s whose length is a perfect squere Set of all palindromes made up of 0‟s and 1‟s String of 0‟s whose length is a prime number All of the given options 45. Choose the incorrect (FALSE) statement. A Mealy machine generates no language as such A Mealy machine has no terminal state For a given input string, length of the output string generated by a Moore machine is not more than the length of the output string generated by that of a Mealy machine All of these 46. Choose the incorrect statement: (a+b)*aa(a+b)* generates Regular language. A language consisting of all strings over ∑={a,b} having equal number of a’s and b’s is a regular language AL-JUNAID INSTITUTE GROUP Every language that can be expressed by FA can also be expressed by RE None of these 47. Left hand side of a production in CFG consists of: One terminal More than one terminal One non-terminal (Page 87) Terminals and non-terminals 48. PDA is only used to represent a regular language. True False 49. A production of the form non-terminal string of two non- terminal is called a live Production. True (Page 127) False 50. We can find a CFG corresponding to a DFA. True (Page 97) False 51. START, READ, HERE and ACCEPTS are conversions of the machine True (Page 122) False 52. 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 True (Page 95) False 53. Syntax tree or Generation tree or Derivation tree are same tree True (Page 92) False 54. The symbols that cannot be replaced by anything are called terminals AL-JUNAID INSTITUTE GROUP True (Page 87) repeat False 55. The production of the form non-terminal one non-terminal is called unit production True (Page 100) False 56. DFA and PDA are equal in power. True False (Page 105) 57. A production of the form non-terminal non-terminal is called a dead Production. True False (Page 127) 58. Semi-word is a string having some terminals and one non- terminal at the right of string. True (Page 97) False 59. Two FAs are equivalent if they have same no. of states. True (Page 15) False 60. There exist exactly two different derivations in an ambiguous CFG for a word. True (Page 93) False 61. Regular languages are closed under Union, Concatenation and Kleene star. True (Page 10) False 62. CFG may also represent a regular language. True (Page 97) AL-JUNAID INSTITUTE GROUP False 63. PDA is stronger than FA. True (Page 105) False 64. A Total Language Tree has All languages over Σ All strings over Σ (Page 96) All words of all languages over Σ All words of one language over Σ 65. What Turing Machine does not have? Stack Tape Head Word 66. CFG given S bS|Sb|aa represents language b*aa aab* b*aab* b*(aa)*b* 67. The values of input (say a & b) does not remain same in one cycle due to NAND gate Click plus OR gate NOT gate 68. Set of all palindromes over {a,b}is regular True False (Page 74) AL-JUNAID INSTITUTE GROUP 69. In CFG, the symbols that cannot be replaced by anything are called Terminals (Page 87) rep Non terminals Productions None of the given options 70. a^n b^n generates the................ language regular non regular EQUAL and non regular (Page 71) EQUAL and regular 71. The grammatical rules which involves meaning of words are called: Semantic (Page 87) Sytactics Alphabets None of the given options 72. If an FA has N state then it must accept the word of length N-1 N+1 N+2N 73. Two languages are said to belong to same class if they end in the same state when they run over an FA, that state Must be final state May be final state or not (Page 75) May be start or not None of the given options 74. In pref(Q in R) Q is …… to (than) R Equal Not Equal (Page 79) Greater AL-JUNAID INSTITUTE GROUP Smaller 75. According to Myhill Nerode theorem, if L generates finite no. of classes then L is....... Finite Infinite Regular (Page 76) Non Regular 76. If the intersection of two regular languages is regular then the complement of the intersection of these two languages is also regular True (Page 68) False 77. In pumping lemma theorem (x y^n z) the range of n is n=1,2,3,4.....(Page 74) n=0,1,2,3,4.... n=-3,-2,-1,0,1,2,3,4..... n=-3,-2,-1,1,2,3,4..... 78. The complement of a regular language is also a regular True repeat False 79. For a non regular language there exist …… FA One At least one At most one No (Page 71) 80. The strings or words which do not belong to a language is called................ of that language Intersection Union Complement (Page 66) Quotient 81. A non regular language can be represented by AL-JUNAID INSTITUTE GROUP RE FA TG None of the given options (Page 71) 82. For language L defined over {a, b},then L partitions {a, b}* into …… classes Infinite Finite Distinct (Page 75) Non distinct 83. If an FA accept a word then there must exist a path from Initial to final state (Page 81) Initial to each state Initial to each state but not to final state Initial to final state by traversing each state 84. Which of the following statement is true about NFA with Null String? Infinite states Infinite set of letters Infinite set of transitions Transition of null string is allowed at any stage (Page 71) 85. FA corresponding to an NFA can be built by introducing an empty state for a letter having no transition at certain state (Page 43) one transition at certain state two transition at certain state more than two transitions at certain state 86. Let FA3 be an FA corresponding to FA1FA2, then the initial state of FA3 must correspond to the initial state of FA1 only (Page 35) FA2 only AL-JUNAID INSTITUTE GROUP FA1 or FA2 FA1 and FA2 87. (a* + b*)* = (a + b)* this expression is _ True False 88. If S = {ab, bb}, then S* will not contain Abbbab Bbba ababbb bbbbab 89. What do automata mean? Something done manually Something done automatically What is false about the term alphabet? It is a finite set of symbols. 90. Consider the following production (of a CFG): S->XYZ Here is left most nonterminal in working string. Note: S, X, Y and Z are all nonterminals S X Y Z 91. A PDA is called nondeterministic PDA if There are more than one outgoing edges at READ or POP states with one label (Page 111) There are more than one PUSH states There are mroe than one POP states All of the given options 92. A PDA consists of the following: An alphabet (Sigma) of input letters. An input TAPE with infinite many locations in one direction AL-JUNAID INSTITUTE GROUP One START state with only one out-edge and no in-edge All of the given options (Page 105) 93. The CFG S --> aSa | bSb | a | b | ^ represents the language EVEN-EVEN PALINDROM (Page 91) EQUAL ODD-ODD 94. Halt states are Start and Accept Accept and Reject (Page 105) Start and Reject Read and Reject 95. Choice of path can be determined by left most derivation of the string belonging to CFL at................state Accept (Page 104) Reject Push POP 96. The unit and null productions can be deleted from a CFG True (Page 99-100) False 97. Identify the TRUE statement about following CFG: S -> SB|AB A -> CC B -> b C -> a The given CFG has 8 Nonterminals The given CFG has 8 Terminals The given CFG is in CNF (Page 101) The given CFG is not in CNF 98. The structure given below is called S -> aA|bB A -> aS|a B -> bS|b RE TG AL-JUNAID INSTITUTE GROUP CFG (Page 87) PDA 99. Which of the following states is not part of PDA START ACCEPT WRITE (Page 107) REJECT 100. The production of the form: nonterminal --> one nonterminal is called the Unit production (Page 100) NULL production Terminal production Non Terminal production 101. A is the one for which every input string has a unique path through the machine. Deterministic PDA (Page 111) nondeterministic PDA PUSHDOWN store Input Tape 102. In the null production N --> ^ , N is a Terminal Non terminal (Page 99) Word None of the given options 103. The major problem in the earliest computers was To store the contents in the registers To display mathematical formulae (Page 87) To load the contents from the registers To calculate the mathematical formula 104. In polish notation, (o-o-o) is the abbreviation of………? Operand - Operator – Operand AL-JUNAID INSTITUTE GROUP Operand - Operand- Operator Operator -Operand – Operand (Page 94) Operand -Operand – Operand 105. 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 One Two More than one (Page 95) At most one 106. The input string is placed, before it runs, in Stack Memory Tape (Page 105) Ram 107. The production S --> SS | a | b | ^ can be expressed by RE (a+b)+ (a+b) (a+b)* (Page 88) (ab)* 108. The locations into which we put the input letters on "Input Tap" are called _ Words alphabets cells (Page 105) elements 109. "CFG" stands for Context Free Graph Context Free Grammer (Page 87) Context Finite Graph Context Finite Grammer AL-JUNAID INSTITUTE GROUP 110. In a CFG the nonterminal that occurs first from the left in the working string, is said to be _ Least Significant nonterminal Most Significant nonterminal Left most nonterminal (Page 103) Left most derivate 111. The unit production is Terminal --> Terminal Terminal --> Non Terminal Non terminal --> Terminal Non terminal --> Non Terminal (Page 100) 112. A operator adds a new letter at the top of STACK PUSH (Page 107) POP READ APPEND 113. PDA stands for Push and Drop Automaton Pop and Drop Automaton Push Down Automaton (Page 112) None of given options 114. The production of the form: Nonterminal-> ^ is said to be production NULL (Page 99) UNIT Chomsky form production None of the given options 115. In a STACK: The element PUSHed first is POPed first The element PUSHed first is POPed in the last (Page 107 concept) The element PUSHed in last is POPed in last AL-JUNAID INSTITUTE GROUP None of given options 116. For a given input, it provides the compliment of Boolean AND output. NAND box (NOT AND) (Page 63) DELAY box OR box AND box 117. It delays the transmission of signal along the wire by one step (clock pulse). NAND box (NOT AND) DELAY box (Page 63) OR box AND box 118. Any language that can not be expressed by a RE is said to be regular language. True False 119. The current in the wire is indicated by 1 and 0 indicates the absence of the current.  True (Page 63)  False 120. For the given input, AND box provides the Boolean AND output.  True (Page 63)  False 121. 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‟.  True (Page 66)  False 122. To describe the complement of a language, it is very important to describe the ------------ of that language over which the language is defined. AL-JUNAID INSTITUTE GROUP  Alphabet (Page 66)  Regular Expression  String  Word 123. For a certain language L, the complement of Lc is the given language L i.e. (Lc)c = Lc  True  False (Page 66) 124. If L is a regular language then, ---------- is also a regular language.  Lm  Ls  Lx  Lc (Page 66) 125. 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  Transition Graph of L  Regular expression of L  Complement of L (Page 66)  Finite Automata of L 126. If L1 and L2 are two regular languages, then L1 U L2 is not a regular.  True  False (Page 65) 127. If L1 and L2 are regular languages, then these can be expressed by the corresponding FAs.  True (Page 68)  False 128. The language that can be expressed by any regular expression is called a Non regular language.  True AL-JUNAID INSTITUTE GROUP  False (Page 71) 129. The languages --------------- are the examples of non regular languages.  PALINDROME and PRIME (Page 71)  PALINDROME and EVEN-EVEN  EVEN-EVEN and PRIME  FACTORIAL and SQURE 130. 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.  Complement of L  Pumping Lemma (Page 72)  Kleene‟s theorem  None in given 131. Languages are proved to be regular or non regular using pumping lemma.  True (Page 74)  False 132. is obviously infinite language.  EQUAL-EQUAL  EVEN-EVEN  PALINDROME (Page 75)  FACTORIAL 133. 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.  True (Page 75)  False 134. Myhill Nerode theorem is consisting of the followings,  L partitions Σ* into distinct classes.  If L is regular then, L generates finite number of classes.  If L generates finite number of classes then L is regular. AL-JUNAID INSTITUTE GROUP  All of above (Page 75) 135. The language Q is said to be quotient of two regular languages P and R, denoted by--- if PQ=R.  R=Q/P  Q=R/P (Page 78)  Q=P/R  P=R/Q 136. If two languages R and Q are given, then the prefixes of Q in R denoted by Pref(Q in R).  True (Page 78)  False 137. Let Q = {aa, abaaabb, bbaaaaa, bbbbbbbbbb} and R = {b, bbbb, bbbaaa, bbbaaaaa} Pref (Q in R) is equal to,  {b,bbba,bbbaaa} (Page 78)  {b,bba,bbaaa}  {ab,bba,bbbaa}  {b,bba,bbba} 138. If R is regular language and Q is any language (regular/ non regular), then Pref (Q in R) is ------- --.  Non-regular  Equal  Regular (Page 79)  Infinite 139. states are called the halt states.  ACCEPT and REJECT (Page 105)  ACCEPT and READ  ACCEPT AND START  ACCEPT AND WRITE 140. The part of an FA, where the input string is placed before it is run, is called  State  Transition AL-JUNAID INSTITUTE GROUP  Input Tape (Page 105)  Output Tape 141. In new format of an FA (discussed in lecture 37), This state is like dead-end non final state  ACCEPT  REJECT (Page 105)  STATR  READ 142. Between the two consecutive joints on a path:  One character can be pushed and one character can be popped  Any no. of characters can be pushed and one character can be popped (Page 122)  One character can be pushed and any no. of characters can be popped  Any no. of characters can be pushed and any no. of characters can be popped 143. The PDA is called non-deterministic PDA when there are more than one out going edges from……… state  START or READ  POP or REJECT  READ or POP (Page 111)  PUSH or POP 144. Identify the TRUE statement:  A PDA is non-deterministic, if there are more than one READ states in PDA  A PDA is never non-deterministic  Like TG, A PDA can also be non-deterministic (Page 111)  A PDA is non-deterministic, if there are more than one REJECT states in PDA 145. There is a problem in deciding whether a state of FA should be marked or not when the language Q is infinite.  True (Page 79)  False AL-JUNAID INSTITUTE GROUP 146. If an effectively solvable problem has answered in yes or no, then this solution is called ---------  Decision procedure (Page 80)  Decision method  Decision problem  Decision making 147. The following problem(s) -------------- is/are called decidable problem(s).  The two regular expressions define the same language  The two FAs are equivalent  Both a and b (Page 80)  None of given 148. To examine whether a certain FA accepts any words, it is required to seek the paths from --------state.  Final to initial  Final to final  Initial to final (Page 81)  Initial to initial 149. The high level language is converted into assembly language codes by a program called compiler.  TRUE (Page 87)  FALSE 150. Grammatical rules which involve the meaning of words are called  Semantics (Page 87)  Syntactic  Both a and b  None of given 151. Grammatical rules which do not involve the meaning of words are called -  Semantics  Syntactic (Page 87) AL-JUNAID INSTITUTE GROUP  Both a and b  None of given 152. The symbols that must be replaced by other things are called  Productions  Terminals  Non-terminals (Page 87)  None of given 153. The grammatical rules are often called  Productions (Page 87)  Terminals  Non-terminals  None of given 154. The terminals are designated by _ letters, while the non- terminals are designated by letters.  Capital, bold  Small, capital (Page 87)  Capital, small  Small, bold 155. The language generated by _ is called Context Free Language (CFL).  FA  TG  CFG (Page 87)  TGT 156. S → aXb|bXa X → aX|bX|Λ The given CFG generates the language in English _  Beginning and ending in different letters (Page 91)  Beginning and ending in same letter  Having even-even language  None of given AL-JUNAID INSTITUTE GROUP 157. 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,  TRUE  FALSE (Page 95) 158. The language generated by that CFG is regular if  No terminal → semi  word No terminal → word  Both a and b (Page 97)  None of given 159. The production of the form no terminal → Λ is said to be null production.  TRUE (Page 99)  FALSE 160. CNF is stands for  Context Normal Form  Complete Normal Form  Chomsky Normal Form (Page 102)  Compared Null Form 161. Kleene‟s theorem states  All representations of a regular language are equivalent.  All representations of a context free language are equivalent.  All representations of a recursive language are equivalent  Finite Automata are less powerful than Pushdown Automata. (Page 105) 162. Null production is a  Word  String  Terminal  All of the given options AL-JUNAID INSTITUTE GROUP 163. In nondeterministic PDA a string is supposed to be accepted, if there exists at least one path traced by the string, leading to _ state.  ACCEPT (Page 111)  REJECT  START  READ 164. The CFG which generates the regular language is called:  Regular expression  Finite Automata  Regular grammar (Page 97)  None of the given options 165. If a CFG has a null production, then it is possible to construct another CFG accepting the same language without null production  TRUE  FALSE (Page 99) 166. In large FA with thousands of states and millions of directed edges, without an effective procedure it is to find a path from initial to final state.  Always easy  Impossible (Page 81)  may be good  always impossible 167. If there is no final state of two FAs then their also have no state  initial, union  final, union  union,final (Page 83)  union, initial 168. Set of all palindromes over {a,b} is:  Regular  Regular and finite AL-JUNAID INSTITUTE GROUP  Regular and infinite  Non-regular (Page 71) 169. In the context of Myhill Nerode theorem, for even-even language sigma star can be partitioned into number of classes.  3  4 (Page 77)  5  6 170. The product of two regular languages is.  Regular (Page 78)  Infinite  non-regular  closure of a regular language 171. incase of Myhill Nerode theorem, if a language L partitions sigma star into distinct classes and L is also regular then L generates number of classes.  Infinite  specified  finite (Page 75)  odd 172. While determining regular expression for a given FA, it is to write its regular expression.  Always possible easily  Sometime impossible (Page 80)  always impossible  None of the given options 173. If (L1 ∩ L2c ) ∪ ( L1c ∩ L2 ) is regular language that accepts the words which are in L1 but not in L2 or else in L2 but not in L1. The corresponding FA cannot accept any word which is in L1 and L2.  Not both  Both (Page 80) AL-JUNAID INSTITUTE GROUP  At least in one  None of the given options 174. A problem that has decision procedure is called _ problem.  Regular language  un-decidable  Infinite  Decidable (Page 80) 175. The product of two regular languages is.  Regular (Page 78)  Infinite  non-regular  closure of a regular language 176. In new format of an FA (discussed in lecture 37):……state is like a final state of an FA  START  ACCEPT (Handouts Page # 119)  REJECT  READ 177. In conversion form of PDA there is no..................... state  PUSH  ACCEPT  REJECT (Handouts Page # 119)  READ 178. Given a PDA that accepts the language L  There does not exist any CFG that generates exactly L  that PDA will also accept Language L' (complement of L)  There exists a CFG that generates exactly L (Handouts Page # 118)  None of given options 179. In a CFG the non-terminal that occurs first from the left in the working string. is said to be  Least Significant nonterminal  AL-JUNAID INSTITUTE GROUP Left most nonterminal (Handouts Page #  103) Most Significant nonterminal Left most derivate 180. The structure given below is called S -> aAlbB A -> aSla B -> bSIb  RE  PDA  CFG (It is form of CFG)  TG 181. An FA has N states then it must accept the word of length  2N  N  N-1  N-1 182. To examine whether a certain FA accepts any words. it is required to seek the paths......... state.  from initial to final (Handouts Page # 81)  from initial-to-initial back  from final to initial  from final to back final 183. In nondeterministic PDA. a string is supposed to be accepted if there exists at least one path traced by the string. leading to state.  START  REJECT  READ  ACCEPT (Handouts Page # 111) AL-JUNAID INSTITUTE GROUP 184. If a CFG has a null production, then it is  Called Null CFG  Not possible to construct another CFG without null production accepting the same language with the exception of the word  Called Chmosky Normal Form (CNF)  Possible to construct another CFG without null production accepting the same language with the exception of the word 185. There is at least one production in CFG that has one……………. on its left side.  Non terminal (Handouts Page # 87)  Null production  Terminal  Unit production 186. In large FA with thousands of states and millions of directed edges, without an effective procedure it is…………to find a path from initial to final state.  Impossible (Handouts Page # 81)  Always easy  always impossible  may be good 187. By removing null and unit productions _ _.  CNF can be converted into FA  CNF can be converted into CFG  CFG can be converted into CNF (Handouts Page # 102)  CNF can be converted into Turing machine 188. A………is the one for which every input string has a unique path through the machine  deterministic PDA  Input Tape  nondeterministic PDA  PUSHDOWN store 189. PDA stands for  Push Down Automaton (Handouts Page # 112) AL-JUNAID INSTITUTE GROUP  Pop and Drop Automaton  Push and Drop Automaton  Push Deterministic Automaton 190. A PDA is called nondeterministic PDA if  there are more than one POP states  there are more than one PUSH states  there are more than one outgoing edges at READ or POP states with one label  every READ state is followed by a HERE state. 191. Which of the following cannot be represented by a regular expression?  String of 0's with an odd length  Language of even-even  Language of odd-odd  String of 0s with a prime length (Because Prime is not regular Langue) 192. In conversion form of PDA. there is………..accept state(s).  At most one  At least one  More than One  Exactly one (Handouts Page # 119) 193. If there is no final state of two FAs, then their……….also have no............ state  union, initial  union. Final (Handouts Page # 83)  final, union  initial, union 194. The tree which produces all the strings of a language is called  Derivation tree  Total language tree (Handouts Page # 96)  Non ambiguous tree  Ambiguous tree 195. In new format of an FA (discussed in lecture 37),................. state is like dead-end non final state. AL-JUNAID INSTITUTE GROUP  READ  REJECT (Handouts Page # 105)  START  ACCEPT 196. To write the expression from the tree, it is required to traverse from  Top to bottom of the tree  Right side of the tree  Left side of the tree (Handouts Page # 94)  Bottom to top of the tree 197. A PDA consists of the following:  An alphabet (Sigma) of input letters.  An input TAPE with infinite many locations in one direction  One START state with only one out-edge and no in-edge   All the given options (Handouts Page 105) 198. If R is regular language and Q is any language (regular/ non- regular), then Pref……….in ………….. is regular.  R R  R.Q  Q.R (Handouts Page # 79)  Q.Q 199. ………….is an operation that takes out a letter from the top of the STACK.  WRITE  APPEND  PUSH  POP (Handouts Page # 107) 200. Before the CFG corresponding to the given PDA is determined, the PDA is converted into the standard form which is called.  Finite Automaton  Conversion form (Handouts Page # 118)  None of given options  Chomsky Normal Form (CNF) AL-JUNAID INSTITUTE GROUP 201. The part of an FA, where the input string is placed before it is run, is called  Transition  Input Tape (Handouts Page # 105)  Output Tape  State 202. A problem is said to be ……………….if there exists an algorithm that provides the solution in…………. number of steps.  Effectively unsolvable, infinite  Effectively solvable, infinite  Effectively unsolvable, finite  Effectively solvable, finite (Handouts Page # 80) 203. ……………… states are called the halt states.  ACCEPT AND START  ACCEPT and READ  ACCEPT and REJECT (Handouts Page # 105)  ACCEPT AND WRITE 204. The grammatical rules which involve meaning of words are called  Semantics (Handouts Page # 87)  Syntactics  strings  alphabets 205. The PDA is called non-deterministic PDA when there are more than one out going edges from state  READ or POP (Handouts Page # 111)  START or READ  POP or  PUSH or POP 206. Which of the following states is not part of PDA?  REJECT  ACCEPT  START  WRITE (All other are parts of PDA) AL-JUNAID INSTITUTE GROUP 207. The major problem in the earliest computers was  To calculate the mathematical formula  To display mathematical formulas (Handouts Page # 87)  To store the contents in the registers  To load the contents from the registers 208. The operators like (` +) in the parse tree are considered as  Terminals (Handouts Page # 93)  productions  non-terminals  intermediates 209. If L1 and L2 are two regular languages, then they……………expressed by FAs.  cannot be  May be  may or may not be  can be (Handouts Page # 68) 210. Before running the input string on PDA it is first placed on  Stack  Ram  Memory  Tape (Handouts Page # 107) 211. Which is the correct option  The element PUSHED in last is POPED in last  The element PUSHED first is POPED in the last (LIFO Method, from Book)  The element PUSHED first is POPED first  None of given options 212. Null production is a  String  Word (Handouts Page # 97) AL-JUNAID INSTITUTE GROUP  Terminal  All the above 213. A/an…………operator adds a new letter at the top of STACK  Push (Handouts Page # 107)  Append  Read  Pop 214. In conversion form of PDA, no two………….states exist in a row without state  POP. READ (Handouts Page # 119)  POP. REJECT  PUSH. START  PUSH READ 215. Given a PDA that accepts the language L  that PDA will also accept Language L' (complement of Ll  There exists a CFG that generates exactly L (Handouts Page # 118)  None of given options  There does not exist any CFG that generates exactly 216. In large FA with thousands of states and millions of directed edges, without an effective procedure it is ………. to find a path from initial to final state.  Always easy  always impossible  may be good  Impossible (Handouts Page # 81) 217. The CFG there generates the regular language is called  Regular expression  finite automata  regular grammars (Handouts Page # 97)  now regular grammars 218. Consider the following CFG: (Note: ^ means NULL) S-Xa XaX|bX|^ AL-JUNAID INSTITUTE GROUP  Above give a CFG can be represented by RE  a*b*  a (a + b) *a  (a + b) *a  A*b*a S production will give us Xa. As the X is nonterminal and we must only change X and the terminal a will be on the last of the R.E. Now we will change X production. X production will give us as many a as we want. or if we use the second production which will give us as many b as we want. And last production will give us ^ (lemda) So the answer would be a*b*a Last a is the terminal which we got from the very first production. 219. For a machine with N number of states, the total number of strings to be tested, defined over an alphabet of m letters is  mN +mN+1 + mN+2 +… +m2N-1 (Handouts Page # 86)  mN  Nm  Nm +mN+1 + mN+2 +… + 220. Consider the CFG given below. AB|b Ba Which of the following is a unit production?  Sbb  Ab  AB  Ba 221. 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 AL-JUNAID INSTITUTE GROUP  One  Two  More than one (Handouts Page # 95)  At most one 222. If Q = {xx, xyxxxy} and R = { xyxyxyxxyy, xyxyyyxx} then Pref {Q in R} = _  Xx  Xyxyxy  Xyxyyy (Solved by my self 100% sure)  Xxy 223. The unit production is  Terminal --> Terminal  Terminal --> Non Terminal  Non terminal --> Terminal  Non terminal --> Non-Terminal (Hand out Page # 100) 224. Which of the following statement is FALSE?  For every PDA, there always exists a regular expression (Not sure)  Every CFG cannot be expressed as Regular Expression  Every Regular Expression be expressed by a CFG.  For a PDA, there exists a CFG that represent the same language 225. The CFG S  aSb|ab|^  Palindrome  Prime  Equal  Even The production will give us ab and non-terminal S inside the a and b. If we change the S into next production of ab, we will get abab but instead of using 2nd production, if we use the last which will give us only ^ (Lemda), thus we will get ^ab. So, we will get Equal language (same number of a and same number of b) AL-JUNAID INSTITUTE GROUP 226. Before the PDA is converted into conversion form, a new state --- ---------- is defined which is placed in the middle of any edge.  HERE (Hand out Page # 118)  STOP  START  REJECT 227. A PDA is in conversion form if it fulfills the following conditions:  There is only one ACCEPT state. (Hand out Page # 119)  There are one REJECT state.  There are more than one ACCEPT states.  There is only one Accept state. 228. Identify the false statement about the following CFG SSB|AB ACC B Ca  CFG has 8 Non terminals  all the given option (All are false as There are 4 terminals , It is in CNF and it does not generate any null string)  CFG is not in CNF  CFG generate null string 229. This CFG there generates to the regular language is called  Regular grammar (Hand out Page # 97)  nonregular grammar  finite automata  regular expression 230. The derivation of the word W generated by CFG such that at each step a production is applied to the leftmost nonterminal in the working string is said to be  Left most terminal AL-JUNAID INSTITUTE GROUP  right most terminal  left most derivation (Hand out Page # 103)  right most derivation 231. If the FA has N states, then test these words of length less than N. If no word is accepted by this FA, then it will word/words  Accept no (Hand out Page # 85)  Accept some  Reject No  Accept All 232. In a CFG then non terminals are denoted by  small letters  numbers  capital letters (Hand out Page # 87)  small letters and numbers 233. “CFG”stands for  Context finite graph  contacts finite grammar  contact free graph  Context free grammar (Hand out Page # 87) 234. Consider the following production (of a CFG) SXYZ Here _ _is left most non terminals in working string note XY and Z are all known terminals  X (X is on the most left side)  S  Z  Y 235. Consider the following CFG S a|Xb|aYa X Y|^ (Note: ^ means NULL) Y b|X which nonterminal is/are not nullable AL-JUNAID INSTITUTE GROUP  Y  S, X and Y  S  X (X is Null Production and not a null able) 236. In new format of an FA (discussed in lecture 37):……state is like a final state of an FA  START  ACCEPT (Handouts Page # 119)  REJECT  READ 237. In conversion form of PDA there is no..................... state  PUSH  ACCEPT  REJECT (Handouts Page # 119)  READ 238. Given a PDA that accepts the language L  There does not exist any CFG that generates exactly L  that PDA will also accept Language L' (complement of L)  There exists a CFG that generates exactly L (Handouts Page # 118)  None of given options 239. In a CFG the non-terminal that occurs first from the left in the working string. is said to be  Least Significant nonterminal Left most nonterminal (Handouts Page # 103)  Most Significant nonterminal  Left most derivate 240. The structure given below is called S -> aAlbB A -> aSla B -> bSIb AL-JUNAID INSTITUTE GROUP  RE  PDA  CFG (It is form of CFG)  TG 241. An FA has N states then it must accept the word of length  2N  N  N-1  N-1 242. To examine whether a certain FA accepts any words. it is required to seek the paths......... state.  from initial to final (Handouts Page # 81)  from initial-to-initial back  from final to initial  from final to back final 243. In nondeterministic PDA. a string is supposed to be accepted if there exists at least one path traced by the string. leading to............. state.  START  REJECT  READ  ACCEPT (Handouts Page # 111) 244. If a CFG has a null production, then it is  Called Null CFG  Not possible to construct another CFG without null production accepting the same language with the exception of the word  Called Chmosky Normal Form (CNF)  Possible to construct another CFG without null production accepting the same language with the exception of the word 245. There is at least one production in CFG that has one……………. on its left side.  Non terminal (Handouts Page # 87)  Null production AL-JUNAID INSTITUTE GROUP  Terminal  Unit production 246. In large FA with thousands of states and millions of directed edges, without an effective procedure it is…………to find a path from initial to final state.  Impossible (Handouts Page # 81)  Always easy  always impossible  may be good 247. By removing null and unit productions _ _.  CNF can be converted into FA  CNF can be converted into CFG  CFG can be converted into CNF (Handouts Page # 102)  CNF can be converted into Turing machine 248. A………is the one for which every input string has a unique path through the machine  deterministic PDA  Input Tape  nondeterministic PDA  PUSHDOWN store 249. PDA stands for  Push Down Automaton (Handouts Page # 112)  Pop and Drop Automaton  Push and Drop Automaton  Push Deterministic Automaton 250. A PDA is called nondeterministic PDA if  there are more than one POP states  there are more than one PUSH states  there are more than one outgoing edges at READ or POP states with one label  every READ state is followed by a HERE state. 251. Which of the following cannot be represented by a regular expression? AL-JUNAID INSTITUTE GROUP  String of 0's with an odd length  Language of even-even  Language of odd-odd String of 0s with a prime length (Because Prime is not regular Langue) 252. In conversion form of PDA. there is………..accept state(s).  At most one  At least one  More than One  Exactly one (Handouts Page # 119) 253. If there is no final state of two FAs, then their……….also have no............ state  union, initial  union. Final (Handouts Page # 83)  final, union  initial, union 254. The tree which produces all the strings of a language is called  Derivation tree  Total language tree (Handouts Page # 96)  Non ambiguous tree  Ambiguous tree 255. In new format of an FA (discussed in lecture 37),................. state is like dead-end non final state.  READ  REJECT (Handouts Page # 105)  START  ACCEPT 256. To write the expression from the tree, it is required to traverse from  Top to bottom of the tree  Right side of the tree  Left side of the tree (Handouts Page # 94)  Bottom to top of the tree 257. A PDA consists of the following: AL-JUNAID INSTITUTE GROUP  An alphabet (Sigma) of input letters.  An input TAPE with infinite many locations in one direction  One START state with only one out-edge and no in-edge   All the given options (Handouts Page 105) 258. If R is regular language and Q is any language (regular/ non- regular), then Pref……….in ………….. is regular.  R R  R.Q  Q.R (Handouts Page # 79)  Q.Q 259. ………….is an operation that takes out a letter from the top of the STACK.  WRITE  APPEND  PUSH  POP (Handouts Page # 107) 260. Before the CFG corresponding to the given PDA is determined, the PDA is converted into the standard form which is called.  Finite Automaton  Conversion form (Handouts Page # 118)  None of given options  Chomsky Normal Form (CNF) 261. The part of an FA, where the input string is placed before it is run, is called  Transition  Input Tape (Handouts Page # 105)  Output Tape  State 262. A problem is said to be ……………….if there exists an algorithm that provides the solution in…………. number of steps.  Effectively unsolvable, infinite  Effectively solvable, infinite  Effectively unsolvable, finite  Effectively solvable, finite (Handouts Page # 80) AL-JUNAID INSTITUTE GROUP 263. ……………… states are called the halt states.  ACCEPT AND START  ACCEPT and READ  ACCEPT and REJECT (Handouts Page # 105)  ACCEPT AND WRITE 264. The grammatical rules which involve meaning of words are called  Semantics (Handouts Page # 87)  Syntactics  strings  alphabets 265. The PDA is called non-deterministic PDA when there are more than one out going edges from state  READ or POP (Handouts Page # 111)  START or READ  POP or  PUSH or POP 266. Which of the following states is not part of PDA?  REJECT  ACCEPT  START  WRITE (All other are parts of PDA) 267. The major problem in the earliest computers was  To calculate the mathematical formula  To display mathematical formulas (Handouts Page # 87)  To store the contents in the registers  To load the contents from the registers 268. The operators like (` +) in the parse tree are considered as  Terminals (Handouts Page # 93)  productions  non-terminals AL-JUNAID INSTITUTE GROUP  intermediates 269. If L1 and L2 are two regular languages, then they……………expressed by FAs.  cannot be  May be  may or may not be  can be (Handouts Page # 68) 270. Before running the input string on PDA it is first placed on  Stack  Ram  Memory  Tape (Handouts Page # 107) 271. Which is the correct option  The element PUSHED in last is POPED in last  The element PUSHED first is POPED in the last (LIFO Method, from Book)  The element PUSHED first is POPED first  None of given options 272. Null production is a  String  Word (Handouts Page # 97)  Terminal  All the above 273. A/an…………operator adds a new letter at the top of STACK  Push (Handouts Page # 107)  Append  Read  Pop 274. In conversion form of PDA, no two………….states exist in a row without state  POP. READ (Handouts Page # 119)  POP. REJECT  PUSH. START  PUSH READ AL-JUNAID INSTITUTE GROUP 275. Given a PDA that accepts the language L  that PDA will also accept Language L' (complement of Ll  There exists a CFG that generates exactly L (Handouts Page # 118)  None of given options  There does not exist any CFG that generates exactly 276. In large FA with thousands of states and millions of directed edges, without an effective procedure it is.............. to find a path from initial to final state.  Always easy  always impossible  may be good  Impossible (Handouts Page # 81) 277. The CFG there generates the regular language is called  Regular expression  finite automata  regular grammars (Handouts Page # 97)  now regular grammars 278. Consider the following CFG: (Note: ^ means NULL) S-Xa XaX|bX|^  Above give a CFG can be represented by RE  a*b*  a (a + b) *a  (a + b) *a  A*b*a 279. For a machine with N number of states, the total number of strings to be tested, defined over an alphabet of m letters is  mN +mN+1 + mN+2 +… +m2N-1 (Handouts Page # 86)  mN  Nm  Nm +mN+1 + mN+2 +… + 280. Consider the CFG given below. AL-JUNAID INSTITUTE GROUP AB|b Ba Which of the following is a unit production?  Sbb  Ab  AB  Ba 281. 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  One  Two  More than one (Handouts Page # 95)  At most one 282. If Q = {xx, xyxxxy} and R = { xyxyxyxxyy, xyxyyyxx} then Pref {Q in R} = _  Xx  Xyxyxy  Xyxyyy (Solved by my self 100% sure)  Xxy 283. The unit production is  Terminal --> Terminal  Terminal --> Non Terminal  Non terminal --> Terminal  Non terminal --> Non-Terminal (Hand out Page # 100) 284. Which of the following statement is FALSE?  For every PDA, there always exists a regular expression (Not sure)  Every CFG cannot be expressed as Regular Expression  Every Regular Expression be expressed by a CFG.  For a PDA, there exists a CFG that represent the same language 285. The CFG S  aSb|ab|^  Palindrome AL-JUNAID INSTITUTE GROUP  Prime  Equal  Even 286. Before the PDA is converted into conversion form, a new state --- ---------- is defined which is placed in the middle of any edge.  HERE (Hand out Page # 118)  STOP  START  REJECT 287. A PDA is in conversion form if it fulfills the following conditions:  There is only one ACCEPT state. (Hand out Page # 119)  There are one REJECT state.  There are more than one ACCEPT states.  There is only one Accept state. 288. Identify the false statement about the following CFG SSB|AB ACC B Ca  CFG has 8 Non terminals  all the given option (All are false as There are 4 terminals , It is in CNF and it does not generate any null string)  CFG is not in CNF  CFG generate null string 289. This CFG there generates to the regular language is called  Regular grammar (Hand out Page # 97)  nonregular grammar  finite automata  regular expression AL-JUNAID INSTITUTE GROUP 290. The derivation of the word W generated by CFG such that at each step a production is applied to the leftmost nonterminal in the working string is said to be  Left most terminal  right most terminal  left most derivation (Hand out Page # 103)  right most derivation 291. If the FA has N states, then test these words of length less than N. If no word is accepted by this FA, then it will word/words  Accept no (Hand out Page # 85)  Accept some  Reject No  Accept All 292. In a CFG then non terminals are denoted by  small letters  numbers  capital letters (Hand out Page # 87)  small letters and numbers 293. “CFG”stands for  Context finite graph  contacts finite grammar  contact free graph  Context free grammar (Hand out Page # 87) 294. Consider the following production (of a CFG) SXYZ Here is left most non terminals in working string note XY and Z are all known terminals  X (X is on the most left side)  S  Z  Y 295. Consider the following CFG AL-JUNAID INSTITUTE GROUP S a|Xb|aYa X Y|^ (Note: ^ means NULL) Y b|X which nonterminal is/are not nullable Y S, X and Y S X (X is Null Production and not a nullable