6 votes 6 votes S1: Can a Turing machine ever write a blank symbol on its tape. S2: Any Turing machine must have at least two states which of above statements are true??? akash.dinkar12 asked Nov 6, 2017 • edited Nov 10, 2019 by akash.dinkar12 akash.dinkar12 1.8k views answer comment Share Follow See all 3 Comments See all 3 3 Comments reply Anu007 commented Nov 6, 2017 reply Follow Share both are true. S1: Can a Turing machine ever write a blank symbol on its tape. yes this is also possible S2: Any Turing machine must have at least two states : i.e. accepts state or reject state. 1 votes 1 votes Rishabh Gupta 2 commented Nov 7, 2017 reply Follow Share reference: http://cseweb.ucsd.edu/~mihir/cse105/ss3.pdf 1 votes 1 votes Vishwesh Vinchurkar commented Dec 10, 2018 reply Follow Share @Anu007 Please could you tell if I am understanding it in a right way ? I am thinking as Turing machine should have minimum two states, because if there is only one state, then if transition is not defined for some symbol in that state, then the strings containing that symbol will halt on that one state only and hence, it will be again be halted in final state, making it accepted. Also, does it apply the same way for PDA also, where we have dead configuration ? 0 votes 0 votes Please log in or register to add a comment.
2 votes 2 votes Both are true. S1: Yes it is also possible S2: Any Turing machine must have at least two states i.e. accept state or reject state. Ref: https://cseweb.ucsd.edu/~mihir/cse105/ss3.pdf gmrishikumar answered Jan 4, 2019 • edited Jan 12, 2019 by gmrishikumar gmrishikumar comment Share Follow See all 2 Comments See all 2 2 Comments reply priyesh9875 commented Nov 8, 2019 reply Follow Share How many states for L = a* over {a}? Is it not possible that initial state is final state and TM accepts everything. 1 votes 1 votes nadeshseen commented Nov 9, 2019 reply Follow Share @priyesh9875 https://cs.stackexchange.com/questions/86538/why-does-a-turing-machine-need-at-least-two-states 0 votes 0 votes Please log in or register to add a comment.