Automata Theory Past Paper PDF

1. How many tuples are there in a finite state machine? - a) 4 - b) 5 (Correct) - c) 6 - d) Unlimited 2. The transition function of a DFA maps: - a) Σ * Q -> Σ - b) Q * Q -> Σ - c) Σ * Σ -> Q - d) Q * Σ -> Q** (Correct) 3. What is the minimum number of states required for a DFA acc...

1. How many tuples are there in a finite state machine? - a) 4 - b) 5 (Correct) - c) 6 - d) Unlimited 2. The transition function of a DFA maps: - a) Σ * Q -> Σ - b) Q * Q -> Σ - c) Σ * Σ -> Q - d) Q * Σ -> Q** (Correct) 3. What is the minimum number of states required for a DFA accepting strings that end with "10"? - a) 3(Correct) - b) 2 - c) 1 - d) Can't be represented. 4. An NFA’s transition function returns: - a) A Boolean value - b) A state - c) A set of states (Correct) - d) An edge 5. Which of the following is true about a DFA? - a) It can have multiple transitions for the same input symbol. - b) It has exactly one transition for each symbol in the alphabet from every state.** (Correct) - c) It can be in multiple states at once. - d) It cannot accept regular languages. 6. What does the term 'accepting state' refer to in automata? - a) The state where processing starts. - b) A state that can transition to any other state. - c) A state where if the automaton ends, the input string is accepted. (Correct) - d) A state that cannot be reached. 7. Which of the following machines is used for recognizing regular languages? - a) Turing Machine - b) Pushdown Automaton - c) Finite Automaton (Correct) - d) None of the above. 8. In which type of automaton can epsilon transitions occur? - a) DFA - b) NFA (Correct) - c) Both DFA and NFA - d) None of the above. 9. The equivalence between DFA and NFA means: - a) They have the same number of states. - b) They accept different sets of strings. - c) They accept the same set of strings. (Correct) - d) They cannot be compared. 10. What is a Mealy machine? - a) An automaton where outputs depend only on states. - b) An automaton that produces output based on input and current state. - c) An automaton that produces output based on input and next state.(Correct) - d) None of the above. 11. Which grammar generates all regular languages? - a) Context-Free Grammar - b) Context-Sensitive Grammar - c) Unrestricted Grammar - d) Regular Grammar (Correct) 12. What is Chomsky Normal Form? - a) A form where each production rule has one terminal symbol. - b) A form where each production rule has two non-terminal symbols. - **c) A form where each production rule is either A → BC or A → a.** (Correct) - d) None of the above. 13. What operation on languages results in strings that are in either language? - a) Concatenation - b) Intersection - c) Union** (Correct) - d) Complement. 14. Recursive enumerable sets are: - a) Sets that can be decided by some algorithm. - b) Sets that can be generated by context-free grammars. - c) Sets that can be recognized by Turing machines. -d) Sets that can be enumerated by some algorithm but not necessarily decided.** (Correct) 15. Which type of grammar can generate non-regular languages? - a) Regular Grammar - b) Context-Free Grammar - c) Regular Expressions - d) Context-Sensitive Grammar** (Correct) 16. Which of the following is not an operation on languages? - a) Union - b) Intersection - c) Concatenation - d) Derivation (Correct) 17. A string belongs to a language generated by grammar if: - a) It can be derived from the start symbol using production rules. - b) It cannot be derived from any other string. - c) It is part of the alphabet of the grammar. - d) It follows all rules defined by the grammar's productions.** (Correct) 18. In formal language theory, what does 'derivation' refer to? - a) The process of creating new languages from existing ones. - b) The method of transforming strings into other strings using rules. - c) The method of proving language properties. - d)** The sequence of production applications leading to a string from the start symbol. (Correct) 19. Which machine uses states and transitions to process input symbols? - a)Turing Machine** (Correct) - b) Finite Automaton - c) Pushdown Automaton – d)All of the above 20. A context-free grammar consists of: – a) Variables, terminals, start symbol, and production rules** (Correct) – b) Only terminals and variables – c) Only production rules – d) Only variables 21. What does it mean for two grammars to be equivalent?  – a) They generate different languages – b) They generate no strings at all – c)They generate exactly the same language (Correct) – d) They have different production rules 22. In which type of automata does every transition lead to exactly one next state – a) Nondeterministic Finite Automaton – b)Mealy Machine – c)Moore Machine – d) Deterministic Finite Automaton(Correct) 23. The pumping lemma is used to prove: – a) The closure properties of regular languages – b)That certain languages are not regular** (Correct) – c)That all context-free languages are regular – d)That all finite automata are equivalent 24. Which machine accepts context-free languages? – a) Finite Automata – bTuring Machines – c) Pushdown Automata (Crrect) – d) None of these 25. What kind of language does an NFA accept? – a) Only regular languages – b) Only context-free languages – c)Only recursive languages – d) Regular languages and some non-regular languages through nondeterminism** (Correct) 26. The main difference between Mealy and Moore machines is:  – a)Their ability to process input symbols only once each time they read them – b) Their output depends solely on states or both states and inputs respectively(Correct) – c)Their number of states required for processing inputs – d) Their acceptance criteria for input strings 27. Which property does not hold for regular languages? – a) Closure under union – b)Closure under intersection – c)Closure under complementation – d)Closure under context-free grammars*(Correct) 28. A Turing machine is considered powerful because: – a) It has limited memory – b) It can simulate any algorithm – c)It cannot recognize all recursive enumerable sets – d)It operates within polynomial time* (Correct) 29. The set of all strings over an alphabet Σ is known as: – a)Empty Language – b) Finite Language – c)Infinite Language – d) Universal Language (Correct) 30. In formal language theory, what does 'closure' refer to? – a) The completeness property concerning derivations – b) The operations applied to sets resulting in new sets within the same family – c)The ability to derive all possible strings from given productions – d) All options are correct (Correct)