HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

How turing machine can be used as enumerator

Submitted by: @import:stackexchange-cs··
0
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 ).

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.

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 + 1

Context

StackExchange Computer Science Q#22410, answer score: 6

Revisions (0)

No revisions yet.