P15.1.4 [10] It would be interesting to have an example of a language decided by an n-state 2WDFA but requiring (n+1)"+1

[answerhappygod]

P15 1 4 10 It Would Be Interesting To Have An Example Of A Language Decided By An N State 2wdfa But Requiring N 1 1 1 (57.31 KiB) Viewed 250 times

P15.1.4 [10] It would be interesting to have an example of a language decided by an n-state 2WDFA but requiring (n+1)"+1 states to decide with an ordinary DIA. The following language (due to Meyer and Fischer in 1971) comes fairly close. Let F. be the set of strings in {a,b,c}* of the form a" babab...a da, where the numbers k, 11, 12,..., in are cach in the range from 1 through n, and in - 1. That is, the string gives a sequence to n numbers in unary, an index k, and a number j, and we are to accept if and only if j was the k'th number given. (a) Using the Myhill-Nerode theorem, prove that no ordinary DFA of fewer than n" states can decide (1) Describe a 2WDFA that decides Fn using a number of states proportional to n. Assume the format of Exercise 15.1.6, so that the 2WDFA can recognize the last letter of the input string without ending the computation. (c) This example shows that any general simulation of m-state 2WDFA's by ordinary DFA's must use at least gm) steps on some example. What is the function g(n) that comes from your solution to part (b)?