Tutorial 1

So for a3 Q1, I'm pretty sure everyone knows it's about DFSA :p. I mean, every the question says itself. So what is DFSA? DFSA stands for DETERMINISTIC FINITE STATE AUTOMATA. Let me state it an easy way, it is just like playing a board game. You start from the beginning  (initial state is the term), In our sake, you have 2 choice, left (0) and right (1). You are already given a path to walk already (ex: 10001000111). So you walk along the board. If you go to the pre-determined goal after finish walking all the indices, then you win (accepting state). If you can't, then you lose (rejected). This sounds simple right? I have some struggle with it first though. Because most of the question, you are not given the board, only the sequence. As far as the simple sequence go, it is pretty straight forward. However it will get messy sometimes.

Notice that this DFSA is just like Markov Chain from sta247 (I'm pretty sure most of us have to take it. If you aren't, then I'm really sorry, because I can't draw here.)
Let's do an example, 100
Whate you have to do it is:
you start on Initial state(q0)
Then you in order to advance, you look at the first element, it is one, so you make (q1) by using an arrow to indicate it transit by 1.
So what happen to 0? It will have another branch of to (q2) which transit by 0. However, we can clearly see that if you enter this q2, it will be in rejected by default, since there is no way you can get to 1 by going that way (think of it as a dead end). We have a special name for this sort of branch, and it's call death state. Usually for cleaness, we will not draw death state on the graph (board). Onto next 0, same steps, 2 branches, (q3) by transit by 0, (q4) transit by 1, which (q4) is a death end. Onto last element 0. For this, since we are already in (q3), which is transit by 0, think of (q3) is equal to 0, there is not point of advacing to the next path, since (q3) is already 0, we can just make a big U turn and go back to (q3) by transit 0. For transit 1, we branch out to (q4) which is a death state. Notice I can't do U turn for 1 is because think of (q3) is 0, 0 =/= 1, so it can't loop back. So we are at the end, and (q3) will be our accepting state (goal). If you land on anything other than (q3), it is by default going to reject.

Let's go through the definition of symbols of DFSA. So it looks like this:
 DFSA = (Q, S ,A , s, F)
where Q is the finite set of states(i.e how many steps it takes to go to the accepting state.)(ex: {q1,q2,q3}), S is the finite alphabet(i.e, the character contained in this sequence.)(ex: {0,1}),
A is the transition function(Q*S),
s is the Initial State (q0)
F is the set of accepting state (Whatever your accepting state is)

Last but not least:
The regular expression of DFSA is usually how the Question from a test look like,
L1 = {x belong to {0, 1} | x has an odd number of 0s and an odd number of 1s} (from textbook ex7.12)
So what does it mean in the {}?
For those who are new to this sort of expression, it simply means that we execute the condition before the "|" , however, that condition must to follow the condition after the "|". So in the example, it simply means that we have to find a x which only contains 0 and 1, and the x must follow the following condition: x has an odd number of 0s and an odd number of 1s.

I hope this helped you clarify any unclear concepts in your mind. Hope you all do good in the course, and see you next time :D.