3
votes
$DTIME_1(o(n^2))\setminus$ REGULAR
The language $L=\{0^n1^n : n\geq 0\}$ is non-regular, but decidable in time $O(n\log n)$ on a one-tape Turing machine (one can either use a counter or iteratively remove every next 0 and 1
plus check ...
- 303
Only top scored, non community-wiki answers of a minimum length are eligible