Sunday 6 April 2014

Sipser 3.18 show that a language is decidable iff some enumerator enumerates the language in lexicographic order.

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.
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