1. Which of the following is NOT a type of grammar in Chomsky hierarchy?
a) Context-sensitive grammar
b) Regular grammar
c) Linear grammar
d) Context-free grammar
Answer: c) Linear grammar
Explanation: In Chomsky hierarchy, the types of grammars are categorized into four levels: Type 0 (Unrestricted), Type 1 (Context-sensitive), Type 2 (Context-free), and Type 3 (Regular). “Linear grammar” is not a recognized category in this hierarchy.
2. Which type of grammar allows productions where the left-hand side may be a single terminal or a single non-terminal?
a) Context-sensitive grammar
b) Regular grammar
c) Context-free grammar
d) Unrestricted grammar
Answer: c) Context-free grammar
Explanation: In context-free grammars, the left-hand side of productions must consist of a single non-terminal symbol, while the right-hand side can be any string of terminals and non-terminals without any restriction.
3. Which level of grammar in the Chomsky hierarchy is the most restrictive?
a) Type 0 (Unrestricted)
b) Type 1 (Context-sensitive)
c) Type 2 (Context-free)
d) Type 3 (Regular)
Answer: d) Type 3 (Regular)
Explanation: Type 3 grammars, also known as regular grammars, are the most restrictive in the Chomsky hierarchy. They can be defined by regular expressions and can be recognized by finite automata.
4. Which type of grammar is represented by productions of the form A -> α, where A is a non-terminal symbol and α is a string of terminals and/or non-terminals?
a) Context-sensitive grammar
b) Context-free grammar
c) Regular grammar
d) Unrestricted grammar
Answer: b) Context-free grammar
Explanation: Context-free grammars have productions where the left-hand side consists of a single non-terminal symbol, and the right-hand side can be any string of terminals and non-terminals.
5. In context-sensitive grammars, the productions are of the form αAβ -> αγβ, where α, β, and γ are strings of terminals and/or non-terminals, and A is a non-terminal. This is an example of:
a) Left-linear grammar
b) Right-linear grammar
c) Linear context-sensitive grammar
d) Non-linear context-sensitive grammar
Answer: c) Linear context-sensitive grammar
Explanation: Context-sensitive grammars where the productions have the form αAβ -> αγβ, where α, β, and γ are strings of terminals and/or non-terminals, and A is a non-terminal, are called linear context-sensitive grammars.
6. Which of the following is true regarding regular grammars?
a) Regular grammars can generate languages that are not recognized by finite automata.
b) Regular grammars can generate any context-free language.
c) Regular grammars can have productions with left-hand sides containing multiple non-terminals.
d) Regular grammars can be represented by regular expressions.
Answer: d) Regular grammars can be represented by regular expressions.
Explanation: Regular grammars can be defined using regular expressions, and they can be recognized by finite automata.
7. Ambiguity in context-free grammars arises when:
a) There are multiple parse trees for a single string.
b) The grammar contains only one non-terminal symbol.
c) The grammar is in Chomsky normal form.
d) The grammar has no nullable productions.
Answer: a) There are multiple parse trees for a single string.
Explanation: Ambiguity occurs in context-free grammars when a single string can be derived by multiple parse trees, leading to multiple possible interpretations.
8. Which of the following is NOT a method to simplify a context-free grammar?
a) Eliminating unit productions
b) Eliminating null productions
c) Introducing more non-terminals
d) Removing unreachable symbols
Answer: c) Introducing more non-terminals
Explanation: Simplification of a context-free grammar typically involves eliminating unit productions, null productions, and unreachable symbols, rather than introducing more non-terminals.
9. Which normal form allows productions of the form A -> BC, where A, B, and C are non-terminals?
a) Chomsky normal form
b) Greibach normal form
c) Right-normal form
d) Left-normal form
Answer: b) Greibach normal form
Explanation: Greibach normal form allows productions of the form A -> BC, where A, B, and C are non-terminals. In Chomsky normal form, productions are either of the form A -> BC or A -> a, where A, B, and C are non-terminals and ‘a’ is a terminal.
10. Which of the following is true regarding Chomsky normal form (CNF)?
a) CNF allows productions of the form A -> αB, where A and B are non-terminals and α is a string of terminals and/or non-terminals.
b) CNF allows ε-productions.
c) CNF allows unit productions.
d) CNF allows left recursion.
Answer: b) CNF allows ε-productions.
Explanation: Chomsky normal form (CNF) does not allow ε-productions. It requires productions to be either of the form A -> BC or A -> a, where A, B, and C are non-terminals and ‘a’ is a terminal.
11. Which of the following automata is equivalent to a regular grammar?
a) Turing machine
b) Pushdown automaton
c) Finite state machine
d) Queue automaton
Answer: c) Finite state machine
Explanation: Regular grammars can be recognized by finite state machines, also known as finite automata.
12. The process of eliminating null productions from a context-free grammar involves:
a) Removing productions that derive the empty string.
b) Replacing non-terminals that can derive the empty string with their corresponding productions.
c) Introducing new non-terminals to represent ε-productions.
d) Eliminating productions that contain only terminals.
Answer: b) Replacing non-terminals that can derive the empty string with their corresponding productions.
Explanation: Null productions are productions that derive the empty string (ε). To eliminate them, non-terminals that can derive ε are replaced with their corresponding productions in all other productions where they appear.
13. Which of the following statements about context-sensitive grammars is false?
a) Context-sensitive grammars can generate languages that cannot be recognized by a linear-bounded automaton.
b) Context-sensitive grammars allow rewriting rules where the length of the right-hand side can be different from the length of the left-hand side.
c) Context-sensitive grammars are more powerful than unrestricted grammars.
d) Context-sensitive grammars are typically used to describe natural languages.
Answer: c) Context-sensitive grammars are more powerful than unrestricted grammars.
Explanation: Context-sensitive grammars are less powerful than unrestricted grammars, as unrestricted grammars can generate any recursively enumerable language, while context-sensitive grammars are limited to a subset of recursively enumerable languages.
14. The Chomsky hierarchy of grammars is based on:
a) The number of non-terminals in the grammar.
b) The complexity of productions in the grammar.
c) The number of terminals in the grammar.
d) The generative power of the grammar.
Answer: d) The generative power of the grammar.
Explanation: The Chomsky hierarchy classifies grammars based on their generative power, which reflects the complexity of the languages they can generate.
15. Which of the following is a characteristic of a context-free grammar in Chomsky normal form (CNF)?
a) Every production is of the form A -> αB, where A and B are non-terminals and α is a terminal or ε.
b) The grammar does not contain any null productions.
c) The grammar can be recognized by a pushdown automaton.
d) Left recursion is allowed in the productions.
Answer: a) Every production is of the form A -> αB, where A and B are non-terminals and α is a terminal or ε.
Explanation: Chomsky normal form (CNF) requires productions to be either of the form A -> BC or A -> a, where A, B, and C are non-terminals and ‘a’ is a terminal or ε.
16. Which of the following operations is NOT part of the process of converting a context-free grammar to a pushdown automaton?
a) Eliminating left recursion
b) Determinizing the automaton
c) Converting productions into transitions
d) Handling epsilon productions
Answer: a) Eliminating left recursion
Explanation: Converting a context-free grammar to a pushdown automaton typically involves operations such as converting productions into transitions, handling epsilon productions, and determinizing the resulting automaton. Eliminating left recursion is a step involved in removing left recursion from a grammar, which is not directly related to converting it into an automaton.
17. The Chomsky hierarchy of grammars is arranged in the following order of increasing generative power:
a) Type 0, Type 1, Type 2, Type 3
b) Type 1, Type 2, Type 3, Type 0
c) Type 3, Type 2, Type 1, Type 0
d) Type 0, Type 3, Type 2, Type 1
Answer: c) Type 3, Type 2, Type 1, Type 0
Explanation: The Chomsky hierarchy arranges grammars in the order of increasing generative power from Type 3 (regular grammars) to Type 0 (unrestricted grammars).
18. Which normal form requires every production to be of the form A -> aα, where A is a non-terminal, ‘a’ is a terminal, and α is either a terminal or a non-terminal?
a) Chomsky normal form
b) Greibach normal form
c) Right-normal form
d) Left-normal form
Answer: c) Right-normal form
Explanation: Right-normal form requires every production to be of the form A -> aα, where A is a non-terminal, ‘a’ is a terminal, and α is either a terminal or a non-terminal.
19. What is the primary advantage of using Chomsky normal form (CNF) for context-free grammars?
a) CNF allows for more efficient parsing algorithms.
b) CNF ensures that the grammar is unambiguous.
c) CNF simplifies the grammar, making it easier to reason about.
d) CNF allows for direct conversion to a finite automaton.
Answer: a) CNF allows for more efficient parsing algorithms.
Explanation: Chomsky normal form (CNF) simplifies the structure of context-free grammars, allowing for more efficient parsing algorithms such as CYK (Cocke–Younger–Kasami) algorithm.
20. Which of the following statements regarding unit productions in context-free grammars is true?
a) Unit productions are productions where the right-hand side contains only terminals.
b) Unit productions can be directly converted into regular expressions.
c) Eliminating unit productions does not affect the language generated by the grammar.
d) Unit productions are productions where the left-hand side and the right-hand side are the same non-terminal.
Answer: d) Unit productions are productions where the left-hand side and the right-hand side are the same non-terminal.
Explanation: Unit productions are productions where a single non-terminal symbol derives another non-terminal symbol directly, without any intervening terminals or non-terminals.