6

Let sigma = {1, #} and Y = {w | w = x^1 # x^2 # ... # x^k # where k Greaterthanorequalto 0, x^I epsilon 1*, and if i notequalto j then x^I notequalto x^j} In other words, Y is the set of all strings that have zero or more substrings that consists of 1s cannot be of the same length. For instance, # epsilon Y and 1 # epsilon Y, but 1 # 11 # 1 # epsilon Y. If Y is regular, draw the corresponding state diagram of the FA. Otherwise, use the pumping lemma proof to show that Y is not regular. Let sigma = {1, #} and Y = {w | w = x^1 # x^2 # ... # x^k # where k Greaterthanorequalto 0, x^I epsilon 1*, and if i notequalto j then x^I notequalto x^j} In other words, Y is the set of all strings that have zero or more substrings that consists of 1s cannot be of the same length. For instance, # epsilon Y and 1 # epsilon Y, but 1 # 11 # 1 # epsilon Y. If Y is regular, draw the corresponding state diagram of the FA. Otherwise, use the pumping lemma proof to show that Y is not regular