2

Yes, of course. $2^{f(n)}$ is asymptotically larger than $f(n)$, so you can come up with an unending sequence of larger and larger running times. The answer to your other questions are also yes, by the time hierarchy theorem.


1

A simple way to do it is to just write an interpreter that follows the transition table. I.e., do something like (in C): state = INITIAL; symbol = get_next(); while(symbol != END) { state = table[state][symbol]; symbol = get_next(); } if(is_accepting(state)) /* Accept */ Next simpler is to write a rat's nest of gotos, transferring among them ...


Only top voted, non community-wiki answers of a minimum length are eligible