| 图灵机扫描子串技术(英文) |
| |
| 引用本文： | 陈文宇,程小鸥,孙世新. 图灵机扫描子串技术(英文)[J]. 电子科技大学学报(社会科学版), 2009, 0(2) |
| |
| 作者姓名： | 陈文宇 程小鸥 孙世新 |
| |
| 作者单位： | 电子科技大学计算机科学与工程学院; |
| |
| 基金项目： | Supported by the Sichuan science and technology(2006J13-068)~~ |
| |
| 摘 要： | 某些语言中的所有句子必须包含有或者不能包含有特定的子串,或者需要将语言中句子所包含的子串进行替换。传统的方法是利用图灵机的存储技术处理该类语言。该文提出了一种图灵机扫描子串技术的新方法,即将特定子串当作一个整体,将扫描一个符号的图灵机的多个状态转换函数合并为一个,使得图灵机一次可以扫描多个符号,但图灵机的读/写头仅移动一个单元。该方法简便且有效,通过实例证明了扫描多个符号的图灵机与扫描一个符号的图灵机是等价的。
|
| 关 键 词： | 移动技术 扫描子串 存储技术 图灵机 |
Technology of Scanning Substring by Turing Machine |
| |
| CHEN Wen-yu,CHENG Xiao-ou,, SUN Shi-xin. Technology of Scanning Substring by Turing Machine[J]. Journal of University of Electronic Science and Technology of China(Social Sciences Edition), 2009, 0(2) |
| |
| Authors: | CHEN Wen-yu CHENG Xiao-ou SUN Shi-xin |
| |
| Affiliation: | School of Computer Science and Engineering;University of Electronic Science and Technology of China Chengdu 610054 |
| |
| Abstract: | In some languages, all the sentences must include or exclude some specific substrings. Sometimes, the substrings must be replaced. It is difficult for a Turing machine to accept such languages. Traditional method is based on the storage technique. In this paper, we present a new method, the scanning substring techonology. In the method, the specific substring is treated as a single unit. Multiple status transition functions of the Turing machine are combined to scan multiple characters at one time, but the ... |
| |
| Keywords: | moving scan substring storage Turing machines |
| 本文献已被 CNKI 等数据库收录！ |
|
