1A Pushdown Automaton (PDA) is formally defined as a 7-tuple: . What does represent?
A.Stack alphabet
B.Set of internal states
C.Transition function
D.Input alphabet
Correct Answer: Stack alphabet
Explanation:
In the 7-tuple definition of a PDA, represents the finite set of symbols that can be pushed onto the stack, known as the stack alphabet.
Incorrect! Try again.
2Which fundamental data structure is used in the computational model of a Pushdown Automaton?
A.Queue
B.Linked List
C.Stack
D.Hash Table
Correct Answer: Stack
Explanation:
A Pushdown Automaton acts like a finite automaton but includes an auxiliary memory in the form of a stack (Last-In-First-Out data structure).
Incorrect! Try again.
3For a Non-Deterministic Pushdown Automaton (NPDA), the transition function is a mapping defined as:
A.
B.
C.
D.
Correct Answer:
Explanation:
The transition function of an NPDA takes a current state, an input symbol (or ), and a top stack symbol, and maps them to a set of pairs consisting of a new state and a string of stack symbols.
Incorrect! Try again.
4An Instantaneous Description (ID) of a PDA is typically represented by a triplet . What does represent in this notation?
A.The unread portion of the input string
B.The contents of the stack
C.The symbols already processed
D.The entire input string
Correct Answer: The unread portion of the input string
Explanation:
In an ID , is the current state, is the remaining (unread) input string, and represents the current stack contents.
Incorrect! Try again.
5What is the primary effect of an -transition in a Pushdown Automaton?
A.The PDA changes its state and/or stack contents without consuming any input symbol.
B.The PDA consumes an input symbol but leaves the stack unchanged.
C.The PDA halts its execution.
D.The PDA rejects the input string immediately.
Correct Answer: The PDA changes its state and/or stack contents without consuming any input symbol.
Explanation:
An -transition allows the PDA to make a move (change state and manipulate the stack) without reading any symbol from the input string.
Incorrect! Try again.
6A PDA accepts a string by 'empty stack' if, after completely reading the input string, the PDA is in:
A.Any state, and the stack is empty
B.A final state with an empty stack
C.The initial state with an empty stack
D.A final state, regardless of stack contents
Correct Answer: Any state, and the stack is empty
Explanation:
Acceptance by empty stack means that the PDA consumes the entire input string and the stack becomes completely empty, regardless of whether the current state is an accepting/final state.
Incorrect! Try again.
7Which of the following statements is true regarding the equivalence of acceptance by empty stack and acceptance by final state for NPDAs?
A.Both acceptance methods describe exactly the same class of languages.
B.Acceptance by empty stack is strictly more powerful.
C.Acceptance by final state is strictly more powerful.
D.They are equivalent only for Deterministic PDAs.
Correct Answer: Both acceptance methods describe exactly the same class of languages.
Explanation:
For Non-Deterministic Pushdown Automata, the class of languages accepted by empty stack is identical to the class of languages accepted by final state (i.e., Context-Free Languages).
Incorrect! Try again.
8If a language is accepted by a DPDA by empty stack, the language must possess the prefix property. What does the prefix property mean?
A.No string in is a proper prefix of another string in .
B.The language contains the empty string .
C.Every string in is a prefix of some string in the universal language.
D.All strings in share the same prefix.
Correct Answer: No string in is a proper prefix of another string in .
Explanation:
A language has the prefix property if no string in the language is a proper prefix of any other string in the language. DPDAs accepting by empty stack can only accept languages with this property.
Incorrect! Try again.
9When converting a PDA that accepts by empty stack into one that accepts by final state, what is a standard modification?
A.Adding a new start state and a new bottom-of-stack marker.
B.Duplicating the stack alphabet.
C.Making the initial state the only final state.
D.Removing all -transitions.
Correct Answer: Adding a new start state and a new bottom-of-stack marker.
Explanation:
To simulate empty stack acceptance with final state acceptance, we add a new bottom-of-stack symbol to prevent premature emptying and transition to a new final state when this symbol is exposed.
Incorrect! Try again.
10A Pushdown Automaton is equivalent in computational power to which type of grammar?
A.Context-Sensitive Grammar
B.Regular Grammar
C.Context-Free Grammar
D.Unrestricted Grammar
Correct Answer: Context-Free Grammar
Explanation:
By Chomsky's hierarchy, Pushdown Automata recognize Context-Free Languages, which are exactly the languages generated by Context-Free Grammars.
Incorrect! Try again.
11How do Deterministic Pushdown Automata (DPDA) and Non-Deterministic Pushdown Automata (NPDA) compare in terms of computational power?
A.Their powers are incomparable.
B.NPDA is strictly more powerful than DPDA.
C.DPDA is strictly more powerful than NPDA.
D.They are equivalent in power.
Correct Answer: NPDA is strictly more powerful than DPDA.
Explanation:
Unlike finite automata, the non-deterministic version of PDA (NPDA) is strictly more powerful than the deterministic version (DPDA). NPDA accepts all CFLs, whereas DPDA only accepts Deterministic CFLs.
Incorrect! Try again.
12A language is classified as a Deterministic Context-Free Language (DCFL) if and only if:
A.It requires infinite stack memory.
B.It can be generated by an ambiguous grammar.
C.It is accepted by some DPDA by final state.
D.It is accepted by some NPDA by empty stack.
Correct Answer: It is accepted by some DPDA by final state.
Explanation:
Deterministic Context-Free Languages are precisely those accepted by a Deterministic Pushdown Automaton (DPDA) using final state acceptance.
Incorrect! Try again.
13Which of the following is a strict condition for a PDA to be considered Deterministic (DPDA)?
A.It must not contain any -transitions.
B.The stack alphabet must be equal to the input alphabet.
C.It must accept by empty stack.
D.If is not empty, then must be empty for all .
Correct Answer: If is not empty, then must be empty for all .
Explanation:
For a PDA to be deterministic, there must be at most one valid move in any situation. If an -transition is possible for a state and stack symbol, no input-consuming transition can exist for that same state and stack symbol.
Incorrect! Try again.
14Which of the following Context-Free Languages is NOT a Deterministic Context-Free Language (DCFL)?
A.
B.
C.
D.
Correct Answer:
Explanation:
The language of even-length palindromes requires guessing the midpoint of the string, which necessitates non-determinism. Hence, it is a CFL but not a DCFL.
Incorrect! Try again.
15When converting a Context-Free Grammar (CFG) to a PDA that accepts by empty stack, the stack alphabet typically consists of:
A.Only the variables (non-terminals) of the CFG
B.The union of variables and terminals of the CFG
C.The states of the PDA
D.Only the terminals of the CFG
Correct Answer: The union of variables and terminals of the CFG
Explanation:
In the standard top-down construction of a PDA from a CFG, the stack symbols include both the variables (to be expanded) and terminals (to be matched against the input).
Incorrect! Try again.
16In the standard top-down construction of a PDA from a CFG, if is a production in the grammar, what is the corresponding PDA transition?
A. contains
B.
C.
D.
Correct Answer: contains
Explanation:
In the top-down parsing simulation by a PDA, non-terminals are expanded on the stack without consuming input. Thus, reading with on top of the stack replaces with .
Incorrect! Try again.
17To simulate a top-down parse, the PDA attempts to construct which type of derivation for the input string?
A.Rightmost derivation
B.Bottom-up derivation
C.Leftmost derivation
D.Mixed derivation
Correct Answer: Leftmost derivation
Explanation:
Top-down parsing (and the corresponding CFG to empty-stack PDA construction) naturally simulates a leftmost derivation by always expanding the leftmost non-terminal (which is at the top of the stack).
Incorrect! Try again.
18Context-Free Languages (CFLs) are unconditionally closed under which of the following operations?
A.Union, Intersection, and Complement
B.Symmetric Difference and Intersection
C.Intersection, Complementation, and Set Difference
D.Union, Concatenation, and Kleene Star
Correct Answer: Union, Concatenation, and Kleene Star
Explanation:
CFLs are closed under union, concatenation, and Kleene star. They are not closed under intersection or complementation.
Incorrect! Try again.
19Which of the following statements about the intersection of languages is true?
A.The intersection of two Regular Languages is sometimes a CFL, but not regular.
B.The intersection of a CFL and a Regular Language is always a CFL.
C.The intersection of a CFL and a Regular Language is always Regular.
D.The intersection of two CFLs is always a CFL.
Correct Answer: The intersection of a CFL and a Regular Language is always a CFL.
Explanation:
CFLs are not closed under intersection with other CFLs, but they are closed under intersection with Regular Languages.
Incorrect! Try again.
20Are Deterministic Context-Free Languages (DCFLs) closed under complementation?
A.Yes, but the complement becomes a non-deterministic CFL.
B.Yes, the complement of a DCFL is always a DCFL.
C.No, DCFLs are never closed under complementation.
D.No, the complement is only regular.
Correct Answer: Yes, the complement of a DCFL is always a DCFL.
Explanation:
Unlike general CFLs, DCFLs are closed under complementation. By swapping final and non-final states in a carefully constructed DPDA, we can accept the complement.
Incorrect! Try again.
21Which of the following is a classic example of a language that is NOT Context-Free?
A.
B.
C.
D.
Correct Answer:
Explanation:
cannot be generated by a CFG or recognized by a PDA because a single stack cannot simultaneously verify the matching count of three distinct sets of symbols.
Incorrect! Try again.
22If is a Context-Free Language and is a Regular Language, what can be said about the set difference ?
A.It is never Context-Free.
B.It is Context-Sensitive but not Context-Free.
C.It is always Context-Free.
D.It is always Regular.
Correct Answer: It is always Context-Free.
Explanation:
The set difference is equivalent to . Since Regular languages are closed under complement, is regular. The intersection of a CFL and a Regular language is a CFL.
Incorrect! Try again.
23In parsing terminology, what does the first 'L' in LL(k) signify?
A.Lexical analysis
B.Lookahead
C.Leftmost derivation
D.Left-to-right scan of the input
Correct Answer: Left-to-right scan of the input
Explanation:
In LL(k), the first 'L' stands for scanning the input from Left to right, while the second 'L' stands for constructing a Leftmost derivation.
Incorrect! Try again.
24What does the second 'L' in LL(k) parsing signify?
A.Leftmost derivation
B.Left factoring
C.Left-to-right scanning
D.Left recursion removal
Correct Answer: Leftmost derivation
Explanation:
The second 'L' in LL(k) stands for producing a Leftmost derivation for the input string.
Incorrect! Try again.
25A grammar contains the production . This grammar is strictly unsuitable for Top-Down LL(k) parsers because it exhibits:
A.Left recursion
B.Right recursion
C.Ambiguity
D.Left factoring
Correct Answer: Left recursion
Explanation:
Top-down parsers (like LL parsers) can enter an infinite loop if the grammar contains left recursion ().
Incorrect! Try again.
26What grammar transformation is necessary when productions have common prefixes, such as , to make the grammar LL(1)?
A.Right factoring
B.Conversion to Chomsky Normal Form
C.Left factoring
D.Elimination of left recursion
Correct Answer: Left factoring
Explanation:
Left factoring is the process of factoring out common prefixes from the right-hand sides of productions so a top-down parser can decide which rule to apply after processing the common prefix.
Incorrect! Try again.
27For a non-terminal , the FIRST set is defined as:
A.The set of non-terminals that can derive .
B.The set of terminals that can appear immediately to the right of in some sentential form.
C.The set of all terminals that can appear at the end of a string derived from .
D.The set of terminals that begin strings derived from .
Correct Answer: The set of terminals that begin strings derived from .
Explanation:
FIRST(X) is the set of terminal symbols that begin any string derived from X. If X can derive the empty string, then is also in FIRST(X).
Incorrect! Try again.
28For a non-terminal , the FOLLOW set is defined as:
A.The set of terminal symbols that can precede .
B.The set of terminals that begin strings derived from .
C.The set of terminals that can appear immediately to the right of in some sentential form.
D.The set of variables that follow in a production rule.
Correct Answer: The set of terminals that can appear immediately to the right of in some sentential form.
Explanation:
FOLLOW(X) consists of the terminals that can immediately follow the non-terminal X in any valid sentential form derived from the start symbol.
Incorrect! Try again.
29A grammar is confirmed to be LL(1) if and only if, for any pair of productions :
A.FIRST() and FIRST() are identical sets.
B.FOLLOW() FOLLOW() = .
C.The grammar is ambiguous.
D.FIRST() FIRST() = , and if FIRST(), then FIRST() FOLLOW() = .
Correct Answer: FIRST() FIRST() = , and if FIRST(), then FIRST() FOLLOW() = .
Explanation:
For an LL(1) parser to be deterministic, alternative productions must have disjoint FIRST sets. If one can derive , its alternate's FIRST set must also be disjoint from the non-terminal's FOLLOW set.
Incorrect! Try again.
30What indicates a failure in making a grammar LL(1) when constructing the LL(1) parse table?
A.A single cell in the parsing table contains multiple production rules.
B.The FIRST and FOLLOW sets have common elements for different non-terminals.
C.The table has blank entries.
D.Every cell contains exactly one rule.
Correct Answer: A single cell in the parsing table contains multiple production rules.
Explanation:
Multiple entries in a single cell of an LL(1) parsing table represent a parsing conflict, meaning the parser cannot deterministically choose which production to apply with 1 symbol of lookahead. Hence, the grammar is not LL(1).
Incorrect! Try again.
31A Recursive Descent Parser is a practical implementation of which parsing methodology?
A.Shift-Reduce Parsing
B.Top-down Parsing
C.Operator Precedence Parsing
D.Bottom-up Parsing
Correct Answer: Top-down Parsing
Explanation:
A recursive descent parser is a top-down parser built from a set of mutually recursive procedures, where each procedure usually implements one of the non-terminals of the grammar.
Incorrect! Try again.
32What does the 'R' in LR(k) parsing signify?
A.Rightmost derivation
B.Right-to-left scanning
C.Recursive descent
D.Rightmost derivation in reverse
Correct Answer: Rightmost derivation in reverse
Explanation:
In LR(k), the 'L' stands for Left-to-right scanning, and the 'R' stands for constructing a Rightmost derivation in reverse (which is characteristic of bottom-up parsing).
Incorrect! Try again.
33A bottom-up parser constructs the parse tree by starting from the:
A.Leaves and growing up to the root
B.Start symbol of the grammar
C.Leftmost child and moving right
D.Root and growing down to the leaves
Correct Answer: Leaves and growing up to the root
Explanation:
Bottom-up parsing starts with the input string (leaves of the parse tree) and applies reductions to ultimately reach the start symbol (the root).
Incorrect! Try again.
34In bottom-up parsing, what is a 'handle'?
A.The left side of a production rule.
B.The start symbol of the grammar.
C.The current input symbol being scanned.
D.A substring that matches the right side of a production and whose reduction represents a step in the reverse rightmost derivation.
Correct Answer: A substring that matches the right side of a production and whose reduction represents a step in the reverse rightmost derivation.
Explanation:
A handle is a substring of the current sentential form that matches the RHS of a production, and reducing it represents the correct immediate step towards the start symbol.
Incorrect! Try again.
35Which parsing action involves pushing the current input symbol onto the stack in an LR parser?
A.Reduce
B.Accept
C.Error
D.Shift
Correct Answer: Shift
Explanation:
The 'Shift' action reads the next input token and pushes it (along with a new state) onto the parser's stack.
Incorrect! Try again.
36What constitutes a 'Shift/Reduce' conflict in bottom-up parsing?
A.The parser cannot decide which of two distinct productions to reduce by.
B.The parser is instructed to shift multiple tokens simultaneously.
C.The parser reaches the end of the input but the stack is not empty.
D.The parser is in a state where it can either shift the next input symbol or reduce by a production, and the lookahead doesn't resolve the choice.
Correct Answer: The parser is in a state where it can either shift the next input symbol or reduce by a production, and the lookahead doesn't resolve the choice.
Explanation:
A Shift/Reduce conflict occurs when a state has both a valid shift action and a valid reduce action for the same lookahead symbol.
Incorrect! Try again.
37An LR(0) item of the form indicates that the parser:
A.Is expecting to see a string derivable from .
B.Has recognized and is ready to reduce it to .
C.Must shift the next symbol immediately.
D.Has recognized and is shifting .
Correct Answer: Has recognized and is ready to reduce it to .
Explanation:
The dot at the end of the item signifies that the entire right-hand side has been seen on the stack, implying a possible reduction action.
Incorrect! Try again.
38How does an SLR(1) parser resolve reduce actions compared to a basic LR(0) parser?
A.It merges states that have identical core items.
B.It reduces only if the next input symbol is in the FIRST set of the left-hand side non-terminal.
C.It looks ahead exactly 2 symbols.
D.It reduces only if the next input symbol is in the FOLLOW set of the left-hand side non-terminal.
Correct Answer: It reduces only if the next input symbol is in the FOLLOW set of the left-hand side non-terminal.
Explanation:
SLR(1) parsing improves upon LR(0) by using FOLLOW sets. It only places a reduce action in the table under input symbol 'a' if 'a' is in FOLLOW(A).
Incorrect! Try again.
39Which of the following describes the relationship between the number of states in LALR(1) and CLR(1) parsing tables for a given grammar?
A.LALR(1) tables always have more states than CLR(1) tables.
B.CLR(1) and LALR(1) tables always have the exact same number of states.
C.LALR(1) tables have the same number of states as LR(0) tables, which is generally fewer than CLR(1).
Correct Answer: LALR(1) tables have the same number of states as LR(0) tables, which is generally fewer than CLR(1).
Explanation:
An LALR(1) parser merges CLR(1) states that have the same core items (differing only in lookaheads), resulting in a state count equivalent to the LR(0)/SLR automaton.
Incorrect! Try again.
40Which parser generator tool prominently uses the LALR(1) parsing technique?
A.Flex
B.ANTLR
C.YACC / Bison
D.Lex
Correct Answer: YACC / Bison
Explanation:
YACC (Yet Another Compiler Compiler) and its GNU equivalent Bison are classic parser generators that produce LALR(1) bottom-up parsers.
Incorrect! Try again.
41Rank the following LR parsers in increasing order of their parsing power (from weakest to strongest).
A.LR(0) < SLR(1) < LALR(1) < CLR(1)
B.LR(0) < LALR(1) < SLR(1) < CLR(1)
C.SLR(1) < LR(0) < CLR(1) < LALR(1)
D.CLR(1) < LALR(1) < SLR(1) < LR(0)
Correct Answer: LR(0) < SLR(1) < LALR(1) < CLR(1)
Explanation:
LR(0) is the weakest, followed by SLR(1) (which uses FOLLOW sets), LALR(1) (which uses lookaheads from merging), and CLR(1) (the canonical LR(1) which has full lookahead items and the most states).
Incorrect! Try again.
42A grammar that is ambiguous can never be:
A.Context-Free
B.Recognized by an NPDA
C.Unrestricted
D.LL(1) or LR(1)
Correct Answer: LL(1) or LR(1)
Explanation:
Ambiguity means there are multiple valid parse trees for a string. Deterministic parsers like LL(1) and LR(1) require exactly one parse tree per string, so an ambiguous grammar inherently causes table conflicts.
Incorrect! Try again.
43The string of grammar symbols on the stack of a bottom-up parser is known as a:
A.Viable prefix
B.Handle
C.Lookahead token
D.Sentential suffix
Correct Answer: Viable prefix
Explanation:
The stack contents in an LR parser always form a 'viable prefix' of a right sentential form, meaning they can be extended to a complete sentential form by adding terminal symbols.
Incorrect! Try again.
44If an LALR(1) parser encounters a reduce/reduce conflict during table construction, it implies that:
A.The grammar is certainly not LALR(1).
B.The parser should shift instead of reducing.
C.The grammar contains left recursion.
D.The grammar is unambiguously LR(0).
Correct Answer: The grammar is certainly not LALR(1).
Explanation:
A reduce/reduce conflict means that for a given state and lookahead, there are two different productions that could be reduced. Thus, the grammar is not LALR(1).
Incorrect! Try again.
45Is every LL(1) grammar also an LR(1) grammar?
A.Yes, the class of LL(1) grammars is a strict subset of LR(1) grammars.
B.No, there are LL(1) grammars that cannot be parsed by LR(1) parsers.
C.Yes, LL(1) and LR(1) are identical sets of grammars.
D.No, LR(1) and LL(1) are disjoint sets of grammars.
Correct Answer: Yes, the class of LL(1) grammars is a strict subset of LR(1) grammars.
Explanation:
Bottom-up LR(1) parsers are strictly more powerful than top-down LL(1) parsers. Every grammar that can be parsed deterministically top-down with 1 lookahead can also be parsed deterministically bottom-up.
Incorrect! Try again.
46When converting a Context-Free Grammar to a Pushdown Automaton, the language accepted by the resulting PDA is:
A.A regular subset of the language generated by the CFG.
B.The complement of the language generated by the CFG.
C.A context-sensitive superset of the CFG's language.
D.Equivalent to the language generated by the CFG.
Correct Answer: Equivalent to the language generated by the CFG.
Explanation:
The fundamental theorem of equivalence between CFGs and PDAs guarantees that the language generated by the grammar is exactly the language accepted by the constructed PDA.
Incorrect! Try again.
47Which parsing technique relies heavily on the computation of FIRST and FOLLOW sets?
A.LL(1) Parsing
B.LR(0) Parsing
C.Operator Precedence Parsing
D.CYK Algorithm
Correct Answer: LL(1) Parsing
Explanation:
LL(1) parsing table construction requires FIRST and FOLLOW sets to correctly place productions into the table and resolve predictive choices.
Incorrect! Try again.
48What happens when an LR parser reaches a configuration where the state is and the lookahead symbol is the end-of-input marker ?
A.A shift error is flagged.
B.The input is successfully accepted.
C.The stack is popped until it is empty.
D.The parser requests more input.
Correct Answer: The input is successfully accepted.
Explanation:
In an LR parser, when the stack contains the start symbol and the input is exhausted (represented by ), the action table points to 'Accept', indicating a successful parse.
Incorrect! Try again.
49Which of the following represents an inherent limitation of Deterministic Pushdown Automata (DPDA)?
A.They cannot recognize any Regular Languages.
B.They require infinite lookahead to resolve stack operations.
C.They cannot recognize non-deterministic Context-Free Languages like palindromes of even length.
D.They are equivalent to finite automata.
Correct Answer: They cannot recognize non-deterministic Context-Free Languages like palindromes of even length.
Explanation:
DPDAs can only accept deterministic context-free languages. They cannot guess the midpoint of strings (e.g., in ), which is a limitation compared to NPDAs.
Incorrect! Try again.
50A shift-reduce parser operates primarily using which two data structures?
A.A Queue for input tokens and a Hash Table for grammar rules
B.A Stack for states/symbols and an Input Buffer for the unread string
C.A Linked List for output and a Tree for lookaheads
D.Two Stacks (one for states, one for input)
Correct Answer: A Stack for states/symbols and an Input Buffer for the unread string
Explanation:
Shift-reduce parsers maintain a stack to hold states and grammar symbols (the viable prefix) and read from an input buffer to see the remaining tokens.