3
$\begingroup$

Currently I am studying Turing machines and I understand that a Turing machine can produce all the strings of the language accepted by that particular Turing machine. We call such a Turing machine an enumerator. I have studied the formal definition of enumerators that have no input. But I am unable to realize how a Turing machine can work as an enumerator for the language $L=\{a^nb^n:n\geq0\}$. Any help would be greatly appreciated.

$\endgroup$
  • 1
    $\begingroup$ Can you do a TM that produces only the empty string, and then stops? Can you do one that does it, and then produces the string "ab" and then stops. Then can you do one that follows it by a third string "aabb"and then stops. .... $\endgroup$ – babou Mar 8 '14 at 21:07
  • $\begingroup$ your 1st stmt is close but not strictly correct; only recursive languages can be enumerated, not the recursively enumerable languages. $\endgroup$ – vzn Mar 10 '14 at 3:52
  • $\begingroup$ @vzn: it is possible to enumerate recursively enumerable languages in a different way. $\endgroup$ – tanmoy Mar 10 '14 at 5:12
  • $\begingroup$ dont think so. what way are you referring to? iirc recursively enumerable languages are still said to be "accepted" by the TM... $\endgroup$ – vzn Mar 10 '14 at 15:20
  • 1
    $\begingroup$ @vzn: generate first string w1 using machine M1 and then make one move of processing of w1 using machine M2.Next generate w2 using M1 and let M2 execute one move on w2,followed by the second move on w1.After this we generate w3 and do one step on w3,the second step on w2,the third step on w1, and so on.In this way M2 will never get into an infinite loop. – $\endgroup$ – tanmoy Mar 10 '14 at 15:41
5
$\begingroup$

As your language $L$ is decidable ( lets its decider be $D$ ), you can build an enumerator $E$ for it ( which disregards its own input ). $E$ gives strings ( with alphabet being $\sum =\{a,b\}$ ) in increasing order ( lexicological order, which is possible as $\sum^{*}$ is a countable set ) to $D$ and if $D$ accepts an input $E$ prints it, if $D$ rejects an input $E$ does not print it. If your language is undecidable but recognizable this method won't work for making an enumerator for such a language.

EDIT

If $L$ is a recognizable but not a decidable language we can build an enumerator for it in the following way. Let $R$ be the recognizer for the language and $E$ the enumerator. The strings in $\sum^{*}$ are denoted as $s_1,s_2,....$ ( again in lexicological order ).

i = 1
while ( True )
  j = 1
  while ( j <= i )
     Give the string s_j as input to R and let R run for i steps,if R halts on
     s_j in at most i steps and accepts it, E prints the string s_j

     j = j + 1
  i = i + 1

Note with above method if a string belongs to $L$ it may be printed several times ( which can be avoided ). But unlike a decidable language there is no way to guarantee that strings are enumerated in lexicological order.

$\endgroup$
2
$\begingroup$

An enumerator is like a Python generator. It constantly enumerates words. There are several ways to define this formally, but suppose that the Turing machine has a special output tape, a special output state, and a special post-output state; whenever the Turing machine reaches the output state, the word on the output tape is output, and the Turing machines continues its operation in the post-output state. In this way, a Turing machine can output many words — possibly infinitely many. We say that the machine enumerates these words. In order to enumerate your language $L$, it can, for example, do the following:

  • Output the empty word.
  • Output the word $ab$.
  • Output the word $aabb$.

Continuing in the same way, the machine eventually outputs every word of the form $a^nb^n$.

$\endgroup$
  • $\begingroup$ what is a python generator? $\endgroup$ – tanmoy Mar 10 '14 at 4:42
  • 4
    $\begingroup$ @tanmoy it is not a female python. But if you do not know, just forget it. Python is a programming language. $\endgroup$ – babou Feb 18 '15 at 0:59

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.