Let us consider the possibility of an infinite automaton that starts with this infinite binary tree:

Let L be any infinite language of strings of a's and h's whatsoever. Show that by the judicious placement of + 's, we can tum the picture above into an infinite automaton to accept the language L. Show that for any given finite string, we can determine from this machine, in a finite time, whether it is a word in L. Discuss why this machine would not be a satisfactory language-definer for L.

Transcribed Image Text:

b a b