Consider a generalization of a homemorphism, where we define a nondetermineistic homeomorphism h to be a function
Question:
Consider a generalization of a homemorphism, where we define a “nondetermineistic homeomorphism” h to be a function from an alphabet S to sets of strings over an alphabet T. For example, consider S = {0,1}, and T = {a,b}, where h(0) = {a,aa} and h (1) = {c, b}. For any language L Í S*, we define h (L) Í T* to be all strings over T that can be obtained by starting with a string w Î L and replacing each 0 in w with one of {a,aa} and replacing each 1 in w with one of {a,b}. Note that our choices do not need to be consistent we can replce some 0’s with a and others with aa, etc. If L is regular, does it follows that h (L) is regular as well? If, so, provide a proof. If not provide a counterexample.
Introduction to Operations Research
ISBN: 978-1259162985
10th edition
Authors: Frederick S. Hillier, Gerald J. Lieberman