Polya Problem Solving

So if I remembered correctly I have to tackle a problem with Polya's problem solving strategy. The problem have chosen is really simple, yet the goal is that I carry out Polya's problem solving strategy, and an easy problem does not stop me from doing that. So the question is: Is every sequence of natural numbers finite and explain?

1. Understand the problem
So to answer the question, I either say yes and prove it, or say no and find an example of an infinite sequence of natural numbers.

2. Make a plan
This is one of those questions that are so obvious that direct reasoning can solve it. So the plan is to use direct reasoning.

3. Carry out the plan
It is less work to try to say no first because providing a counterexample is less work than proving something. So I will start by saying no and I will try to find a counterexample. So I know that there are an infinite number of natural numbers since if n is a natural number then n+1 is also. So the sequence 1, 2, 3, 4... is an infinite sequence of natural numbers for each term n, the next term is n+1.

4. Reflect
Saying no worked pretty well because if I had said yes I would have to deal with a non-working proof then conclude that the answer is no which takes a long time. So in a problem where I have no idea whether the answer is yes or no, I should first try the answer that has less work.

DFSA

DFSA was very scary when it came up because the name was very long and things with long names tend to be complicated. Luckily it seems pretty simple, at least the DFSAs relevant to CSC236. I am unsure on what it means to prove every single case at the same time but I assume it will be proven next class. So I really have nothing to say until the proof is presented.

As well, the equivalent RE properties resemble mathematical ones which makes them very easy to remember, although I hope memorization the name of each property is not required. Is it required?

Language?

When class first started I thought "this should be pretty easy, just some symbols and stick them together" but it started going downhill after the Kleene star since I was confused how the * is applied to the language when previously it applied to sigma, which is a set of symbols and how the * applied to the language gives the same result as * applied to the set of symbols in the language.

So I was confused for awhile until the examples came which I surprisingly got them somewhat correct since I did not understand the notations at all. Where did the (1 + 0)* come from when the Kleene star was either applied to the set of characters or the set of all strings in L? (1 + 0) does not use { } so how is it a set? So I kind of guessed that 1 + 0 = {1, 0} because of the + symbol meant union for languages although it was never explicitly said that it applied to symbols as well. All that was said was that (R + S) wasn't really defined, like how saying 1 + 3 is a valid arithmatic expression even if I did not know what 1 + 3 means. To me it would make somewhat more sense if it was ({1} + {0})* instead since (1 + 0)* could be taken as ("10")* for a new learner.

The difference between a regular expression and language is confusing as well so I hope I can differentiate them as I am type this. So according to my understanding, a language is the set of all strings formed by a regular expression. For example, L((10)*) would be the set of all strings {empty string, 10, 1010, ...}. A regular expression on the other hand is not the set of strings but identifies the set of strings. Ok, so maybe that is why (1 + 0)* is used instead because ({1}, {0})* would be a language instead of a regular expression?

Then there's the proof that was never completed in class but whose outline was given. I would prefer the proof (perhaps next class?) since I want to know the proper terminologies to use in this type of proofs.

Iterative Correctness

Wow, iterative correctness is so much more difficult then its recursive counter part. Iteration is generally easier to see than recursion but theirs proofs is the other way around, partly because induction is so close to recursion; they are like siblings. Iteration is too different. First there is just a bunch of variables in iteration and keeping track of them is a task in itself. Then there is the scary loop invariant. It is one of those things that a person just "sees" and unfortunately I am not one of those people who is able to just "see" it. In other words, I am screwed. As well there's a lot more parts to proving iteration compared to recursion. Argh! I am just going to memorize every type of iterative proof in class and then apply the corresponding loop invariant on tests and exams! It is likely not the best method but it should work, hopefully.