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.
$\begingroup$
$\endgroup$
8
asked Mar 8, 2014 at 20:35
-
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$– babouCommented Mar 8, 2014 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$– vznCommented Mar 10, 2014 at 3:52
-
$\begingroup$ @vzn: it is possible to enumerate recursively enumerable languages in a different way. $\endgroup$– Tanmoy BanerjeeCommented Mar 10, 2014 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$– vznCommented Mar 10, 2014 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 BanerjeeCommented Mar 10, 2014 at 15:41
|
Show 3 more comments
2 Answers
$\begingroup$
$\endgroup$
1
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.
answered Nov 4, 2015 at 13:20
-
$\begingroup$ I have a question: the definition of enumerator says it has no input, so how can you give the string s_j as the input to E. I notice you give s_j as input to R, but how can E knows that $\endgroup$ Commented Jan 9, 2023 at 3:17
$\begingroup$
$\endgroup$
2
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$.
answered Mar 9, 2014 at 0:53
-
1$\begingroup$ what is a python generator? $\endgroup$ Commented Mar 10, 2014 at 4:42
-
5$\begingroup$ @tanmoy it is not a female python. But if you do not know, just forget it. Python is a programming language. $\endgroup$– babouCommented Feb 18, 2015 at 0:59