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-2
C.Type-3
D.Type-1
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 all non-terminals are replaced simultaneously.
B.A derivation where the leftmost non-terminal is always replaced at each step.
C.A derivation that only uses left-recursive production rules.
D.A derivation where the rightmost non-terminal is always replaced first.
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 regular expression
B.A sentential form
C.A parse tree
D.A terminal string
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 terminal string
C.A right-sentential form
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 there exists a string in the language that has more than one leftmost derivation or more than one parse tree.
B.If it has both nullable and unit productions.
C.If it contains left-recursive rules.
D.If it generates an infinite language.
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 ambiguous because the string 'aaa' has multiple parse trees.
B.The grammar generates the language .
C.The grammar is in Chomsky Normal Form.
D.The grammar is unambiguous.
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 Context-Free Grammar that generates the language is ambiguous.
B.The language contains the empty string .
C.The language can only be generated by a regular grammar.
D.Every string in the language has multiple parse trees.
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.No, but it can be decided if the grammar is in Greibach Normal Form.
B.Yes, using the CYK algorithm.
C.No, the problem is formally undecidable.
D.Yes, using the Pumping Lemma.
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.Database schema indexing
B.Lexical analysis and token generation
C.Syntax analysis (parsing) in compilers
D.Network routing algorithms
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.Turing Machine state diagrams
C.Deterministic Finite Automata (DFA)
D.Backus-Naur Form (BNF)
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.Awk
B.Grep
C.Lex
D.YACC (Yet Another Compiler Compiler)
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.6 parts ()
C.5 parts ()
D.4 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 language is NOT context-free.
B.To convert a grammar into Chomsky Normal Form.
C.To prove that a grammar is ambiguous.
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 .
B.A production of the form where is a terminal.
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 where the right-hand side is exactly one non-terminal: .
B.A rule that contains exactly one terminal and one non-terminal.
C.A rule that derives the empty string: .
D.A rule that derives a single terminal string: .
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 does not participate in the derivation of any string of terminals.
B.It appears on the left side of a unit production.
C.It derives the empty string .
D.It is only reachable from the start symbol.
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-generating symbols, then eliminate non-reachable symbols.
B.First eliminate non-reachable symbols, then eliminate non-generating symbols.
C.The order does not matter.
D.First eliminate unit productions, then non-reachable symbols.
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 -productions Eliminate unit productions
B.Eliminate useless symbols Eliminate unit productions Eliminate -productions
C.Eliminate unit productions Eliminate -productions Eliminate useless symbols
D.Eliminate -productions Eliminate unit productions Eliminate useless symbols
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.
B., where is a terminal.
C.
D.It cannot derive any string.
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 simply deleting it and making no other changes.
D.By merging the variables and into a single variable.
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 that has been converted to Chomsky Normal Form.
B.A grammar with only one production rule per non-terminal.
C.A grammar in which there are no unit productions, no -productions, and no useless symbols.
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. or
D. where is a string of variables
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 contains no terminal nodes.
B.It is a strictly binary tree (each internal node has exactly two children, except nodes leading to terminals).
C.It is a left-skewed tree.
D.It has a maximum depth of 3.
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?
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.2
B.1
C.Any number
D.3
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.Terminal symbols
C.Left recursion
D.Chomsky Normal Form rules
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.Complement only
B.Union, Concatenation, and Kleene Star
C.Intersection only
D.Intersection and Complement
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 undecidable.
D.It is neither regular nor context-free.
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.Turing Machines (TM)
B.Deterministic Finite Automata (DFA)
C.Pushdown Automata (PDA)
D.Linear Bounded Automata (LBA)
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.
C. and
D. and
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 root symbol of 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 set of all non-terminals used in 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.There is no difference between deterministic and non-deterministic CFLs.
B.Deterministic CFLs are exactly the languages accepted by Deterministic Pushdown Automata (DPDA).
C.Deterministic CFLs can only be generated by regular expressions.
D.Every Context-Free Language is deterministic.
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.Strings containing only variables
C.Strings of infinite length
D.The empty string
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 converts the language into a regular language.
B.It allows the grammar to be parsed unambiguously by default.
C.It minimizes the number of production rules.
D.It restricts the grammar so that algorithmic parsing (like CYK) and theoretical proofs become simpler.
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.Any sequence of variables and terminals.
B.Exactly one variable (non-terminal).
C.At least one terminal and one non-terminal.
D.A string of 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.Parallel derivation
B.Leftmost derivation
C.Rightmost derivation
D.Bottom-up 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.
Incorrect! Try again.
Did this save you a night before the exam?
LPU Notes is free, and it stays free. Ads cover part of the server bill.
The rest comes out of a student's own pocket: the domain, the storage,
and keeping the site up through the weeks everyone needs it at once.
The payment button didn't load. An ad blocker or a filtered network is the usual reason.
to try again.
Nothing here is ever locked, and nothing unlocks. Chip in only if it was worth it.
What it pays for →