1. Which of the following is true about regular languages?
A) They can be recognized by a deterministic pushdown automaton (DPDA)
B) They can be described by regular expressions
C) They can be generated by context-free grammars
D) They require a Turing machine for recognition
Answer: B) They can be described by regular expressions
2. Which of the following types of grammars can generate regular languages?
A) Context-free grammar
B) Context-sensitive grammar
C) Regular grammar
D) Type 0 grammar
Answer: C) Regular grammar
3. Which of the following automata can accept a regular language?
A) Pushdown automaton (PDA)
B) Turing machine
C) Finite state automaton (FSA)
D) Linear-bounded automaton (LBA)
Answer: C) Finite state automaton (FSA)
4. Which of the following is true for context-free languages?
A) They are always regular languages
B) They are recognized by a finite state machine
C) They can be generated by a context-free grammar
D) They can only be described by a regular expression
Answer: C) They can be generated by a context-free grammar
5. Which of the following statements is true about context-free grammars?
A) They can generate only finite languages
B) They can be parsed by a finite state automaton
C) They generate languages that can be recognized by a pushdown automaton
D) They cannot describe programming languages
Answer: C) They generate languages that can be recognized by a pushdown automaton
6. Which of the following is NOT a property of regular languages?
A) They are closed under union
B) They are closed under intersection
C) They can be recognized by a Turing machine
D) They require a stack for recognition
Answer: D) They require a stack for recognition
7. What is the pumping lemma used for in the context of regular languages?
A) To prove that a language is context-free
B) To prove that a language is not regular
C) To minimize a finite automaton
D) To prove that a language is context-sensitive
Answer: B) To prove that a language is not regular
8. Which of the following grammars can generate context-free languages?
A) Regular grammar
B) Context-sensitive grammar
C) Type 0 grammar
D) Context-free grammar
Answer: D) Context-free grammar
9. What type of automaton is used to recognize context-free languages?
A) Finite state automaton
B) Pushdown automaton
C) Linear-bounded automaton
D) Turing machine
Answer: B) Pushdown automaton
10. Which of the following is an example of a regular language?
A) {a^n b^n | n ≥ 0}
B) {a^n b^n c^n | n ≥ 0}
C) {a^n | n ≥ 0}
D) {a^n b^n c^n d^n | n ≥ 0}
Answer: C) {a^n | n ≥ 0}
11. Which of the following is a correct property of context-free languages?
A) They are closed under union
B) They are closed under complement
C) They are closed under intersection
D) They are closed under reversal
Answer: A) They are closed under union
12. Which of the following cannot be recognized by a deterministic finite automaton (DFA)?
A) Regular language
B) Context-free language
C) Context-sensitive language
D) Regular expression
Answer: B) Context-free language
13. Which of the following is an example of a context-free language?
A) {a^n b^n | n ≥ 0}
B) {a^n b^n c^n | n ≥ 0}
C) {a^n | n ≥ 0}
D) {a^n b^n c^n d^n | n ≥ 0}
Answer: A) {a^n b^n | n ≥ 0}
14. Which of the following is true about the relationship between regular and context-free languages?
A) Every regular language is also a context-free language
B) Every context-free language is also a regular language
C) Regular languages and context-free languages are disjoint
D) Regular languages cannot be generated by context-free grammars
Answer: A) Every regular language is also a context-free language
15. Which of the following statements is correct about a regular grammar?
A) It generates a context-sensitive language
B) It generates a language that can be recognized by a finite state automaton
C) It generates a language that requires a stack for recognition
D) It can generate recursive languages
Answer: B) It generates a language that can be recognized by a finite state automaton
16. Which of the following types of languages can be both context-free and regular?
A) The set of all strings of the form {a^n b^n | n ≥ 0}
B) The set of all strings of the form {a^n b^n c^n | n ≥ 0}
C) The set of all strings of the form {a^n | n ≥ 0}
D) The set of all strings of the form {a^n b^n c^n d^n | n ≥ 0}
Answer: C) The set of all strings of the form {a^n | n ≥ 0}
17. Which of the following is true about context-free grammars (CFG)?
A) They generate regular languages
B) They can be parsed by a finite automaton
C) They can generate non-context-free languages
D) They cannot describe arithmetic expressions
Answer: C) They can generate non-context-free languages
18. What is the minimum number of states required to recognize a regular language using a deterministic finite automaton (DFA)?
A) 1
B) 2
C) 3
D) Depends on the language
Answer: D) Depends on the language
19. Which of the following languages is NOT context-free?
A) {a^n b^n | n ≥ 0}
B) {a^n b^n c^n | n ≥ 0}
C) {a^n b^n c^n d^n | n ≥ 0}
D) {a^n | n ≥ 0}
Answer: C) {a^n b^n c^n d^n | n ≥ 0}
20. Which of the following is a property of context-sensitive languages?
A) They are closed under union
B) They can be recognized by a pushdown automaton
C) They are generated by Type 0 grammars
D) They require a Turing machine for recognition
Answer: D) They require a Turing machine for recognition