Home, All Posts, RSS feed

Models of Computation | Lecture Notes 2

2016 August 31. Wednesday.

Last day in August! Another class of CS 575 (Models of Computation) with Dr Judy Goldsmith at UKY. I’m trying typing as we go instead of writing on paper in class then typing after.

By the way, these notes are not proofread or edited by her or anyone else, so they contain lots of mistakes.

Homework is about you learning, not testing you.

This means you can go to Dr G and ask her if a solution is correct, or ask her for help on a problem. You can also ask other students, just remember to thank them in the copy you turn in. You do the homework so you can learn the material.

BUT the exams are old fashioned alone and closed note, so don’t completely depend on others or the internet.

Regular Expressions

Question: What is the regular expression for strings of a’s that have length 2 mod 4?

Answer: aa(aaaa)* will generate all such strings. (aaaa)*aa also works and so does a(aaaa)*a. And here is a finite automoton that will only accept strings of a’s that are of length 2 mod 4:

2 mod 4 DFA
2 mod 4 DFA

Question from the audience: Is there more than one DFA that works?

Answer from Dr G: There are infinitely many DFA’s that work. You can just draw some unreachable frowny faces on the outside with nothing connected to them. However, there is one unique DFA that has the minimum number of circles.

Side note: To understand the coming lectures you should understand some things. If you don’t understand them, then google it:

Question: What is the implication of DFA having a loop?

Answer: If there is no loop then the DFA can not accept an infinite number of strings. You only know that the the language is infinite if it has an accept state (smiley face) in a cycle that is reachable from the start state.

Question: When does a regular expression generate an infinite set?

Answer: If it has a star (*) over a non-empty regular expression.

Infinite Hotel Continued

Question: You have infinite buses each with infinite passengers arrive at your infinite hotel with infinite rooms, one person in each room right now. How do you fit in the new arrivals?


Here is one way. Consider the guests in the rooms numbered a positive power of 2. So rooms 2, 4, 8, 16, 32... Do the even-odd thing from last lecture to make half of them empty. Put your first bus in those rooms. Then do it again with rooms 3, 9, 27, 81... Put your second bus there. Since there are infinitely many primes and their powers will never overlap, you can fit every guest on every bus into your hotel.

Here is another way. Do the original even-odd thing so that the odd numbered rooms are empty and the even rooms are full. Then pull the guests off one at a time, moving between the buses. Represent guest number n on bus number m as the pair (n, m). Fill your rooms in this order: (0,0), (0, 1), (1, 0), (1, 1), (0, 2), (2, 0), (1, 2), (2, 1), (2, 2), (0, 3), ...

Question: Let’s abstract and functionize the second solution above. Write a function f that forms a bijection from N x N (N is the natural numbers) to N.

Answer: One easy solution: f(m, n) = 11m 17n. And if infinite sets A and B have a bijective function g between them, then we say that A = B, so we have N x N = N.

Question for next class: You now have a parking lot with infinite spots numbered 1, 2, 3, .... There are infinite people numbered 1, 2, 3, .... There is a bus for each possible combination of people. How can you fit every bus in your parking lot?

Public Domain Dedication.