4P61 Cheat Sheet: Automata and Formal Languages

Posted by on Jan 13, 2025 in Computational Mathematics | 0 comments

4P61 Cheat Sheet

Assignment 1

1) Function f: N→N has a fixed point at i such that f(i) = i. Show that the set is not countable.

Answer: If countable, f1, f2,… define function f; f(i) = fi(i) + i for i = 1, 2, 3,…

Therefore, (1) f does not have a fixed point since f(i) > i and (2) f ≠ fi since f(i) ≠ fi(i); i.e., not countable.

2) k≥1, A: N→(1, 2,… k), B: (1, 2,… k)→N. Is A or B countable?

Answer: k=1, only 1 function. If A is finite, then yes, it is countable. k>1, similar to

Read More