NFSA and DFSA

NFSA stands for non-deterministic finite state automaton. DFSA stands for deterministic finite state automaton. My first intuition of these concepts were that these two ought to be a very different concept. Using this assumption, I was lost in the lectures and figured a few days later after searching online that these two concepts are relevant. DFSA is a finite state automaton where transition from a state to another is chosen in the first place. NFSA also allows states to transit from a state to another but for some cases, the transition is very ambiguous. That is why NFSA is called non-deterministic because transition is non-determined, while DFSA is called deterministic because transition is determined. They are also relevant because they can only recognize regular languages.

There is an example of NFSA online; in a binary string, determine if the input ends with 1.

This is pretty simple when the input is 0. However, problem raises when 1 is added. User does not know that if the the state has to be the accepting state or same as the current state. Due to this non-deterministic property, NFSA is called non-deterministic finite state automaton.

In my opinion using of NFSA is really bad idea because it needs further explanations to the readers. On the other hand DFSA seems really straight forward so that you do not need further explanation to understand the diagram.

As written above, the concept of DFSA is understood pretty well to me. However, NFSA is still ambiguous. I think I will ask the professor or search more examples online so that I can fully understand why NFSA is important. 

String and Finite States

Before discussing about finite states I will discuss some string definitions because the finite states will use string definitions to be proven. The common definition of alphabet is the standard set of letters which is used by some countries. In this computation theory, alphabet is a set of letters which can be combined to create a new word. A set of {b, e, r, d,s } is an example of alphabet. Alphabets can also contain numeric or non-characters. For example, {1, 5, 324, ㅎ, *, !} is also an example of alphabets. The notation for alphabet is S. String is a finite sequence of symbols over alphabet. 'boss' is an example of string from an alphabet set {a, b, o, s}. This string does not have to be the real word. Any combination from an alphabet set is still considered to be a string. From the previous example {a, b, o, s}, another example of string would be 'osboooba'. Obviously, this is not a real word. But this still is an example of string. Also, empty string is still an example of string. S* is the notation for the string. Language  is a set of strings from a set of alphabet. It can be empty or infinite. However, empty set and empty string are different things.
Finite States contain finite number of states where you can possibly move form one state. This is mostly used for creating electronic circuits. The state where you are currently at is called current state. You can also move from one state to another. This movement is called transition. From computation theory point of view, there is a transition formula where the condition is given in order to move from one state to another. There are two different states to the finite states. The first is accepting state. This state accepts an claim. The second is rejecting state. It rejects a claim.

For the finite states, there was an example question online; create a state machine which determines if a binary string contains even number of 1s. This is an easy example. You create two states; one called accepting state and the other called rejecting state. It will start from the accepting state because empty binary string is still considered to contain even number of 1s. For both cases, it transit to itself if 0 is added to the end. If 1 is added to the end, it moves to the other state.

For this strings, the concepts were really easy to understand because they all comes from the previous year studies. For example, python strings do not have to be the real world word. I found difficult was the state machine because the design of the finite state can vary from a person to another. I still understand that there is the best way to describe a finite state but finding the most efficient design was really hard for me. It would be extremely helpful if there was many examples but the class only covers a few examples. I think these are not enough to fully design an efficient finite state.
Upon learning of the string, it was extremely boring to me because it felt like we are reviewing stuffs that we learned long times ago. At the same time, finite states were not really new to me as well as the string because this is what I was learning in CSC258, a computer organization course from University of Toronto. However, it made a difference because it was still hard for me to develop a design in both classes. First intuition of this chapter was like 'I am so screwed.'
From the finite states, I decided that I should look up some questions regarding this topic because I know that I am really bad at this and I really want to improve on this.

Correctness Of An Iteration

There are several terminologies that I learned this week. Precondition refers to a condition before a loop iteration is starting. Some binary sort algorithm requires the list of numbers to be sorted in a certain way. Postcondition refers to a condition upon termination of the loop. Loop Invariant refers to the condition when an iteration finish. The loop invariant of the last iteration should be equal to the post condition and the every loop invariant should satisfy the precondition. If precondition, loop invariant, and termination happens, post condition is automatically satisfied. Precondition does not need to be proved because the condition depends on the user input. Loop invariant needs to be proved because if the loop invariant does not satisfy, the post condition cannot be satisfied. In order to prove the loop invariant, you let the current iteration to be i and the next iteration to be i+1. Why do we consider the next iteration? It is because the variables at i+1th iteration is same as the variables at the end of ith iteration. Termination needs to be proved too. Mostly, we do not need to use induction to prove because we can refer to the loop invariant to prove the termination. In order to prove the post-condition we simply prove precondition, loop-invariant, and termination. Then we match with the post-condition.
From this, I learned that this will be useful to create an algorithm. Sometimes, a loop falls into a infinite loop. Rather then using trial-and-error method, this proof should take longer but make more senses to me. From now on, I think I will briefly use this method to create a looping algorithm to make sure that the loop terminates and returns the value I wanted.

Assignment Two Evaluation

For the question one, it took more for me to come up with a pattern then the proving. I wrote down all the possible cases until the length of the binary string became 6 and found a pattern of P(n) numbers. However, I still had to figure out the reason behind. Otherwise, my proof will become an intuition or a guess. I found out that P(n-1) and P(n-2) are related to P(n) and this is somewhat similar to Fibonacci's sequence. From this question, I learned that finding a pattern might be the toughest step and the rest is easy. I think what we are learning in this course is more about finding pattern and the lectures are there to help us explain the pattern in words. From now on, I will look closer to the pattern when it comes to proving or coming up with an algorithm.
The question two was about expressing time complexity of a binary search algorithm. It was similar to the question we learned in a tutorial and a lecture. It was just that we did not go deeply inside the concept. First, I had to prove that the P(n) is non-decreasing. It was basically the one from the textbook. I proved the time complexity in two different ways. The first was by inequality and proving both upper bound and lower bound. The second was using the master theorem.