1A Pushdown Automaton (PDA) is formally defined as a 7-tuple: . What does represent?
A.Transition function
B.Set of internal states
C.Input alphabet
D.Stack 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.Linked List
B.Stack
C.Hash Table
D.Queue
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 symbols already processed
C.The entire input string
D.The contents of the stack
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 halts its execution.
B.The PDA changes its state and/or stack contents without consuming any input symbol.
C.The PDA rejects the input string immediately.
D.The PDA consumes an input symbol but leaves the stack unchanged.
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.A final state, regardless of stack contents
B.Any state, and the stack is empty
C.A final state with an empty stack
D.The initial state with an empty stack
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.Acceptance by final state is strictly more powerful.
B.Both acceptance methods describe exactly the same class of languages.
C.They are equivalent only for Deterministic PDAs.
D.Acceptance by empty stack is strictly more powerful.
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.All strings in share the same prefix.
B.The language contains the empty string .
C.No string in is a proper prefix of another string in .
D.Every string in is a prefix of some string in the universal language.
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.Making the initial state the only final state.
B.Adding a new start state and a new bottom-of-stack marker.
C.Removing all -transitions.
D.Duplicating the stack alphabet.
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.Context-Free Grammar
C.Regular 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.They are equivalent in power.
C.DPDA is strictly more powerful than NPDA.
D.NPDA is strictly more powerful than DPDA.
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 is accepted by some NPDA by empty stack.
B.It requires infinite stack memory.
C.It is accepted by some DPDA by final state.
D.It can be generated by an ambiguous grammar.
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.If is not empty, then must be empty for all .
B.It must not contain any -transitions.
C.The stack alphabet must be equal to the input alphabet.
D.It must accept by empty stack.
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 terminals of the CFG
B.The union of variables and terminals of the CFG
C.Only the variables (non-terminals) of the CFG
D.The states of the PDA
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.Leftmost derivation
B.Mixed derivation
C.Bottom-up derivation
D.Rightmost 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, Concatenation, and Kleene Star
B.Union, Intersection, and Complement
C.Symmetric Difference and Intersection
D.Intersection, Complementation, and Set Difference
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 CFLs is always a CFL.
B.The intersection of a CFL and a Regular Language is always Regular.
C.The intersection of two Regular Languages is sometimes a CFL, but not regular.
D.The intersection of a CFL and a Regular Language 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, the complement of a DCFL is always a DCFL.
B.No, the complement is only regular.
C.No, DCFLs are never closed under complementation.
D.Yes, but the complement becomes a non-deterministic CFL.
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 always Regular.
B.It is always Context-Free.
C.It is never Context-Free.
D.It is Context-Sensitive but not Context-Free.
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.Leftmost derivation
B.Left-to-right scan of the input
C.Lexical analysis
D.Lookahead
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.Left factoring
B.Left-to-right scanning
C.Leftmost derivation
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.Ambiguity
B.Left recursion
C.Right recursion
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.Elimination of left recursion
B.Right factoring
C.Left factoring
D.Conversion to Chomsky Normal Form
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 all terminals that can appear at the end of a string derived from .
B.The set of non-terminals that can derive .
C.The set of terminals that can appear immediately to the right of in some sentential form.
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 variables that follow in a production rule.
B.The set of terminals that can appear immediately to the right of in some sentential form.
C.The set of terminals that begin strings derived from .
D.The set of terminal symbols that can precede .
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.FIRST() FIRST() = , and if FIRST(), then FIRST() FOLLOW() = .
D.The grammar is ambiguous.
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.Every cell contains exactly one rule.
B.The FIRST and FOLLOW sets have common elements for different non-terminals.
C.A single cell in the parsing table contains multiple production rules.
D.The table has blank entries.
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.Bottom-up Parsing
B.Operator Precedence Parsing
C.Shift-Reduce Parsing
D.Top-down 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.Recursive descent
B.Rightmost derivation
C.Rightmost derivation in reverse
D.Right-to-left scanning
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.Leftmost child and moving right
B.Start symbol of the grammar
C.Leaves and growing up to the root
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.A substring that matches the right side of a production and whose reduction represents a step in the reverse rightmost derivation.
B.The current input symbol being scanned.
C.The left side of a production rule.
D.The start symbol of the grammar.
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.Accept
B.Reduce
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 is instructed to shift multiple tokens simultaneously.
B.The parser reaches the end of the input but the stack is not empty.
C.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.
D.The parser cannot decide which of two distinct productions to reduce by.
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.Has recognized and is ready to reduce it to .
B.Is expecting to see a string derivable from .
C.Has recognized and is shifting .
D.Must shift the next symbol immediately.
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 reduces only if the next input symbol is in the FOLLOW set of the left-hand side non-terminal.
B.It reduces only if the next input symbol is in the FIRST set of the left-hand side non-terminal.
C.It merges states that have identical core items.
D.It looks ahead exactly 2 symbols.
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?
B.LALR(1) tables have the same number of states as LR(0) tables, which is generally fewer than CLR(1).
C.LALR(1) tables always have more states than CLR(1) tables.
D.CLR(1) and LALR(1) tables always have the exact same number of states.
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.YACC / Bison
B.Lex
C.Flex
D.ANTLR
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.CLR(1) < LALR(1) < SLR(1) < LR(0)
C.LR(0) < LALR(1) < SLR(1) < CLR(1)
D.SLR(1) < LR(0) < CLR(1) < LALR(1)
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.LL(1) or LR(1)
B.Recognized by an NPDA
C.Context-Free
D.Unrestricted
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.Sentential suffix
B.Lookahead token
C.Viable prefix
D.Handle
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.No, there are LL(1) grammars that cannot be parsed by LR(1) parsers.
B.Yes, LL(1) and LR(1) are identical sets of grammars.
C.Yes, the class of LL(1) grammars is a strict subset of LR(1) 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 context-sensitive superset of the CFG's language.
B.Equivalent to the language generated by the CFG.
C.A regular subset of the language generated by the CFG.
D.The complement of 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.Operator Precedence Parsing
B.LL(1) Parsing
C.CYK Algorithm
D.LR(0) Parsing
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 parser requests more input.
C.The stack is popped until it is empty.
D.The input is successfully accepted.
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 non-deterministic Context-Free Languages like palindromes of even length.
B.They require infinite lookahead to resolve stack operations.
C.They are equivalent to finite automata.
D.They cannot recognize any Regular Languages.
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 Stack for states/symbols and an Input Buffer for the unread string
B.A Queue for input tokens and a Hash Table for grammar rules
C.Two Stacks (one for states, one for input)
D.A Linked List for output and a Tree for lookaheads
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.