Context-free grammars (CFG)(MCQs)
What is a context-free grammar (CFG)?
a) A grammar where each production rule has a single non-terminal on the left-hand side
b) A grammar where production rules can have multiple non-terminals on the left-hand side
c) A grammar where production rules include both terminals and non-terminals
d) A grammar used for defining regular languages
Answer: a) A grammar where each production rule has a single non-terminal on the left-hand side
Which of the following is a characteristic of a context-free grammar?
a) Each production rule has a single non-terminal symbol on the left-hand side
b) Each production rule can have multiple non-terminals on the left-hand side
c) Production rules can only include terminals
d) Production rules can have a mix of terminals and non-terminals on the left-hand side
Answer: a) Each production rule has a single non-terminal symbol on the left-hand side
Which of the following languages is NOT context-free?
a) The set of balanced parentheses
b) The set of strings of the form a^n b^n
c) The set of strings with equal numbers of a and b
d) The set of palindromes over the alphabet {a, b}
Answer: d) The set of palindromes over the alphabet {a, b}
What is a terminal symbol in a context-free grammar?
a) A symbol that appears in the final strings generated by the grammar
b) A symbol that can be replaced by other symbols in production rules
c) A symbol used to denote non-terminal categories
d) A symbol that does not appear in the final strings generated by the grammar
Answer: a) A symbol that appears in the final strings generated by the grammar
Which of the following is a valid CFG production rule?
a) A → aB | b
b) AB → a
c) aA → B
d) A → a | B
Answer: a) A → aB | b
In a CFG, what does the start symbol represent?
a) The initial non-terminal from which derivations begin
b) A terminal symbol that must appear in the final string
c) A non-terminal symbol that represents the end of the derivation
d) A placeholder for future production rules
Answer: a) The initial non-terminal from which derivations begin
What is the main difference between context-free grammars (CFGs) and regular grammars?
a) CFGs can generate languages with nested structures, while regular grammars cannot
b) Regular grammars can generate languages with nested structures, while CFGs cannot
c) CFGs are less powerful than regular grammars
d) CFGs cannot generate any language that regular grammars can
Answer: a) CFGs can generate languages with nested structures, while regular grammars cannot
Which of the following is a context-free language?
a) {a^n b^n | n ≥ 0}
b) {a^n b^n c^n | n ≥ 0}
c) {a^n b^n | n ≥ 1, n is odd}
d) {a^n b^n c^m | n, m ≥ 0}
Answer: a) {a^n b^n | n ≥ 0}
Which of the following rules is an example of a right-linear grammar?
a) A → aB
b) A → a | B
c) A → a | aB
d) A → AB | a
Answer: a) A → aB
In CFGs, what is a non-terminal symbol?
a) A symbol that can be replaced by other symbols in production rules
b) A symbol that represents terminal categories in the grammar
c) A symbol that appears in the final strings generated by the grammar
d) A symbol that indicates the end of the derivation
Answer: a) A symbol that can be replaced by other symbols in production rules
Which of the following is a property of context-free grammars?
a) They can be parsed using a pushdown automaton
b) They can be parsed using a finite automaton
c) They can only generate regular languages
d) They cannot handle recursive structures
Answer: a) They can be parsed using a pushdown automaton
Which of the following is a correct CFG for the language of balanced parentheses?
a) S → (S)S | ε
b) S → (S) | S
c) S → (S)S | S
d) S → (S) | ε
Answer: a) S → (S)S | ε
What is an example of a context-free grammar production rule that generates strings with exactly one a and one b in any order?
a) S → aSb | bSa | ε
b) S → a | b
c) S → aSb | bSa | ε
d) S → aAb | bAa
Answer: a) S → aSb | bSa | ε
Which property is NOT true for context-free grammars?
a) They can describe all regular languages
b) They can be used to describe languages with nested structures
c) They can describe languages requiring counting of multiple symbols
d) They cannot be parsed by finite automata
Answer: c) They can describe languages requiring counting of multiple symbols
Which CFG production rule is NOT valid for generating the language {a^n b^n | n ≥ 0}?
a) S → aSb | bSa | ε
b) S → aSb | ε
c) S → aS | bS | ε
d) S → aSb | bSa | ε
Answer: c) S → aS | bS | ε
Which parsing technique is commonly used for context-free grammars?
a) LL Parsing
b) LR Parsing
c) Recursive Descent Parsing
d) All of the above
Answer: d) All of the above
What is a common use of context-free grammars in computer science?
a) Designing programming languages
b) Implementing regular expressions
c) Managing databases
d) Creating graphical user interfaces
Answer: a) Designing programming languages
What is the Chomsky Normal Form (CNF) for a CFG?
a) A form where each production rule is either A → BC or A → a
b) A form where each production rule is either A → aB or A → Ba
c) A form where each production rule is A → B or A → aB
d) A form where each production rule is A → a | B
Answer: a) A form where each production rule is either A → BC or A → a
In CFGs, what does the term ‘derivation’ refer to?
a) The process of generating a string from the start symbol using production rules
b) The process of parsing a string using a finite automaton
c) The process of identifying terminal symbols
d) The process of defining the start symbol
Answer: a) The process of generating a string from the start symbol using production rules
Which of the following grammars is in Chomsky Normal Form (CNF)?
a) A → aB | b
b) A → aB | bC
c) A → a | B | C
d) A → AB | BC
Answer: d) A → AB | BC
What is the primary difference between LL and LR parsing techniques for context-free grammars?
a) LL parsing is top-down while LR parsing is bottom-up
b) LL parsing is bottom-up while LR parsing is top-down
c) LL parsing handles ambiguous grammars better than LR parsing
d) LR parsing is used for regular languages while LL parsing is used for context-free languages
Answer: a) LL parsing is top-down while LR parsing is bottom-up
What does ‘Left Recursion’ mean in the context of CFGs?
a) A non-terminal that derives itself as the leftmost symbol in one of its productions
b) A terminal symbol that appears on the left-hand side of a production rule
c) A non-terminal that derives itself as the rightmost symbol in one of its productions
d) A terminal that can be derived recursively
Answer: a) A non-terminal that derives itself as the leftmost symbol in one of its productions
Which of the following is a method to eliminate left recursion in CFGs?
a) Rewriting the production rules to use right recursion
b) Adding extra terminal symbols
c) Using a different set of terminal symbols
d) Removing non-terminals
Answer: a) Rewriting the production rules to use right recursion
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 | n is even}
d) {a^n b^n | n is odd}
Answer: b) {a^n b^n c^n | n ≥ 0}
In CFGs, what is the purpose of a ‘parse tree’?
a) To visually represent the derivation of a string from the start symbol
b) To represent the regular expressions used in the grammar
c) To store the terminal symbols in the grammar
d) To document the terminal and non-terminal symbols
Answer: a) To visually represent the derivation of a string from the start symbol
What is the purpose of the CYK algorithm?
a) To parse context-free grammars in Chomsky Normal Form (CNF)
b) To optimize context-free grammar rules
c) To convert CFGs into regular expressions
d) To generate parse trees for context-free languages
Answer: a) To parse context-free grammars in Chomsky Normal Form (CNF)
Which grammar is more powerful: Context-Free Grammar (CFG) or Regular Grammar?
a) Context-Free Grammar (CFG)
b) Regular Grammar
c) Both are equally powerful
d) Neither is powerful
Answer: a) Context-Free Grammar (CFG)
Which of the following is an example of a context-free grammar production rule for strings of the form a^n b^n?
a) S → aSb | bSa | ε
b) S → aSb | bS | ε
c) S → aSb | ε
d) S → aSb | bS | a
Answer: c) S → aSb | ε
Which of the following languages can be generated by a context-free grammar?
a) {a^n b^n | n ≥ 0}
b) {a^n b^n c^n | n ≥ 0}
c) {a^n b^n | n is prime}
d) {a^n b^n c^n d^n | n ≥ 0}
Answer: a) {a^n b^n | n ≥ 0}
What is the primary use of context-free grammars in programming languages?
a) To define the syntax of programming languages
b) To manage memory allocation
c) To implement runtime environments
d) To handle hardware interactions
Answer: a) To define the syntax of programming languages
In a CFG, what does ‘ambiguous grammar’ refer to?
a) A grammar that can generate a string with more than one parse tree
b) A grammar that generates an empty language
c) A grammar that has no terminal symbols
d) A grammar that only generates palindromes
Answer: a) A grammar that can generate a string with more than one parse tree
What does ‘Eliminating Ambiguity’ involve in CFGs?
a) Reformulating the grammar so that each string has a unique parse tree
b) Introducing more non-terminals
c) Adding more terminal symbols
d) Simplifying production rules
Answer: a) Reformulating the grammar so that each string has a unique parse tree
Which type of grammar can be parsed by a recursive descent parser?
a) LL(1) grammars
b) LR(1) grammars
c) SLR(1) grammars
d) LALR(1) grammars
Answer: a) LL(1) grammars
Which of the following techniques is used to convert CFGs into a form suitable for parsing?
a) Chomsky Normal Form (CNF) conversion
b) Regular Expression conversion
c) Pushdown Automaton conversion
d) Finite Automaton conversion
Answer: a) Chomsky Normal Form (CNF) conversion
In CFGs, what does ‘First’ set represent?
a) The set of terminals that begin the strings derivable from a non-terminal
b) The set of terminals that end the strings derivable from a non-terminal
c) The set of non-terminals that are directly reachable from the start symbol
d) The set of terminal symbols used in production rules
Answer: a) The set of terminals that begin the strings derivable from a non-terminal
In CFGs, what does ‘Follow’ set represent?
a) The set of terminals that can appear immediately to the right of a non-terminal in any valid derivation
b) The set of terminals that can appear immediately to the left of a non-terminal in any valid derivation
c) The set of all non-terminals reachable from a start symbol
d) The set of terminals used in the production rules
Answer: a) The set of terminals that can appear immediately to the right of a non-terminal in any valid derivation
Which of the following is a valid production rule in Chomsky Normal Form (CNF)?
a) A → a
b) A → B | C
c) A → aB | bC
d) A → aB | b
Answer: a) A → a
Which of the following best describes ‘Right-Linear Grammar’?
a) A grammar where production rules have the form A → xB or A → x, where x is a terminal string
b) A grammar where production rules have the form A → Bx or A → x, where x is a terminal string
c) A grammar where production rules have the form A → Bx or A → xB
d) A grammar with mixed terminal and non-terminal symbols on the left-hand side
Answer: a) A grammar where production rules have the form A → xB or A → x, where x is a terminal string
Which of the following is an example of a left-linear grammar?
a) A → aB
b) A → Ba
c) A → a | bB
d) A → aB | b
Answer: b) A → Ba
Which CFG production rule is NOT in Chomsky Normal Form (CNF)?
a) S → aB
b) S → AB
c) S → a
d) S → a | b
Answer: d) S → a | b
What does ‘Terminals’ mean in a CFG?
a) Symbols that appear in the final strings generated by the grammar
b) Symbols used to represent non-terminal categories
c) Symbols used to denote the start of the grammar
d) Symbols that do not appear in the final strings generated by the grammar
Answer: a) Symbols that appear in the final strings generated by the grammar
What is a parse tree in the context of CFGs?
a) A tree structure representing the syntactic structure of a string according to the CFG
b) A list of terminals in the grammar
c) A graph showing the grammar rules
d) A flowchart for generating strings
Answer: a) A tree structure representing the syntactic structure of a string according to the CFG
Which parsing technique uses a stack to handle non-terminals?
a) LR Parsing
b) LL Parsing
c) Recursive Descent Parsing
d) CYK Algorithm
Answer: a) LR Parsing
Which of the following is true about context-free grammars?
a) They can be used to describe programming language syntax
b) They are limited to describing regular languages only
c) They cannot handle recursive structures
d) They are less powerful than regular grammars
Answer: a) They can be used to describe programming language syntax
What does ‘Eliminating Left Recursion’ achieve in CFGs?
a) It makes the grammar suitable for top-down parsing techniques
b) It makes the grammar more ambiguous
c) It simplifies the grammar by removing all non-terminal symbols
d) It allows the grammar to be used for bottom-up parsing techniques
Answer: a) It makes the grammar suitable for top-down parsing techniques
In a CFG, which of the following is a common use of epsilon (ε) productions?
a) To allow the derivation of empty strings
b) To denote terminal symbols
c) To represent end-of-file markers
d) To convert CFGs to regular expressions
Answer: a) To allow the derivation of empty strings
What is the purpose of the CYK algorithm in relation to context-free grammars?
a) To parse strings according to CFGs in Chomsky Normal Form (CNF)
b) To convert CFGs into regular expressions
c) To simplify CFG production rules
d) To handle ambiguous CFGs
Answer: a) To parse strings according to CFGs in Chomsky Normal Form (CNF)
Which of the following CFG productions is an example of a right-recursive rule?
a) S → aSb
b) S → bSa
c) S → a | b
d) S → aS | b
Answer: a) S → aSb
In a CFG, which of the following rules can generate a language with nested structures?
a) S → aSb | bSa | ε
b) S → a | b
c) S → aSb
d) S → a | bS
Answer: a) S → aSb | bSa | ε
What is the main goal of converting a CFG into Chomsky Normal Form (CNF)?
a) To make the grammar suitable for parsing algorithms like CYK
b) To simplify the grammar by removing all terminals
c) To add more non-terminals to the grammar
d) To create a grammar that generates regular languages only
Answer: a) To make the grammar suitable for parsing algorithms like CYK