# {0,1}* ∈ P class?

I have the following question about complexity time classes. Given the language $$L = \{0,1\}^*$$, is it inside the class P or not?

$$L = \{0,1\}^∗ ∈ P?$$

• What's your guess? Do you see an algorithm to test whether $w \in L$? – holf Oct 15 '19 at 12:04
• Your language is regular and so can be decided in linear time. – Yuval Filmus Oct 15 '19 at 12:35

A useful exercise to answer the question could be to build a simple Turing machine $$M$$ (let's say one tape and one head) that recognizes your language. Such a TM could work directly on the input tape and be equipped with an extremely simple transition function:

2. If $$($$input $$= 0$$ $$\lor$$ input $$= 1)$$ $$\implies$$ Move R (right on the tape)
$$I = [\varnothing, 0, 1,1,0,0,1,0,0,1,0,0,1,1,.........,\varnothing]$$ and that your TM start from the left blank symbol and HALT $$\iff$$ it reaches the final blank symbol, you can notice that this machine HALT $$\iff$$ it recognizes $$L$$.
1. What is the time complexity of running $$M$$ on $$w$$ $$\in$$ $$L$$ if |$$w$$| $$=n$$ ?
2. Is $$w$$ $$\in$$ $$L$$ regular and why?