1. Consider the set {A, B} of strings over the symbols A and B. Recall that e is the empty string. Define the relation g on {A, B}* N such that (A.s, n x 100+12) 9 (,0) Eg if (s, n) g then ((B.s, n 1000 + 122) 9 For example, (ABAB, 1212212122) g and (BA, 12212) g. (a) State the condition for g to be function and argue that g is indeed a function. (2) (b) State the condition for g to be one-to-one and argue that g is indeed one-to-one. (2) (c) Show that g is total on {A, B}*: ) (d) Show that g is an encoding function for {A, B}*. (2) (e) Show that g is a Gdel numbering of {A, B}*. (3) (f) Use g to give an enumeration of {A, B}* (2) (g) State whether {A, B}* is finite or infinite and whether it is countable or uncountable. Justify your answer. (2) (h) Consider the set {A, B,C) of strings over the symbols A, B and C. Give a Gdel numbering g' of {A, B, C)* such that for any string s, if s {A, B}* then g(s) = g'(s). (3) (i) Is the set {A, B}* * {A, B, C}* enumerable? Justify your answer. (2) 1. Consider the set {A, B} of strings over the symbols A and B. Recall that e is the empty string. Define the relation g on {A, B}* N such that (A.s, n x 100+12) 9 (,0) Eg if (s, n) g then ((B.s, n 1000 + 122) 9 For example, (ABAB, 1212212122) g and (BA, 12212) g. (a) State the condition for g to be function and argue that g is indeed a function. (2) (b) State the condition for g to be one-to-one and argue that g is indeed one-to-one. (2) (c) Show that g is total on {A, B}*: ) (d) Show that g is an encoding function for {A, B}*. (2) (e) Show that g is a Gdel numbering of {A, B}*. (3) (f) Use g to give an enumeration of {A, B}* (2) (g) State whether {A, B}* is finite or infinite and whether it is countable or uncountable. Justify your answer. (2) (h) Consider the set {A, B,C) of strings over the symbols A, B and C. Give a Gdel numbering g' of {A, B, C)* such that for any string s, if s {A, B}* then g(s) = g'(s). (3) (i) Is the set {A, B}* * {A, B, C}* enumerable? Justify your answer. (2)