The document contains a set of multiple choice questions related to formal languages and automata theory. It covers topics like regular languages, DFA, NFA, grammars, finite state machines and more. There are 60 questions in total along with their answers.
The document contains a set of multiple choice questions related to formal languages and automata theory. It covers topics like regular languages, DFA, NFA, grammars, finite state machines and more. There are 60 questions in total along with their answers.
The document contains a set of multiple choice questions related to formal languages and automata theory. It covers topics like regular languages, DFA, NFA, grammars, finite state machines and more. There are 60 questions in total along with their answers.
The document contains a set of multiple choice questions related to formal languages and automata theory. It covers topics like regular languages, DFA, NFA, grammars, finite state machines and more. There are 60 questions in total along with their answers.
1. A Language for which no DFA exist is a________ a) Regular Language b) Non-Regular Language c) May be Regular d) Cannot be said 2. A DFA cannot be represented in the following format a) Transition graph b) Transition Table c) C code d) None of the mentioned 3. What the following DFA accepts?
TRACE KTU
a) x is a string such that it ends with ‘101’
b) x is a string such that it ends with ‘01’ c) x is a string such that it has odd 1’s and even 0’s d) x is a strings such that it has starting and ending character as 1 4. Which of the following will the given DFA won’t accept?
a) ε b) 11010 c) 10001010 d) String of letter count 11 5. TRACE KTU Can a DFA recognize a palindrome number? a) Yes b) No c) Yes, with input alphabet as ∑* d) Can’t be determined 6. Given: L= {0n1n for n>=1}; Can there be a DFA possible for the language? a) Yes b) No 7. Which among the following states would be notated as the final state/acceptance state? L= {xϵ∑= {a, b} | length of x is 2} a) q1 b) q2 c) q1, q2 d) q3 8 Given:
a) Yes b) No TRACE KTU L= {wwR|wϵ{0,1} }Can there be a DFA possible for the language?
9.
Which among the following states would be notated as the final state/acceptance state? L= {xϵ∑= {a, b} | length of x is atmost 2} a) q1 b) q2 c) q0,q1, q2 d) q1, q2,q3 10. How many languages are over the alphabet R? a) countably infinite b) countably finite c) uncountable finite d) uncountable infinite
11. State true or false: Statement: Both NFA and e-NFA recognize exactly the same languages. a) true b) false 12. Which of the following belongs to the epsilon closure set of a?
a) {f1, f2, f3}
b) {a, f1, f2, f3} c) {f1, f2} d) none of the mentioned 13. The number of elements present in the e-closure(f2) in the given diagram:
TRACE KTU
a) 0 b) 1 c) 2 d) 3 14. Is the language preserved in all the steps while eliminating epsilon transitions from a NFA? a) yes b) no 15. Remove all the epsilon transitions in the given diagram and compute the number of a- transitions in the result?
a) 5 b) 7 c) 9 d) 6 16. TRACE KTU What does the following figure most correctly represents?
a) Final state with loop x
b) Transitional state with loop x c) Initial state as well as final state with loop x d) Insufficient Data 17. Which of the following will not be accepted by the following DFA?
a) ababaabaa b) abbbaa c) abbbaabb d) abbaabbaa 18. The entity which generate Language is termed as: a) Automata b) Tokens c) Grammar d) Data TRACE KTU 19. Given grammar G: (1)S->AS (2)S->AAS (3)A->SA (4)A->aa Which of the following productions denies the format of Chomsky Normal Form? a) 2,4 b) 1,3 c) 1, 2, 3, 4 d) 2, 3, 4 20. Suppose A->xBz and B->y, then the simplified grammar would be: a) A->xyz b) A->xBz|xyz c) A->xBz|B|y d) none of the mentioned ANSWERS
11.a 12.b 13.c 14.a 15.b 16.c 17.a 18.c 19.a 20.a 21. Given Grammar: S->A, A->aA, A->e, B->bA Which among the following productions are Useless productions? a) S->A b) A->aA c) A->e d) B->bA 22. TRACE KTU S->…->xAy->…->w, then A is _____ a) Reachable b) Generating c) Both Reachable and Generating d) None of above 23. For the given grammar G: S->ABaC A->BC B->b| e C->D| e D-> d Remove the e productions and generate the number of productions from S in the modified or simplified grammar. a) 6 b) 7 c) 5 d) 8 24. Consider G=({S,A,B,E}, {a,b,c},P,S), where P consists of S →AB, A →a, B →b and E →c. Number of productions in P’ after removal of useless symbols: a) 4 b) 3 c) 2 d) 5 25. Given grammar G: S->aS| AB A-> e B-> e D-> b Reduce the grammar, removing all the e productions: a) S->aS| AB| A| B, D-> b b) S->aS| AB| A| B| a, D-> b c) S->aS| AB| A| B d) None of the mentioned 26. The format: A->aB refers to which of the following?
TRACE KTU a) Chomsky Normal Form b) Greibach Normal Form c) Backus Naur Form d) None of the mentioned 27. NFA, in its name has ’non-deterministic’ because of : a) The result is undetermined b) The choice of path is non-deterministic c) The state to be transited next is non-deterministic d) All of the mentioned 28. Given Language L= {xϵ {a, b}*|x contains aba as its substring} Find the difference of transitions made in constructing a DFA and an equivalent NFA? a) 2 b) 3 c) 4 d) Cannot be determined. 29. The number of tuples in an extended Non Deterministic Finite Automaton: a) 5 b) 6 c) 7 d) 4 30. What is the relation between DFA and NFA on the basis of computational power? a) DFA > NFA b) NFA > DFA c) Equal d) Can’t be said ANSWERS
21.d 22.c 23.d 24.a
TRACE KTU 25.b 26.b 27.b 28.a 29.a 30.c
31. Which of the following is not an example of finite state machine system? a) Control Mechanism of an elevator b) Combinational Locks c) Traffic Lights d) Digital Watches 32. Which of the following is the corresponding Language to the given DFA?
a) L= {x ϵ {0, 1} * | x ends in 1 and does not contain substring 01}
b) L= {x ϵ {0,1} * |x ends in 1 and does not contain substring 00} c) L= {x ϵ {0,1} |x ends in 1 and does not contain substring 00}
TRACE KTU d) L= {x ϵ {0,1} * |x ends in 1 and does not contain substring 11} 33. Subset Construction method refers to: a) Conversion of NFA to DFA b) DFA minimization c) Eliminating Null references d) ε-NFA to NFA 34. We can represent one language in more one FSMs, true or false? a) TRUE b) FALSE c) May be true d) Cannot be said 35. The production of form non-terminal -> ε is called: a) Sigma Production b) Null Production c) Unit Production d) All of the mentioned 36. Which of the following is an application of Finite Automaton? a) Compiler Design b) Grammar Parsers c) Text Search d) All of the mentioned 37. Can a DFA recognize a palindrome number? a) Yes b) No c) Yes, with input alphabet as ∑* d) Can’t be determined 38. Which of the following is not an example of finite state machine system? a) Control Mechanism of an elevator b) Combinational Locks c) Traffic Lights d) Digital Watches 39. An NFA can be modified to allow transition without input alphabets, along with one or
a) True b) False TRACE KTU more transitions on input symbols.
40. The Grammar can be defined as: G=(V, ∑, p, S) In the given definition, what does S represents? a) Accepting State b) Starting Variable c) Sensitive Grammar d) None of these ANSWERS
31.d 32.b 33.a 34.a 35.b 36.d 37.b 38.d 39.a 40.b 41. Which among the following cannot be accepted by a regular grammar? a) L is a set of numbers divisible by 2 b) L is a set of binary complement c) L is a set of string with odd number of 0 d) L is a set of 0n1n 42. Which of the expression is appropriate? For production p: a->b where a∈V and b∈_______ a) V b) S c) (V+∑)* d) V+ ∑ 43. For S->0S1|∈ for ∑={0,1}*, which of the following is wrong for the language produced?
b) 0n1n | n>=0 c) 0n1n | n>=1 TRACE KTU a) Non regular language
d) None of the mentioned
44. The minimum number of productions required to produce a language consisting of palindrome strings over ∑={a,b} is a) 3 b) 7 c) 5 d) 6 45. Which of the following statement is correct? a) All Regular grammar are context free but not vice versa b) All context free grammar are regular grammar but not vice versa c) Regular grammar and context free grammar are the same entity d) None of the mentioned 46. Are ambiguous grammar context free? a) Yes b) No 47. A->aA| a| b The number of steps to form aab: a) 2 b) 3 c) 4 d) 5 48. The language accepted by Push down Automaton: a) Recursive Language b) Context free language c) Linearly Bounded language d) All of the mentioned 49. Which of the following the given language belongs to? L={ambmcm| m>=1} a) Context free language b) Regular language c) Both (a) and (b) d) None of the mentioned 50.
a) Queue b) Linked List TRACE KTU The most suitable data structure used to represent the derivations in compiler:
c) Tree d) Hash Tables ANSWERS
41.d 42.c 43.d 44.c 45.a 46.a 47.b 48.b 49.d 50.c 51. The Kleene Star operation accepts the following strings over set A = {0,1} | where string s contains even number of 0 and 1 a) 01,0011,010101,.... b) 0011,11001100,... c) ε,0011,11001100,... d) ε,0011,11001100,... 52. Moore Machine is an application of: a) Finite automata without input b) Finite automata with output c) Non- Finite automata with output d) None of the mentioned 53. For a give Moore Machine, Given Input=’101010’, thus the output would be of length: a) |Input|+1 b) |Input| c) |Input-1|
54. TRACE KTU
d) Cannot be predicted
Which of the following is a correct statement?
a) Moore machine has no accepting states b) Mealy machine has accepting states c) We can convert Mealy to Moore but not vice versa d) All of the mentioned 55. A regular language over an alphabet ∑ is one that cannot be obtained from the basic languages using the operation a) Union b) Concatenation c) Kleene* d) All of the mentioned 56. The output alphabet can be represented as: a) δ b) ∆ c) ∑ d) None of the mentioned 57. Mealy Machine is an application of: a) Finite automata without input b) Finite automata with output c) Non- Finite automata with output d) None of the mentioned 58. Statement1:Nullstring is accepted in Moore Machine. Statement 2: There are more than 5-Tuples in the definition of Moore Machine.
Choose the correct option:
a) Statement 1 is true and Statement 2 is true b) Statement 1 is true while Statement 2 is false c) Statement 1 is false while Statement 2 is true d) Statement 1 and Statement 2, both are false
59. Statement 1: A Finite automata can be represented graphically; Statement 2: The nodes can be its states; Statement 3: The edges or arcs can be used for transitions Which of the following make the correct combination? a) Statement 1 is false but Statement 2 and 3 are correct b) Statement 1 and 2 are correct while 3 is wrong c) None of the mentioned statements are correct
TRACE KTU d) All of the mentioned 60. In Moore machine, output is produced over the change of: a) transitions b) states c) Both d) None of the mentioned ANSWERS
51.c 52.b 53.a 54.a 55.d 56.b 57.b 58.a 59.d 60.b 61. Which of the following is a correct statement? a) Moore machine has no accepting states b) Mealy machine has accepting states c) We can convert Mealy to Moore but not vice versa d) All of the mentioned 62. In mealy machine, the O/P depends upon? a) State b) Previous State c) State and Input d) Only Input 63. Mealy and Moore machine can be categorized as: a) Inducers b) Transducers c) Turing Machines d) Linearly Bounder Automata 64. TRACE KTU Which among the following is the root of the parse tree? a) Production P b) Terminal T c) Variable V d) Starting Variable S 65. Which of the following does the given parse tree correspond to?
a) P->1100 b) P->0110 c) P->1100ε TRACE KTU d) P->0101 66. A grammar with more than one parse tree is called: a) Unambiguous b) Ambiguous c) Regular d) None of the mentioned 67. A symbol X is ________ if there exists : S-> aXb a) reachable b) generating c) context free d) none of the mentioned 68. A symbol X is called to be useful if and only if its is: a) generating b) reachable c) both generating and reachable d) none of the mentioned 69. Which of the following is false for a grammar G in Chomsky Normal Form: a) G has no useless symbols b) G has no unit productions c) G has no epsilon productions d) None of the mentioned 70. To derive a string using the production rules of a given grammar, we use: a) Scanning b) Parsing c) Derivation d) All of the mentioned ANSWERS
61.a 62.c 63.b 64.d 65.b TRACE KTU 66.b 67.a 68.c 69.d 70.b 71. The e-NFA recognizable languages are not closed under : a) Union b) Negation c) Kleene Closure d) None of the mentioned 72. Which of the following are undecidable problems? a) Determining whether two grammars generate the same language b) Determining whether a grammar is ambiguous c) Both (a) and (b) d) None of the mentioned 73. If a problem has an algorithm to answer it, we call it _________ a) decidable b) solved c) recognizable d) none of the mentioned 74. The ratio of number of input to the number of output in a mealy machine can be given as: a) 1 b) n: n+1 c) n+1: n d) None of the mentioned 75. Which of the given are correct? a) Moore machine has 6-tuples b) Mealy machine has 6-tuples c) Both Mealy and Moore has 6-tuples d) None of the mentioned 76. TRACE KTU The major difference between Mealy and Moore machine is about: a) Output Variations b) Input Variations c) Both d) None of the mentioned 77. Which of the following does not belong to input alphabet if S={a, b}* for any language? a) a b) b c) e d) none of the mentioned 78. Every grammar in Chomsky Normal Form is: a) regular b) context sensitive c) context free d) all of the mentioned 79. Which of the production rule can be accepted by Chomsky grammar? a) A->BC b) A->a c) S->e d) All of the mentioned 80. A push down automaton employs ________ data structure. a) Queue b) Linked List c) Hash Table d) Stack ANSWER 71.d 72.c 73.a 74.a 75.c
TRACE KTU 76.a 77.c 78.c 79.d 80.d 81. Push down automata accepts _________ languages. a) Type 3 b) Type 2 c) Type 1 d) Type 0 82. A string is accepted by a PDA when a) Stack is empty b) Acceptance state c) Both (a) and (b) d) None of the mentioned 83. A context free grammar can be recognized by a) Push down automata b) 2 way linearly bounded automata c) Both (a) and (b) d) None of the mentioned 84. The production of the form A->B , where A and B are non terminals is called a) Null production b) Unit production c) Greibach Normal Form d) Chomsky Normal Form 85. In pushdown automata notation,what does the symbol z0 represents? a) an element of G b) initial stack symbol c) top stack alphabet d) all of the mentioned 86. A turing machine operates over:
TRACE KTU a) finite memory tape b) infinite memory tape c) depends on the algorithm d) none of the mentioned 87. Which of the functions are not performed by the turing machine after reading a symbol? a) writes the symbol b) moves the tape one cell left/right c) proceeds with next instruction or halts d) none of the mentioned 88. Given Grammar G: S->aA A->a| A B->B The number of productions to be removed immediately as Unit productions: a) 0 b) 1 c) 2 d) 3 89. Given grammar: S->aA A->a A->B B-> A B->bb Which of the following is the production of B after simplification by removal of unit productions? a) A b) bb c) aA d) A| bb 90. CFGs can be parsed in polynomial time using__________ a) LR parser b) CYK algorithm c) SLR parser d) None of the mentioned
ANSWERS
TRACE KTU 81.b 82.c 83.c 84.b 85.b 86.b 87.d 88.c 89.b 90.b 91. The following move of a PDA is on the basis of: a) Present state b) Input Symbol c) Both (a) and (b) d) None of the mentioned 92. Which among the following is not a part of the Context free grammar tuple? a) End symbol b) Start symbol c) Variable d) Production 93. Which of the following automata takes stack as auxiliary storage? a) Finite automata b) Push down automata c) Turing machine d) All of the mentioned 94. A null production can be referred to as: a) String b) Symbol c) Word TRACE KTU d) All of the mentioned 95. A push down automata can be represented as: PDA= ε-NFA +[stack] State true or false: a) true b) false 96. Which of the following does not have left recursions? a) Chomsky Normal Form b) Greibach Normal Form c) Backus Naur Form d) All of the mentioned 97. Which of the following are correct statements? a) TMs that always halt are known as Decidable problems b) TMs that are guaranteed to halt only on acceptance are recursive ennumerable. c) Both (a) and (b) d) None of the mentioned 98. With reference to binary strings, state true or false: Statement: For any turing machine, the input alphabet is restricted to {0,1}. a) true b) false 99. The decision problem is the function from string to ______________ a) char b) int c) boolean d) none of the mentioned 100. Which of the following is true for The Halting problem? a) It is recursively ennumerable b) It is undecidable c) Both (a) and (b) d) None of the mentioned ANSWERS
