Could you help me answer this question?

occurs for some string u? P15.1.4 It wo uld be interesting10 to have an example of a language decide d by an n-state 2WDFA but requiring (n+1)n+1 states to decide with an ordinary DFA. The following language (due to Meyer and Fischer in 1971) comes fairly close. Let Fr be the set of strings in fa, b,cy of the form a't bat bai3b. . . a'nchai, where the numbers k, i1, i2,... in are each in the range from 1 through n, and i j. That is, the string gives a sequence of n numbers in unary, an inde 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 D FA of fewer than n" states can decide Fr- (b) Describe a 2WDFA that decides F, using a number of states proportional to n. (c) This example shows that any general simulatio n of m-state 2WDFA's by ordinary DFA's must use at least g(m) steps on some example. What is the function g) that comes from your solution to part (b)? occurs for some string u? P15.1.4 It wo uld be interesting10 to have an example of a language decide d by an n-state 2WDFA but requiring (n+1)n+1 states to decide with an ordinary DFA. The following language (due to Meyer and Fischer in 1971) comes fairly close. Let Fr be the set of strings in fa, b,cy of the form a't bat bai3b. . . a'nchai, where the numbers k, i1, i2,... in are each in the range from 1 through n, and i j. That is, the string gives a sequence of n numbers in unary, an inde 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 D FA of fewer than n" states can decide Fr- (b) Describe a 2WDFA that decides F, using a number of states proportional to n. (c) This example shows that any general simulatio n of m-state 2WDFA's by ordinary DFA's must use at least g(m) steps on some example. What is the function g) that comes from your solution to part (b)