patternMinor
How turing machine can be used as enumerator
Viewed 0 times
canhowusedmachineturingenumerator
Problem
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.
Solution
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 ).
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.
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 + 1Note 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.
Code Snippets
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 + 1Context
StackExchange Computer Science Q#22410, answer score: 6
Revisions (0)
No revisions yet.