The Design of 3-State Turing Machine for Accepting L=｛0~n1~n|n≥0｝
Qin Ding · Journal of Huaiyin Teachers College · 2006
This paper shows a design of only 3-state Turing machine for accepting L=｛0~n1~n|n≥0｝.Its method is to control the moving direction of the TM's tape head by using the tape symbols cooperatively so as to reduce the number of states of the TM.The design is implemented in C programming.