Question

Let $f:N\to N$be any function where $f\left(n\right)=o\left(nlogn\right)$. Show that $TIME\left(f\left(n\right)\right)$ contains only the regular languages.

Short answer

Thus, it is only a regular language. It is accepted by the $TIME\left(f\left(n\right)\right)$.

Step-by-step solution

To Regular Language

A language is a collection of strings made up of characters or symbols from a specific alphabet.

A regular language is one that may be stated using regular expressions, finite automata, or state machines, both deterministic and non-deterministic.

To Explain and remove the form

Suppose language is $A=\left\{0^k{1}^k\right|k\ge 0\}\in TIME(n\log n)$

• If w is not of the form, reject M(w).
• Rep till all w's have been crossed out.
• Reject if$\left(parityf0\text{'}s\right)\ne \left(parityf1\text{'}s\right)$.
• Remove every other 0 and 1 from the equation.
• If all other bits are crossed out, accept.

A language is a collection of strings made up of characters or symbols from a specific alphabet.

Thus, it is only a regular language. It is accepted by the $TIME\left(f\left(n\right)\right)$.