Back to the 2025 paper
Similar questions
FORMAL LANGUAGE & AUTOMATA THEORYFrom the options, the pair having different expressive powers is: (i) DPDA and NPDA (ii) DFA and NFA (iii) single-tape TM and multi-tape TM (iv) deterministic single-tape TM and nondeterministic single-tape TM20232mFormal Language & Automata TheoryWhich of the following pairs have DIFFERENT expressive powers? (i) Deterministic finite automata (DFA) and non-deterministic finite automata (NDFA) (ii) Deterministic push-down automata (DPDA) and non-deterministic push-down automata (NDPDA) (iii) Deterministic single-tape Turing machine and non-deterministic single-tape Turing machine (iv) Single-tape Turing machine and multi-tape Turing machine20222mFormal Language & Automata TheoryExplain the multi-tape version of turing machine and its significance.20207mFORMAL LANGUAGE & AUTOMATA THEORYWrite short notes on: Multi-tape Turing Machine.20237m
PreviousWhich of the following CFLs is deterministic? (i) {a^n b^n} (ii) Arithmetic expressions (iii) Palindromes (iv) {ww^R}NextGiven the grammar G = (\{S\}, \{a, b\}, P, S) P: S \rightarrow aSb | ab Derive the string aabb using leftmost derivation, rightmost derivation and also draw the parse tree.