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.

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.

*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`

:

*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:

- in a graph what it means for a node to be reachable
- spanning trees
- bread-first search
- depth-first search

*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.

*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?

*Answer:*

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) =`

11^{m} 17^{n}. 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.