Problem sheet Turing machines and context sensitive grammar

Download 12.09 Kb. Date 13.01.2023 Size 12.09 Kb. #60369

Problem sheet Turing machines and context sensitive grammar What language is accepted by the TM M({q0, q1, q2, q3}, {a, b}, {a, b, #}, , q0, #, {q3}) (q0, 0) = (q1, a, R) (q0, b) = (q2, b, R) (q1, b) = (q1, b, R) (q1, #) = (q3, #, R) (q2, b) = (q2, b, R) (q2, a) = (q3, a, R) Design a Turing Machine with no more than three states that accepts L(a(a + b)*) defined over = {a,b}. Download 12.09 Kb. Share with your friends: