Let D be decider for language. Now I will simulate an enumerator E using D.
Take all strings in lexicographic order and run D on each one by one. If D accepts then print out this string otherwise skip to next string and run D on it.
Vice versa follows:
Let E be enumerator for given language which enumerates in lexicographic order. Make decider D using E as follow.
Let E be enumerator for given language which enumerates in lexicographic order. Make decider D using E as follow.
Run E, it will generate strings one by one in lexicographic order. Compare given string when every time E generates a new string. If matches then halt E, and consider D accepts the input string. Else if decider have generated a string which comes later than input string in lexicographic order, reject input string. Because E is enumerating language in Lexicographic order and all next coming strings will be those who fall after input string.
No comments:
Post a Comment