Finite State Machines

Todays tid-bit is about FSM (Finite State Machines) of which there are

NFA-E  Non-deterministic Finite Automaton - With E closure
NFA Non-deterministic Finite Automaton   explanation
DFA Deterministic Finite Automaton explanation

So I was doing my homework and then I came across a question about stating why a FSM has to be a DFA in order to have the complement of the FSM to recognize everything of the alphabet the original DFA cannot.

So after some investigation here is WHY you have to convert any NFA to a DFA for it to hold true for all complements.

Proof by counter example:

A final state has 2 circles around it
A non-final state has 1 circle around it
Arrows are transitions

When you take the complement of a FSM you do not change transitions, rather you change all final states to non-final states, and all non-final states to final. This allows for a Complement to handle anything from the alphabet the original couldn't.
So it becomes:
Final states: S0, S2, S4
Non-Final States: S3, S1

HOWEVER the input "E" will still be accepted by the complement, and thus both original and complement FSM will take same input breaking the rules of a complement! Therefore you NEED to have a DFA.

I hope you understood this! If you have a question/comment post it below. Thanks for reading!

Useful CS Links

Hey guys! Me here again, here are some helpful links:


http://stackoverflow.com/
For all your CS programming related questions, c++, vb, javascript, java, c#, etc. Be careful what you ask though, their ban on questions is quite extensive, they really hate "dumb" questions.

http://math.stackexchange.com/   Similar: http://mathoverflow.net
Same as above but for math.

http://serverfault.com
""" But for servers..

http://superuser.com
""" for random tech questions

http://www.w3schools.com/
A website to teach you everything that you need to know to create a website from HTML to XML to PHP and AJAX. (To be honest, I'm only vaguely knowledgeable about these topics, I'm actually educating myself using this site haha)

http://codingbat.com/
For learning Java, and now offers Python education. Good for introduction and even "medium" level topics such as advanced recursion.

Hello World

This will be the Computer Science "division" of my blogs. Anything cs/math related will go onto this blog, therefore I'm moving my original post about binary to here:


So "hello world" :) I completely forgot about this website for a long time. So here's my first post. To start with I'll tell you what's going on with me,
20 years old, going to college and gunning for a Computer Science degree, I enjoy lifting and sports, and watch way too many movies/shows. You'll probably get to know tid-bits about me as I progress on this blog, I'll post some instructions for random things, and perhaps some "personal" posts.

Explanation to the name of the blog: The name is "Bit of a Byte" which is a pun on the words "bit" and "byte" since there are 8 bits in a byte, and a bit is also defined as a "small portion of something else" and byte can be read as "bite" in this scenario.
Explanation of Bit: http://en.wikipedia.org/wiki/Bit
Explanation of Byte: http://en.wikipedia.org/wiki/Byte

And for this first post... As I delay going to bed right before my CS 301 midterm (Languages and Automata) I decided to make a small post :)


Let's start with a common thing that most common people don't know/understand. "Numbering systems." Simply speaking there are an infinite amount of number notations for representing an integer. E.g. we as a society use "base ten" numbering, so 18394. Or 100011111011010 in binary.

Think of it this way,  4 is in the "1's" slot because it is position 0 in the set of numbers, therefore 10^0 e.g. "1" so we take 10^0 and multiply it by the number in the slot, 4 in this case and get "4".  (the ten is because we are in base ten, in binary it would be "2")

As additional example:
29 into binary is 11101

Let's break it down: 2 * 10^1 = 20
9 * 10^0 = 9
20 + 9 = 29

In binary
1 * 2^0 = 1
0 * 2^1 = 0
1 * 2^2 = 4
1 * 2^3 = 8
1 * 2^4 = 16
1 + 4 + 8 + 16 = 29

Remember we go right to left on the number when we "increase" the exponent, the first number, or the "1's" place is always to the 0 power, and ten's place is to the "1" power, etc.
I hope this helps, if not there are more explanations online!


GOOD NIGHT