I ask the students who voted incorrectly (some say anything except Stewart-Colbert-2020 is an incorrect vote, though I'm partial to Bee-Oliver, though John Oliver was not born in this country so he's not eligible, though our current president might say that neither was Obama so thats not a bar to the presidency) why they vote the way they do to get a good discussion going. I give some examples. I use real first names but decided to not give last names for reasons of security. The people involved all agreed. If you have examples of students being WRONG but HAVING A POINT, leave an intelligent comment about it!

1) In Discrete Math they vote on:

*is Q, the rationals, countable?*One of the NO votes was named Alice (really!).

**Alice**: The rationals, like there are SO many of them. They are just so crammed in their. I mean really!

**Bill**: I think you want to say that between any two rationals is a rational.

**Alice:**Thats what I said!!

**Bill:**Great! And realize that a set is countable if there is a bijection from the set to N. So what you are really saying is-----

**Alice:**There is a bijection between N and Q but not an order preserving Bijection!

2) In Formal Lang theory they vote

*if alpha is a reg expression and L(alpha) is the lang generated by alpha then is there a reg exp beta such that L(beta) is the complement of L(alpha).*One of the NO votes was named Andrea (nickname Andy).

*Andy:**Given alpha I just don't see an easy way, or for that matter any way, to create beta.*

**Bill:**I will soon prove that regular expressions are equivalent to DFA's. So what one would do is take the L(alpha), form the DFA, complement the DFA, then convert back to a regular expression.

**Andy:**Oh, yes that works, but it seems complicated.

**Bill:**It is! You though it would be complicated so it was false. Even though its true, your intuition that its complicated is correct! In fact, there are reg expressions of length n such that the complement lang has a rather large reg expression.

3) Formal Lang theory again. Not a vote this time. I had on the board the regular expression

(a UNION b)(a UNION b )^*

A student Dolapo thought it could be simplified:

**Dolapo:**Can't you write that as the regular expression (a union b)^+ ?

**Bill:**Yes and no. Yes the lang is (a UNION b)^+, but + is not allowed in regular expressions.

**Dolapo**: Why not?

**Bill:**First off, they really could have been defined that way and perhaps should have. So why weren't they? I go with historical accident, but some people disagree- see my blog post here

Isnt there a "b" missing as second argument of the second UNION in 3)

ReplyDeleteFixed, thanks

Deletebill g.

First: Ted Cruz was not born in this country and he ran for president anyway. Second: When I told my class that it is undecidable to tell if a program has an infinite loop or not, someone said if that if that were really so, the TA wouldn't be able to grade their homework. (Valid point.) - Mike Goodrich

ReplyDeleteIsnt there a "p" missing from "current resident"? (I guess this wasn't meant as a pun)

ReplyDeleteFixed- thanks.

ReplyDeleteWhen I first wrote it, it was intention- not an insult, I think I got it from a novelty song to the tune of Modern Major General (or to the tune of The Elements if you prefer) that rhymed President with

Resident and refered to the prez as the current resident. But its still wrong and confusing so I corrected it.