1. Which of the following is the primary concern of formal language theory?
A) Syntax and semantics of programming languages
B) Memory management in compilers
C) The formal specification of programming languages
D) Code optimization techniques
Answer: A) Syntax and semantics of programming languages
2. Which of the following is a key concept in automata theory?
A) Syntax analysis
B) Context-free grammars
C) Finite state machines (FSM)
D) Attribute grammars
Answer: C) Finite state machines (FSM)
3. Which type of grammar is used to describe the syntax of most programming languages?
A) Regular grammar
B) Context-free grammar
C) Context-sensitive grammar
D) Type-0 grammar
Answer: B) Context-free grammar
4. What is a pushdown automaton (PDA) used for?
A) Accepting regular languages
B) Recognizing context-free languages
C) Processing context-sensitive languages
D) Parsing arithmetic expressions
Answer: B) Recognizing context-free languages
5. Which of the following is true about regular expressions?
A) Regular expressions can represent context-free languages
B) Regular expressions are more expressive than context-free grammars
C) Regular expressions can represent regular languages
D) Regular expressions are used for parsing
Answer: C) Regular expressions can represent regular languages
6. What is the Chomsky hierarchy used to classify?
A) Programming languages
B) Types of grammars and languages
C) Compiler optimization techniques
D) Automata models
Answer: B) Types of grammars and languages
7. Which of the following is a property of a context-free grammar (CFG)?
A) The grammar can be parsed by a deterministic finite automaton
B) It can be used to describe the syntax of most programming languages
C) It can only describe regular languages
D) It is restricted to describing simple arithmetic expressions
Answer: B) It can be used to describe the syntax of most programming languages
8. Which of the following is a limitation of a deterministic finite automaton (DFA)?
A) It can only accept regular languages
B) It cannot handle ambiguity in grammar
C) It requires infinite memory for computation
D) It cannot be used to parse context-free grammars
Answer: D) It cannot be used to parse context-free grammars
9. Which of the following describes a context-sensitive grammar (CSG)?
A) A grammar where the left side of every production rule can have more than one symbol
B) A grammar that can be parsed by a stack machine
C) A grammar whose production rules have the form of A → B where A and B are non-terminal symbols
D) A grammar that can describe all recursively enumerable languages
Answer: A) A grammar where the left side of every production rule can have more than one symbol
10. What is the primary difference between a regular language and a context-free language?
A) Regular languages are more expressive than context-free languages
B) Context-free languages can be recognized by a finite automaton, whereas regular languages cannot
C) Regular languages can be recognized by finite state machines, while context-free languages require a pushdown automaton
D) Context-free languages cannot be represented using regular expressions
Answer: C) Regular languages can be recognized by finite state machines, while context-free languages require a pushdown automaton
11. In the Chomsky hierarchy, which class of grammars can describe recursively enumerable languages?
A) Type 0 grammars
B) Type 1 grammars
C) Type 2 grammars
D) Type 3 grammars
Answer: A) Type 0 grammars
12. Which of the following is a property of an LL(1) parser?
A) It uses left recursion to parse input
B) It requires multiple passes over the input
C) It reads the input left to right and constructs a leftmost derivation
D) It can handle all types of grammars, including context-sensitive ones
Answer: C) It reads the input left to right and constructs a leftmost derivation
13. What is the pumping lemma used for in formal language theory?
A) To prove whether a language is regular
B) To convert context-free grammars into normal form
C) To generate valid syntax trees
D) To prove that a language is context-sensitive
Answer: A) To prove whether a language is regular
14. Which of the following is true about the pumping lemma for context-free languages?
A) It is used to prove that a language is context-sensitive
B) It applies only to regular languages
C) It provides a method to prove that a language is not context-free
D) It is used to minimize a context-free grammar
Answer: C) It provides a method to prove that a language is not context-free
15. Which of the following is true about recursive enumerable languages?
A) They can be recognized by a deterministic finite automaton
B) They can be recognized by a Turing machine
C) They are always context-free
D) They can be parsed by a pushdown automaton
Answer: B) They can be recognized by a Turing machine
16. Which of the following is a method used to minimize a deterministic finite automaton (DFA)?
A) Removing unreachable states
B) Applying the pumping lemma
C) Applying the Chomsky normal form
D) Converting to a nondeterministic finite automaton (NFA)
Answer: A) Removing unreachable states
17. Which parsing technique is specifically designed to parse context-free languages in a left-to-right manner?
A) Recursive descent parsing
B) LL parsing
C) LR parsing
D) SLR parsing
Answer: B) LL parsing
18. Which of the following is the main advantage of using LR parsing over LL parsing?
A) LR parsing is easier to implement
B) LR parsing can handle more complex grammars
C) LL parsing is more efficient
D) LL parsing is easier to understand and implement
Answer: B) LR parsing can handle more complex grammars
19. What does a Turing machine model?
A) A pushdown automaton
B) A finite state machine
C) A general-purpose computer
D) A regular expression engine
Answer: C) A general-purpose computer
20. Which of the following types of grammars can describe all context-sensitive languages?
A) Type 0 grammars
B) Type 1 grammars
C) Type 2 grammars
D) Type 3 grammars
Answer: B) Type 1 grammars