What is the space bound of a Linear Bounded Automaton for input length n?
LBAs restrict memory workspace strictly to a linear multiple of input length n.
Is the language L = { w w | w ∈ {a, b}* } Context-Free or Context-Sensitive?
Duplicating arbitrary string w requires tracking two separated matching patterns, violating CFL pumping lemma.
Is the language L = { $a^n$ $b^j$ $c^n$ $d^j$ | n, j $\ge 1 } Context-Free$ or Context-Sensitive?
Interleaved comparisons of 'a' with 'c' and 'b' with 'd' require context-sensitive LBA power.
Is the language L = { a^{$n^2}$ | n $\ge 1 } (square length strings) Context-Free$ or Context-Sensitive?
$Non-linear quadratic string growth a^{n^2} cannot be pumped linearly, making it context-sensitive.$
What machine model accepts Type-0 (Unrestricted / Phase Structure) Grammars?
Unrestricted Type-0 grammars correspond exactly to Turing Machines.