Skip to main content
Computer Science

Return to Answer

improved presentation
Source Link
babou
babou
  • 19.6k
  • 41
  • 76

I think your idea is workable (though there are other ways to do it), thoughbut there is still some work to be done to take care of detail"details".

But first, you have to know what is the value of $n$ for your input.in order to use your idea, you have to know what is the value of $n$ for your input. And you do not know, and have no simple way to know. So you use the great trick of automata theory: you guess. You guess by using non-determinism. You guess by using non-determinism. The first thing the automaton does is to enter a state where it write a sting of symbols $a$ on the tape. The state has non deterministic transitions so that it switches to a new state at some point, after writing some number $n$ of symbols $a$.

Now, the TM much check that the input actually contains $n^2$ symbols $O$.

You must keep carefully your string $a^n$ since it is your reference number for the computation. But you can use the TM to make as many copies as needed, using different symbols to avoid confusion. Basically, you will need one copy $b^n$ to implement a loop counter that erases $n$ symbols $0$ at each turn. To erase $n$ symbols ... you think hard.

And this is already help beyond a simple hint.

But asAs stated in some comments it may not be the simplest solution. Its main advantage is that it teaches you to use non-determinism to guess (and check) ... and that makes life so much easier in automata theory.

I think your idea is workable, though there is still some work to be done to take care of detail.

But first, you have to know what is the value of $n$ for your input. And you do not know, and have no simple way to know. So you use the great trick of automata theory: you guess. You guess by using non-determinism. The first thing the automaton does is to enter a state where it write a sting of symbols $a$ on the tape. The state has non deterministic transitions so that it switches to a new state at some point, after writing some number $n$ of symbols $a$.

Now, the TM much check that the input actually contains $n^2$ symbols $O$.

You must keep carefully your string $a^n$ since it is your reference number for the computation. But you can use the TM to make as many copies as needed, using different symbols to avoid confusion. Basically, you will need one copy $b^n$ to implement a loop counter that erases $n$ symbols $0$ at each turn. To erase $n$ symbols ... you think hard.

And this is already help beyond a simple hint.

But as stated in some comments it may not be the simplest solution. Its main advantage is that it teaches you to guess (and check) ... and that makes life so much easier in automata theory.

I think your idea is workable (though there are other ways to do it), but there is still some work to be done to take care of "details".

But first, in order to use your idea, you have to know what is the value of $n$ for your input. And you do not know, and have no simple way to know. So you use the great trick of automata theory: you guess. You guess by using non-determinism. The first thing the automaton does is to enter a state where it write a sting of symbols $a$ on the tape. The state has non deterministic transitions so that it switches to a new state at some point, after writing some number $n$ of symbols $a$.

Now, the TM much check that the input actually contains $n^2$ symbols $O$.

You must keep carefully your string $a^n$ since it is your reference number for the computation. But you can use the TM to make as many copies as needed, using different symbols to avoid confusion. Basically, you will need one copy $b^n$ to implement a loop counter that erases $n$ symbols $0$ at each turn. To erase $n$ symbols ... you think hard.

And this is already help beyond a simple hint.

As stated in some comments it may not be the simplest solution. Its main advantage is that it teaches you to use non-determinism to guess (and check) ... and that makes life so much easier in automata theory.

Source Link
babou
babou
  • 19.6k
  • 41
  • 76

I think your idea is workable, though there is still some work to be done to take care of detail.

But first, you have to know what is the value of $n$ for your input. And you do not know, and have no simple way to know. So you use the great trick of automata theory: you guess. You guess by using non-determinism. The first thing the automaton does is to enter a state where it write a sting of symbols $a$ on the tape. The state has non deterministic transitions so that it switches to a new state at some point, after writing some number $n$ of symbols $a$.

Now, the TM much check that the input actually contains $n^2$ symbols $O$.

You must keep carefully your string $a^n$ since it is your reference number for the computation. But you can use the TM to make as many copies as needed, using different symbols to avoid confusion. Basically, you will need one copy $b^n$ to implement a loop counter that erases $n$ symbols $0$ at each turn. To erase $n$ symbols ... you think hard.

And this is already help beyond a simple hint.

But as stated in some comments it may not be the simplest solution. Its main advantage is that it teaches you to guess (and check) ... and that makes life so much easier in automata theory.