Theoretical Foundations MCQs December 19, 2025December 14, 2024 by u930973931_answers 30 min Score: 0 Attempted: 0/30 Subscribe 1. What is the main purpose of a formal grammar in compiler design? (A) To generate machine code (B) To define the syntax of programming languages (C) To optimize execution speed (D) To manage memory allocation 2. Which of the following is NOT a type of formal grammar in the Chomsky hierarchy? (A) Regular grammar (B) Context-free grammar (C) Context-sensitive grammar (D) Procedural grammar 3. What is a language in terms of automata theory? (A) A collection of syntax errors (B) A set of compiler instructions (C) A set of strings over an alphabet (D) A runtime error detection system 4. Which automaton recognizes regular languages? (A) Pushdown automaton (B) Finite automaton (C) Turing machine (D) Linear-bounded automaton 5. Context-free grammars are usually recognized by which type of automaton? (A) Finite automaton (B) Deterministic finite automaton (C) Turing machine (D) Pushdown automaton 6. Which of the following is a property of regular languages? (A) Can count nested structures (B) Require a stack for recognition (C) Can perform arbitrary computation (D) Can be recognized by finite automata 7. What is the purpose of derivation in grammar? (A) To optimize code execution (B) To generate strings in the language (C) To allocate memory (D) To handle runtime exceptions 8. Which of the following is an example of a context-free language? (A) Strings of balanced parentheses (B) Strings with equal number of a’s, b’s, and c’s (C) Any string over {0,1} (D) Finite set of numbers 9. What does the term “ambiguity” in grammar refer to? (A) A grammar that generates infinite strings (B) A grammar with no terminal symbols (C) A language that cannot be recognized by a Turing machine (D) A string that has more than one leftmost derivation 10. Which automaton is equivalent in power to a Turing machine? (A) Deterministic finite automaton (B) None; Turing machine is the most powerful (C) Linear-bounded automaton (D) Pushdown automaton 11. Which of the following is NOT true about regular expressions? (A) Can describe context-free languages (B) Can be converted into finite automata (C) Can describe regular languages (D) Cannot count nested parentheses 12. What is the pumping lemma used for? (A) To prove that a language is not regular or not context-free (B) To optimize code generation (C) To detect syntax errors (D) To generate parse trees 13. Which of the following is a limitation of finite automata? (A) Cannot represent alphabets (B) Cannot recognize regular languages (C) Cannot process input symbols (D) Cannot recognize context-free languages 14. Deterministic and non-deterministic finite automata are: (A) Non-deterministic automata cannot recognize languages (B) Deterministic automata are more powerful (C) Equally powerful for recognizing regular languages (D) Only theoretical concepts with no practical use 15. What is a parse tree? (A) A tree representing memory allocation (B) A tree representing the syntactic structure of a string according to a grammar (C) A tree used for optimization (D) A tree for storing variables 16. Which of the following is a key difference between context-free and regular grammars? (A) Context-free grammars can handle nested structures (B) Regular grammars require a stack (C) Regular grammars are Turing-complete (D) Context-free grammars cannot generate strings 17. What is the purpose of leftmost derivation in parsing? (A) To determine the order of applying grammar rules from left to right (B) To optimize code execution (C) To allocate memory (D) To perform semantic analysis 18. Which class of languages is recognized by a linear-bounded automaton? (A) Regular languages (B) Context-free languages (C) Recursively enumerable languages (D) Context-sensitive languages 19. In automata theory, what is the “accepting state”? (A) The initial state (B) The state where memory is allocated (C) A state indicating that input string is accepted by the automaton (D) A state indicating runtime error 20. Which of the following is true about Turing machines? (A) Can recognize only regular languages (B) Only theoretical, with no practical implications (C) Cannot recognize context-sensitive languages (D) Can simulate any computation that a real computer can perform 21. What is a “dead state” in finite automata? (A) A state that optimizes memory usage (B) A starting state (C) A state from which no accepting state can be reached (D) A state used for debugging 22. Which of the following is the highest level in the Chomsky hierarchy? (A) Regular languages (B) Context-free languages (C) Recursively enumerable languages (D) Context-sensitive languages 23. Which of the following is a recursively enumerable language? (A) Any language accepted by a Turing machine (B) Strings of balanced parentheses (C) Strings of alternating 0s and 1s (D) Empty language 24. What is the main difference between deterministic and non-deterministic pushdown automata? (A) Nondeterministic PDA cannot recognize context-free languages (B) Deterministic PDA has a single possible move for each input and stack symbol, Nondeterministic can have multiple moves (C) Deterministic PDA uses memory (D) No difference exists 25. What is the main purpose of syntax-directed translation? (A) To check memory usage (B) To generate stack frames (C) To execute machine code (D) To translate strings into intermediate code based on parse trees 26. Which of the following is NOT true about context-sensitive languages? (A) Recognized by linear-bounded automata (B) Cannot be recognized by any Turing machine (C) All context-free languages are context-sensitive (D) Can describe some programming language constructs 27. Which property distinguishes deterministic context-free languages? (A) Requires multiple stacks (B) Cannot be parsed efficiently (C) Can be recognized by a deterministic pushdown automaton (D) Cannot represent programming language syntax 28. Which theorem is used to prove that certain languages are not regular? (A) Church-Rosser theorem (B) Rice’s theorem (C) Gödel’s incompleteness theorem (D) Pumping lemma for regular languages 29. Which of the following is a practical application of automata theory in compilers? (A) Dynamic memory allocation (B) Lexical analysis for token recognition (C) Optimizing hardware circuits (D) Network security 30. Which of the following is true about the relation between Chomsky hierarchy and compiler design? (A) Only recursively enumerable languages are relevant (B) Context-sensitive languages are ignored (C) Regular and context-free languages form the basis of lexical and syntax analysis (D) Compiler design only uses Turing machines