1. Which of the following is the highest level in the Chomsky hierarchy of grammars?
A) Type 0
B) Type 1
C) Type 2
D) Type 3
Answer: A) Type 0
2. Which type of grammar corresponds to regular languages?
A) Type 0 grammar
B) Type 1 grammar
C) Type 2 grammar
D) Type 3 grammar
Answer: D) Type 3 grammar
3. Which of the following is true about Type 2 grammars (context-free grammars)?
A) They can be parsed by finite automata
B) They can be recognized by a deterministic finite automaton (DFA)
C) They are more powerful than Type 3 grammars
D) They cannot be used to describe arithmetic expressions
Answer: C) They are more powerful than Type 3 grammars
4. Which type of automaton is used to recognize languages generated by Type 1 grammars?
A) Finite state automaton (FSA)
B) Pushdown automaton (PDA)
C) Linear-bounded automaton (LBA)
D) Turing machine
Answer: C) Linear-bounded automaton (LBA)
5. Which of the following is true about regular languages?
A) They can be parsed by a pushdown automaton (PDA)
B) They can be recognized by a deterministic finite automaton (DFA)
C) They require a Turing machine for recognition
D) They are not closed under union
Answer: B) They can be recognized by a deterministic finite automaton (DFA)
6. What is a key characteristic of context-sensitive languages (Type 1)?
A) They can be recognized by a finite state automaton
B) Their grammar rules are not restricted in length
C) They require a pushdown automaton for recognition
D) They can be generated by a context-free grammar
Answer: B) Their grammar rules are not restricted in length
7. Which of the following is true about Type 3 grammars (regular grammars)?
A) They can describe the syntax of programming languages
B) They generate regular languages
C) They can be parsed by a recursive descent parser
D) They require a pushdown automaton for recognition
Answer: B) They generate regular languages
8. What does a Turing machine model?
A) A finite state machine
B) A general-purpose computer
C) A pushdown automaton
D) A context-free grammar
Answer: B) A general-purpose computer
9. Which of the following grammars is capable of generating all recursively enumerable languages?
A) Type 0 grammar
B) Type 1 grammar
C) Type 2 grammar
D) Type 3 grammar
Answer: A) Type 0 grammar
10. Which of the following is used to describe a language recognized by a nondeterministic finite automaton (NFA)?
A) Regular grammar
B) Context-free grammar
C) Context-sensitive grammar
D) Recursively enumerable grammar
Answer: A) Regular grammar
11. Which of the following is the most powerful class of grammars in the Chomsky hierarchy?
A) Type 3 grammars
B) Type 2 grammars
C) Type 1 grammars
D) Type 0 grammars
Answer: D) Type 0 grammars
12. Which of the following automata can recognize languages generated by context-free grammars?
A) Finite state automaton (FSA)
B) Pushdown automaton (PDA)
C) Turing machine
D) Linear-bounded automaton (LBA)
Answer: B) Pushdown automaton (PDA)
13. Which of the following statements is true for a deterministic finite automaton (DFA)?
A) It accepts a context-free language
B) It uses a stack for memory
C) It accepts only regular languages
D) It can be used to recognize context-sensitive languages
Answer: C) It accepts only regular languages
14. Which of the following is true about Type 1 grammars (context-sensitive grammars)?
A) The production rules are context-free
B) They can be recognized by a Turing machine
C) They generate regular languages
D) They can be parsed using a deterministic finite automaton
Answer: B) They can be recognized by a Turing machine
15. What is the pumping lemma used for in the context of regular languages?
A) To prove that a language is context-sensitive
B) To prove that a language is not regular
C) To demonstrate that a language is recursively enumerable
D) To minimize a finite automaton
Answer: B) To prove that a language is not regular
16. What is the key difference between Type 0 and Type 1 grammars?
A) Type 0 grammars generate regular languages, while Type 1 grammars generate context-free languages
B) Type 1 grammars have more restricted production rules than Type 0 grammars
C) Type 1 grammars can be recognized by a Turing machine, while Type 0 grammars cannot
D) Type 1 grammars generate languages that are not context-sensitive
Answer: B) Type 1 grammars have more restricted production rules than Type 0 grammars
17. Which of the following is not a property of regular languages?
A) Closed under union
B) Closed under intersection
C) Can be recognized by a DFA
D) Can be parsed by a pushdown automaton
Answer: D) Can be parsed by a pushdown automaton
18. Which type of grammar can be used to define recursive functions in programming languages?
A) Type 3 grammar
B) Type 2 grammar
C) Type 1 grammar
D) Type 0 grammar
Answer: B) Type 2 grammar
19. Which of the following describes a deterministic pushdown automaton (DPDA)?
A) It recognizes context-free languages
B) It can only recognize regular languages
C) It requires a stack to store symbols
D) It can recognize all context-sensitive languages
Answer: A) It recognizes context-free languages
20. Which class of languages can be recognized by a linear-bounded automaton (LBA)?
A) Regular languages
B) Context-free languages
C) Context-sensitive languages
D) Recursively enumerable languages
Answer: C) Context-sensitive languages