DocumentCode :
707618
Title :
Computational complexity in language string processing and theory of halting problem in deterministic turing machine accepting context sensitive language, context free language or regular language
Author :
Sharma, Chetan ; Shakya, Rinku
Author_Institution :
Dept. of Comput. Sci. & Eng., Chitkara Univ., Rajpura, India
fYear :
2015
fDate :
11-13 March 2015
Firstpage :
2091
Lastpage :
2096
Abstract :
Turing machines are equivalent to modern electronic computers at a certain theoretical level, but differ in many details. In the analogy with a computer, the “tape” of the Turing machine is the computer memory, idealized to extend infinitely in each direction. The remarkable fact is that certain Turing machines are “universal”, in the sense that with appropriate input, they can be made to perform any ordinary computation. Not every Turing machine has this property; many can only behave in very simple ways. In effect, they can only do specific computations; they cannot act as “general-purpose computers”. Turing machine can process different types of strung written in various type language defined by Chomsky hierarchy. Machine will stop when it didn´t have proper input or a machine state which is stable but not final and show halting state of machine. In this paper we are trying to describe using a example that a Turing machine can accept a language or string defined by context sensitive, context free or regular language till it find suitable input, but it show the halting state of the machine when it does not reach to a state closure to the final state along with the complexity of the process to process of that language or string.
Keywords :
Turing machines; computational complexity; context-free languages; context-sensitive languages; Chomsky hierarchy; computational complexity; computer memory; context free language; context sensitive language; deterministic turing machine; electronic computers; general-purpose computers; halting theory problem; language string processing; regular language; Computers; Context; Grammar; Magnetic heads; Time complexity; Turing machines; Chomsky hierarchy; context free; context sensitive; halting state; universal;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Computing for Sustainable Global Development (INDIACom), 2015 2nd International Conference on
Conference_Location :
New Delhi
Print_ISBN :
978-9-3805-4415-1
Type :
conf
Filename :
7100608
Link To Document :
بازگشت