Problem sheet Turing machines and context sensitive grammar



Download 12.09 Kb.
Date13.01.2023
Size12.09 Kb.
#60369
Problem sheet3TM

Problem sheet
Turing machines and context sensitive grammar


  1. 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)


  1. 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:




The database is protected by copyright ©ininet.org 2024
send message

    Main page