# I have trouble translating Turing machine language, can you help me break down language notation to English?

My problem is I don't have many issues with creating a Turing machine state table when given a string such as 01101, my issue arises when I am presented with a problem which requires the Turing machine to recognize the language {0n1n | n ≥ 0}.

I have found this guide on a similar problem however I cannot grasp what is going on and what is required from the language statement. Any help in regards to how to read the specified language effectively would be appreciated.

• The link contains a very detailed guide. I suggest implementing the machine on a simulator and running it to see how it works. – Yuval Filmus May 13 at 21:06
• This is also, notably, probably the most famous example of a non-regular language. Try implementing a simpler regular language first, such as $\{0^i 1^j \mid i, j \in \mathbb{N}\}$. – Draconis May 15 at 3:47

When $$s$$ is a symbol and $$n$$ is a natural number, "$$s^n$$" means "$$s$$ repeated $$n$$ times". So you're being asked to recognize the language of all strings that consist of $$n$$ zeros followed by $$n$$ ones, for any possible value of $$n\geq 0$$. That is, $$\{\epsilon, 01, 0011, 000111, 00001111, \dots\}$$, where $$\epsilon$$ denotes the empty string (some people write $$\lambda$$ for the empty string, instead).
• @DiamondDude Is there any $n$ such that $0101$ consists of $n$ zeros followed by $n$ ones? – David Richerby May 15 at 11:56