Talk:Read-only Turing machine

Page started

Created article, as per request. Modelled on queue machine and pushdown automaton. Will finish tonight. SamuelRiv 14:51, 6 November 2007 (UTC)[reply]

pushdown 2NFA and CFGs

It seems you don't need nondeterminism - a 2DFA with a stack should be able to parse context-free grammars, unless I'm missing something. Is that directly from your source? SamuelRiv (talk) 05:00, 26 November 2007 (UTC)[reply]

Mmm. The obvious approach I thought up doesn't work, since a 2DFA can't tell where it needs to backtrack to in general (for parsing, say, palindromes). Wagner and Wechsung doesn't actually say anything about the matter, except that "1:k-NPDA" (one-way nondeterministic pushdown automata with k heads) is a subset of "2:3k-DPDA" (two-way deterministic automata with 3k heads and a stack). For the k=1 case, they cite "Separating tape bounded auxiliary pushdown automata classes" 9th STOC (1977) by I H Sudborough. I'm just assuming they would have mentioned a better result if there were one (unless of course it was only developed after the book was published in 1986). Ben Standeven (talk) 05:15, 26 November 2007 (UTC)[reply]

A 2DFA with stack should be able to parse a palindrome - if we know the start and end points of our palindrome, we can easily calculate the length by pushing a counting marker for every other symbol from front to back, then popping every symbol from front to back (which leaves us at the halfway point), then pushing backwards from the halfway point to the front, and then popping if equal from the back. Another method is to push the first symbol and pop it when it repeats. If there's still string left after the repetition, run back to the beginning and push a "skip" marker" for every repeat of that symbol in the backwards run. Recurse.

This will work if we have regular or DCFGs before and after the palindrome, as we can parse both forwards and backwards and quickly get rid of any confusion those might cause. If there are two or more palindromes, it might be a problem... I'll have to think about it, but either way, I think the nondeterministic case is too general, and it's misleading to begin with because it's not equivalent to CFG machines - it's more powerful. SamuelRiv (talk) 06:27, 26 November 2007 (UTC)[reply]