Which of the following represents the language accepted by the Turing machine with the transition function (δ):
δ(q0, a) = (q1, x, R)
δ(q1, a) = (q1, a, R)
δ(q1, y) = (q1, y, R)
δ(q1, b) = (q2, y, L)
δ(q2, y) = (q2, y, L)
δ(q2, a) = (q2, a, L)
δ(q2, x) = (q0, x, R)
δ(q0, y) = (q3, y, R)
δ(q3, y) = (q3, y, R)
δ(q3, □) = (qf, □, R)
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: B. L = {aⁿbⁿ | n ≥ 1}
Explanation
The machine repeatedly marks the leftmost a as x and the matching b as y. When no a is left it checks that only y's remain and accepts on the blank. On empty input q0 sees □ and has no move, so ε is rejected: L = {aⁿbⁿ | n ≥ 1}. (Options B and C describe the same set; B is the keyed answer.)More Theory of Computation and Compilers questions
- Match List I with List IIList I List II A. Conflict Resolution I. Three-Address Code B. Common Subexpression II. Precedence C. Quadruples I…
- Match List I with List IIList I List II A. Type-0 Grammar I. Linear Grammar B. Type-1 Grammar II. GNF C. Type-2 Grammar III. x → y, |x| ≤ |…
- Which of the following CFG(s) is/are in Chomsky Normal Form? (All capital letters are variables & lower case letters are terminals) A. S →…
- yacc is which of the following parsers?
- For the above-mentioned passage, which of the following automata is correct? Each option is described by its transitions (start state 1).
- For the above specified passage, which of the following represents the grammar for the language accepted by the machine?