What is an 'instantaneous description' (ID) of a Pushdown Automaton?
An ID of a PDA captures the exact configuration at any step as (q, w, $\gamma ) containing current state, unconsumed input$, and stack string.
Are Context-Free Languages closed under Union and Concatenation?
CFLs ARE closed under Union, Concatenation, Kleene Star, Substitution, Homomorphism, and Reversal.
What is the maximum height of a parse tree for a string of length 'n' generated by a grammar in CNF?
In CNF, deriving a string of length n builds a binary tree whose maximum height is n (linear chain of n-1 non-terminals plus 1 terminal leaf).
If a PDA has 1 state, 2 stack symbols, and accepts by empty stack, it accepts the class of:
Single-state PDAs accepting by empty stack can accept any Context-Free Language (via LL/LR stack parsing techniques).
Which symbol can be pushed onto the stack of a PDA during an $\epsilon -transition$?
In an \epsilon -transition \delta (q, \epsilon , Z) = (q', \gamma ), string \gamma can push any sequence of stack symbols without consuming input.