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.

  • 2
    $\begingroup$ The link contains a very detailed guide. I suggest implementing the machine on a simulator and running it to see how it works. $\endgroup$ – Yuval Filmus May 13 at 21:06
  • $\begingroup$ 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}\}$. $\endgroup$ – 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).

  • $\begingroup$ Thank you for this answer it has definitely helped! Just wondering would 0101 be accepted by this language or must it always be a number of zeros equal to n followed by a number of ones equal to n? $\endgroup$ – DiamondDude May 15 at 11:18
  • $\begingroup$ @DiamondDude Is there any $n$ such that $0101$ consists of $n$ zeros followed by $n$ ones? $\endgroup$ – David Richerby May 15 at 11:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.