1Which of the following describes the formal definition of a Context-Free Grammar (CFG)?
A.A 4-tuple
B.A 4-tuple
C.A 5-tuple
D.A 7-tuple
Correct Answer: A 4-tuple
Explanation:A Context-Free Grammar is formally defined as a 4-tuple , where is a set of variables (non-terminals), is a set of terminals, is a set of production rules, and is the start symbol.
Incorrect! Try again.
2In the Chomsky Hierarchy, Context-Free Languages (CFLs) are classified as which type of language?
A.Type-0
B.Type-1
C.Type-2
D.Type-3
Correct Answer: Type-2
Explanation:In the Chomsky Hierarchy, Type-2 languages represent Context-Free Languages, which are generated by Context-Free Grammars.
Incorrect! Try again.
3Which of the following correctly defines the language generated by a Context-Free Grammar ?
A.
B.
C.
D.
Correct Answer:
Explanation:The language generated by a CFG, , consists of all strings of terminals () that can be derived from the start symbol in zero or more steps ().
Incorrect! Try again.
4What is a Leftmost Derivation (LMD) in a Context-Free Grammar?
A.A derivation where the rightmost non-terminal is always replaced first.
B.A derivation where all non-terminals are replaced simultaneously.
C.A derivation where the leftmost non-terminal is always replaced at each step.
D.A derivation that only uses left-recursive production rules.
Correct Answer: A derivation where the leftmost non-terminal is always replaced at each step.
Explanation:In a Leftmost Derivation (LMD), the leftmost variable (non-terminal) in the current sentential form is always the one chosen to be replaced by applying a production rule.
Incorrect! Try again.
5If represents a valid derivation in a CFG, what is called if it contains both variables and terminals?
A.A parse tree
B.A terminal string
C.A sentential form
D.A regular expression
Correct Answer: A sentential form
Explanation:Any string of variables and/or terminals that can be derived from the start symbol is called a sentential form.
Incorrect! Try again.
6If a sentential form is derived using exclusively a rightmost derivation, what is it specifically called?
A.A left-sentential form
B.A right-sentential form
C.A terminal string
D.A canonical sentence
Correct Answer: A right-sentential form
Explanation:A sentential form that occurs during a rightmost derivation is formally known as a right-sentential form.
Incorrect! Try again.
7When is a Context-Free Grammar considered ambiguous?
A.If it contains left-recursive rules.
B.If there exists a string in the language that has more than one leftmost derivation or more than one parse tree.
C.If it generates an infinite language.
D.If it has both nullable and unit productions.
Correct Answer: If there exists a string in the language that has more than one leftmost derivation or more than one parse tree.
Explanation:A grammar is ambiguous if there is at least one string in its language that can be generated by two or more distinct leftmost derivations (which corresponds to having two or more distinct parse trees).
Incorrect! Try again.
8Consider the grammar . Which of the following statements is true?
A.The grammar is unambiguous.
B.The grammar is ambiguous because the string 'aaa' has multiple parse trees.
C.The grammar generates the language .
D.The grammar is in Chomsky Normal Form.
Correct Answer: The grammar is ambiguous because the string 'aaa' has multiple parse trees.
Explanation:The grammar is ambiguous because strings like 'aaa' can be derived in multiple ways, yielding different parse trees (e.g., grouping either left or right).
Incorrect! Try again.
9What does it mean for a Context-Free Language to be 'inherently ambiguous'?
A.Every string in the language has multiple parse trees.
B.The language can only be generated by a regular grammar.
C.Every Context-Free Grammar that generates the language is ambiguous.
D.The language contains the empty string .
Correct Answer: Every Context-Free Grammar that generates the language is ambiguous.
Explanation:A language is inherently ambiguous if there is no unambiguous grammar that can generate it; every valid CFG for this language will contain ambiguity.
Incorrect! Try again.
10Is the problem of determining whether an arbitrary Context-Free Grammar is ambiguous decidable?
A.Yes, using the Pumping Lemma.
B.Yes, using the CYK algorithm.
C.No, the problem is formally undecidable.
D.No, but it can be decided if the grammar is in Greibach Normal Form.
Correct Answer: No, the problem is formally undecidable.
Explanation:It is a well-known theorem in formal language theory that determining whether an arbitrary Context-Free Grammar is ambiguous is an undecidable problem. No general algorithm exists to solve it.
Incorrect! Try again.
11Which of the following strings is NOT derivable from the grammar ?
A.
B.
C.
D.
Correct Answer:
Explanation:The grammar generates the language . The string does not fit this pattern, as all 'a's must precede all 'b's.
Incorrect! Try again.
12What is the primary application of Context-Free Grammars in computer science?
A.Lexical analysis and token generation
B.Syntax analysis (parsing) in compilers
C.Network routing algorithms
D.Database schema indexing
Correct Answer: Syntax analysis (parsing) in compilers
Explanation:Context-Free Grammars are extensively used in the syntax analysis phase of a compiler to specify the syntactic structure of programming languages and to build parsers.
Incorrect! Try again.
13Which standard format is used to represent Context-Free Grammars in the design of programming languages?
A.Regular Expressions (RE)
B.Backus-Naur Form (BNF)
C.Turing Machine state diagrams
D.Deterministic Finite Automata (DFA)
Correct Answer: Backus-Naur Form (BNF)
Explanation:Backus-Naur Form (BNF) is a metasyntax notation widely used to express Context-Free Grammars, specifically for the syntax of computing programming languages.
Incorrect! Try again.
14Which popular parser generator tool directly utilizes Context-Free Grammars to generate C code for a parser?
A.Lex
B.Grep
C.YACC (Yet Another Compiler Compiler)
D.Awk
Correct Answer: YACC (Yet Another Compiler Compiler)
Explanation:YACC is a standard parser generator that takes a CFG specification (usually in a BNF-like format) and generates a syntax analyzer (parser) in C.
Incorrect! Try again.
15In the context of the Pumping Lemma for Context-Free Languages, a string is divided into how many parts?
A.3 parts ()
B.4 parts ()
C.5 parts ()
D.6 parts ()
Correct Answer: 5 parts ()
Explanation:The Pumping Lemma for CFLs states that any sufficiently long string in a CFL can be divided into five parts: .
Incorrect! Try again.
16According to the Pumping Lemma for Context-Free Languages, which of the following conditions must hold for the decomposition ?
A. and
B. and
C. and
D. and
Correct Answer: and
Explanation:The Pumping Lemma for CFLs requires that the middle portion has a length of at most the pumping length () and that the substrings and cannot be simultaneously empty ().
Incorrect! Try again.
17Which of the following is the 'pumped' string in the Pumping Lemma for Context-Free Languages?
A.
B.
C.
D.
Correct Answer:
Explanation:The lemma states that if is a CFL, then for any , the pumped string must also be in .
Incorrect! Try again.
18What is the primary purpose of the Pumping Lemma for Context-Free Languages?
A.To prove that a grammar is ambiguous.
B.To convert a grammar into Chomsky Normal Form.
C.To prove that a language is NOT context-free.
D.To find the shortest string generated by a CFG.
Correct Answer: To prove that a language is NOT context-free.
Explanation:Like the Pumping Lemma for regular languages, the Pumping Lemma for CFLs is primarily used in proofs by contradiction to show that a specific language is NOT context-free.
Incorrect! Try again.
19Which of the following languages is a classic example of a language that is NOT context-free, often proven using the Pumping Lemma?
A.
B.
C.
D.
Correct Answer:
Explanation:The language requires counting and matching three elements equally, which exceeds the capabilities of a pushdown automaton (and thus CFGs). It is famously proven non-context-free using the Pumping Lemma.
Incorrect! Try again.
20What defines a Null () production in a Context-Free Grammar?
A.A production of the form where is a terminal.
B.A production of the form .
C.A production where the start symbol is not used.
D.A production of the form where is a single variable.
Correct Answer: A production of the form .
Explanation:A null production, or -production, is a rule that replaces a non-terminal with the empty string ().
Incorrect! Try again.
21What is a Unit production in a Context-Free Grammar?
A.A rule that derives a single terminal string: .
B.A rule that derives the empty string: .
C.A rule where the right-hand side is exactly one non-terminal: .
D.A rule that contains exactly one terminal and one non-terminal.
Correct Answer: A rule where the right-hand side is exactly one non-terminal: .
Explanation:A unit production is a production rule of the form , where both and are single variables (non-terminals).
Incorrect! Try again.
22A variable in a CFG is called a 'useless symbol' if it satisfies which of the following conditions?
A.It is only reachable from the start symbol.
B.It does not participate in the derivation of any string of terminals.
C.It derives the empty string .
D.It appears on the left side of a unit production.
Correct Answer: It does not participate in the derivation of any string of terminals.
Explanation:A symbol is useless if it is non-generating (cannot derive a terminal string) or non-reachable (cannot be reached from the start symbol in any derivation). Therefore, it never appears in any successful derivation of a valid terminal string.
Incorrect! Try again.
23When eliminating useless symbols from a CFG, what is the correct order of the two main steps to ensure all useless symbols are properly removed?
A.First eliminate non-reachable symbols, then eliminate non-generating symbols.
B.First eliminate non-generating symbols, then eliminate non-reachable symbols.
C.First eliminate unit productions, then non-reachable symbols.
D.The order does not matter.
Correct Answer: First eliminate non-generating symbols, then eliminate non-reachable symbols.
Explanation:To successfully remove all useless symbols, you must first find and eliminate all non-generating variables (and rules containing them). Then, from the remaining grammar, you find and eliminate all variables and terminals that are not reachable from the start symbol. Doing it in reverse can leave useless symbols.
Incorrect! Try again.
24What is the recommended standard order for the three simplification steps of a Context-Free Grammar?
A.Eliminate useless symbols Eliminate unit productions Eliminate -productions
B.Eliminate -productions Eliminate unit productions Eliminate useless symbols
C.Eliminate unit productions Eliminate -productions Eliminate useless symbols
D.Eliminate useless symbols Eliminate -productions Eliminate unit productions
Correct Answer: Eliminate -productions Eliminate unit productions Eliminate useless symbols
Explanation:The standard sequence to guarantee a fully simplified grammar without re-introducing bad rules is: 1) Eliminate -productions, 2) Eliminate Unit productions, 3) Eliminate Useless symbols.
Incorrect! Try again.
25In a CFG, a variable is termed 'nullable' if it meets which condition?
A.It cannot derive any string.
B.
C.
D., where is a terminal.
Correct Answer:
Explanation:A variable is nullable if it can derive the empty string in one or more steps ().
Incorrect! Try again.
26Consider a grammar with the production , where both and are nullable variables. When eliminating -productions, which new productions must be added for ?
A.
B.
C.
D.
Correct Answer:
Explanation:If and can derive , replacing combinations of and with yields , (when ), and (when ). We do not add unless itself is being evaluated as nullable at the root level, but strictly the RHS variations are .
Incorrect! Try again.
27How is a unit production eliminated from a grammar?
A.By replacing it with .
B.By adding the rule for every non-unit rule .
C.By merging the variables and into a single variable.
D.By simply deleting it and making no other changes.
Correct Answer: By adding the rule for every non-unit rule .
Explanation:To eliminate a unit production , you find all non-unit productions of (e.g., ) and add the productions directly to .
Incorrect! Try again.
28Which of the following best defines a 'reduced grammar'?
A.A grammar with only one production rule per non-terminal.
B.A grammar in which there are no unit productions, no -productions, and no useless symbols.
C.A grammar that has been converted to Chomsky Normal Form.
D.A grammar that generates a finite language.
Correct Answer: A grammar in which there are no unit productions, no -productions, and no useless symbols.
Explanation:A reduced CFG is one that has undergone simplification to remove all -productions (except possibly for the start symbol), all unit productions, and all useless symbols.
Incorrect! Try again.
29What is the specific format of production rules in Chomsky Normal Form (CNF)?
A. or
B. or
C. where is a string of variables
D. or
Correct Answer: or
Explanation:In Chomsky Normal Form (CNF), every production rule must be of the form (two variables) or (one terminal).
Incorrect! Try again.
30If a string of length () is generated by a grammar in Chomsky Normal Form, exactly how many steps are in its derivation?
A.
B.
C.
D.
Correct Answer:
Explanation:In CNF, deriving a string of length requires exactly rule applications of the form (to generate variables) and applications of the form (to convert variables to terminals). Total steps = .
Incorrect! Try again.
31What structural property does the parse tree of a string derived from a CFG in Chomsky Normal Form possess?
A.It is a left-skewed tree.
B.It is a strictly binary tree (each internal node has exactly two children, except nodes leading to terminals).
C.It has a maximum depth of 3.
D.It contains no terminal nodes.
Correct Answer: It is a strictly binary tree (each internal node has exactly two children, except nodes leading to terminals).
Explanation:Because all non-terminal rules in CNF take the form , every internal node in the parse tree branching to variables has exactly two children. Terminals are single children ().
Incorrect! Try again.
32Which dynamic programming algorithm relies on the grammar being in Chomsky Normal Form to check string membership in a CFL?
Explanation:The CYK algorithm is a standard parsing algorithm that determines whether a string can be generated by a CFG. It requires the grammar to be in Chomsky Normal Form.
Incorrect! Try again.
33What is the maximum number of variables on the right-hand side of a production rule in Chomsky Normal Form?
A.1
B.2
C.3
D.Any number
Correct Answer: 2
Explanation:In CNF, the allowed forms are or . Therefore, the maximum number of variables on the right side is exactly 2.
Incorrect! Try again.
34What is the specific format of production rules in Greibach Normal Form (GNF)?
A. or
B., where is a single terminal and is a string of zero or more variables.
C. or
D., where is a terminal and is a string of variables.
Correct Answer: , where is a single terminal and is a string of zero or more variables.
Explanation:In Greibach Normal Form (GNF), every production rule must start with exactly one terminal, optionally followed by any number of non-terminals (variables): .
Incorrect! Try again.
35If a string of length is generated by a grammar in Greibach Normal Form, exactly how many derivation steps are required?
A.
B.
C.
D.
Correct Answer:
Explanation:In GNF, every production rule generates exactly one terminal symbol. Therefore, to generate a string of length , exactly derivation steps are required.
Incorrect! Try again.
36Before converting a Context-Free Grammar into Greibach Normal Form, which structural issue MUST be eliminated from the grammar?
A.Right recursion
B.Left recursion
C.Chomsky Normal Form rules
D.Terminal symbols
Correct Answer: Left recursion
Explanation:Left recursion (e.g., ) prevents a grammar from being converted into GNF because GNF requires every rule to start with a terminal, consuming input on the left.
Incorrect! Try again.
37Which of the following rules is an example of immediate left recursion?
A.
B.
C.
D.
Correct Answer:
Explanation:Immediate left recursion occurs when a production rule has the same non-terminal on the left side and at the very beginning of the right side, such as .
Incorrect! Try again.
38Context-Free Languages are closed under which of the following operations?
A.Intersection and Complement
B.Union, Concatenation, and Kleene Star
C.Intersection only
D.Complement only
Correct Answer: Union, Concatenation, and Kleene Star
Explanation:CFLs are closed under union, concatenation, and Kleene star operations. They are NOT closed under intersection or complementation.
Incorrect! Try again.
39If is a Context-Free Language and is a Regular Language, what can be said about ?
A.It is always a Regular Language.
B.It is always a Context-Free Language.
C.It is neither regular nor context-free.
D.It is undecidable.
Correct Answer: It is always a Context-Free Language.
Explanation:The intersection of a Context-Free Language and a Regular Language is always a Context-Free Language. This is known as the closure property under regular intersection.
Incorrect! Try again.
40Greibach Normal Form (GNF) is particularly useful for demonstrating the equivalence between Context-Free Grammars and which computational model?
A.Deterministic Finite Automata (DFA)
B.Pushdown Automata (PDA)
C.Linear Bounded Automata (LBA)
D.Turing Machines (TM)
Correct Answer: Pushdown Automata (PDA)
Explanation:GNF is structurally very close to how a PDA operates. Because each rule generates exactly one terminal, it naturally mirrors a PDA consuming one input symbol per transition.
Incorrect! Try again.
41When eliminating immediate left recursion of the form , which new set of productions correctly replaces it? (Assume is a new variable)
A. and
B. and
C. and
D.
Correct Answer: and
Explanation:The standard algorithm to eliminate immediate left recursion converts into right recursion: and .
Incorrect! Try again.
42What is the 'yield' of a parse tree?
A.The set of all non-terminals used in the tree.
B.The height of the longest branch in the tree.
C.The concatenation of all the leaves of the tree from left to right.
D.The root symbol of the tree.
Correct Answer: The concatenation of all the leaves of the tree from left to right.
Explanation:The yield of a parse tree is the string formed by reading the labels of the leaf nodes from left to right. This forms the sentential form or terminal string derived by the tree.
Incorrect! Try again.
43Which of the following grammars generates the language of all palindromes over the alphabet ?
A.
B.
C.
D.
Correct Answer:
Explanation:Palindromes read the same forwards and backwards. The rules and ensure symmetry. The rules handle the middle of odd-length and even-length palindromes.
Incorrect! Try again.
44Which of the following is true regarding deterministic vs non-deterministic Context-Free Languages?
A.Every Context-Free Language is deterministic.
B.Deterministic CFLs are exactly the languages accepted by Deterministic Pushdown Automata (DPDA).
C.There is no difference between deterministic and non-deterministic CFLs.
D.Deterministic CFLs can only be generated by regular expressions.
Correct Answer: Deterministic CFLs are exactly the languages accepted by Deterministic Pushdown Automata (DPDA).
Explanation:Unlike finite automata, non-deterministic PDAs are strictly more powerful than deterministic PDAs. The languages accepted by DPDAs form a proper subset of all CFLs, called Deterministic Context-Free Languages (DCFLs).
Incorrect! Try again.
45If and are Context-Free Languages, which operation is NOT guaranteed to produce a Context-Free Language?
A.
B.
C.
D.
Correct Answer:
Explanation:CFLs are closed under union (), concatenation (), and Kleene Star (). They are NOT closed under intersection ().
Incorrect! Try again.
46Consider the CFG: , , . What is the language generated by this grammar?
A.
B.
C.
D.
Correct Answer:
Explanation:The variable generates one or more 'a's (). The variable generates one or more 'b's (). Concatenating them gives , which means any sequence of 'a's followed by any sequence of 'b's (at least one of each).
Incorrect! Try again.
47If a CFG is simplified to eliminate null productions, which string might be accidentally removed from its language if not handled carefully?
A.Any string of length 1
B.The empty string
C.Strings containing only variables
D.Strings of infinite length
Correct Answer: The empty string
Explanation:If the original language contains the empty string , completely eliminating all -productions will remove from the language. To fix this, is typically allowed if doesn't appear on the right side.
Incorrect! Try again.
48What is the primary benefit of converting a Context-Free Grammar into Chomsky Normal Form (CNF)?
A.It minimizes the number of production rules.
B.It allows the grammar to be parsed unambiguously by default.
C.It restricts the grammar so that algorithmic parsing (like CYK) and theoretical proofs become simpler.
D.It converts the language into a regular language.
Correct Answer: It restricts the grammar so that algorithmic parsing (like CYK) and theoretical proofs become simpler.
Explanation:CNF imposes a strict structure ( or ) that standardizes parse trees as binary trees, making algorithms like CYK possible and derivation lengths highly predictable ().
Incorrect! Try again.
49Which component is missing from this partial definition of a context-free rule: 'The left-hand side of a production rule must consist of...'?
A.At least one terminal and one non-terminal.
B.Exactly one variable (non-terminal).
C.A string of terminals.
D.Any sequence of variables and terminals.
Correct Answer: Exactly one variable (non-terminal).
Explanation:By the definition of a Context-Free Grammar (Type-2), the left-hand side of every production rule must be exactly one single variable (non-terminal). This is what makes it 'context-free'.
Incorrect! Try again.
50What type of derivation generates the tree nodes in a depth-first, left-to-right manner?
A.Rightmost derivation
B.Leftmost derivation
C.Bottom-up derivation
D.Parallel derivation
Correct Answer: Leftmost derivation
Explanation:A leftmost derivation continually expands the leftmost non-terminal, naturally corresponding to building the parse tree in a depth-first, left-to-right order.