In a PDA accepting by Empty Stack, when is an input string 'w' accepted?
Empty stack acceptance requires consuming all input characters w resulting in an empty stack string (q, $\epsilon , \epsilon$).
Can a Deterministic Pushdown Automaton (DPDA) accepting by EMPTY STACK recognize a language L that possesses the 'Prefix Property'?
If x ∈ L and xy ∈ L, an empty-stack DPDA would empty its stack upon reading x, failing to process suffix y; thus N(DPDA) languages must have the prefix property.
How can any DPDA L(M) accepting by Final State be modified to accept by Empty Stack?
Appending end-marker '$' enforces the prefix property, allowing final-state DPDAs to transition to an empty-stack clearing state upon reading '$'.
What language is generated by the CFG rules: S → aB | bA, A → a | aS | bAA, B → b | bS | aBB?
State A tracks an excess of one 'a', state B tracks an excess of one 'b', and S generates balanced strings with equal 'a' and 'b' counts.
What is the maximum number of non-terminals on the right-hand side of any production rule in Chomsky Normal Form (CNF)?
CNF explicitly restricts non-terminal RHS branching to exactly two non-terminals (A → BC).