State machines... we meet again

On Wednesday, we were introduced to state diagrams and how to draw a circuit from given states and state transitions... I did FSMs back home when I was studying electronics... They are very useful for designing sequential circuits using JK flip-flops. I was surprised and happy to learn that we are learning how to use state machines in CSC236 but this time, we are not lighting leds or making a vending machine... instead we are building "circuits" to analyse strings.

Professor Danny used a very interesting software called jKFLAP (? not sure) where he made the circuit simply by drag-and-drop. I was also amazed that it can even test the circuit.. Now, how I wished I knew back then that there was such a software...

Unfortunately because of some personal problems, I missed two lectures (the ones dealing with formal languages) but it was pretty easy to catch up on the slides. I found that the laws for the equivalent REs on the slides were similar to the laws whether a vector belongs to a vector space from linear algebra (MAT223).

For example, there has to be the zero element or empty string such that:

( R + Ø ) = R # Ø is the empty string.

Theres only one thing I'm not too sure about and that is the "Idempotence of Kleene start" where:


( R** = R* )

I missed that lecture, unfortunately, but i'm wondering whether there is a typo and if it should have been: Kleen star (thats what google says)

Wikipedia states that: http://en.wikipedia.org/wiki/Kleene_star

1) If V is a set of strings then V* is defined as the smallest superset of V that contains λ (the empty string) and is closed under the string concatenation operation. This set can also be described as the set of strings that can be made by concatenating zero or more strings from V.


2) If V is a set of symbols or characters then V* is the set of all strings over symbols in V, including the empty string.

So for example:

{'a', 'b', 'c'}* = {λ, "a", "b", "c", "aa", "ab", "ac", "ba", "bb", "bc", "ca", "cb", "cc", ...}

Applying the Kleene star would mean it contains the zero element λ and all the elements 'a', 'b', 'c'

And then it would looke like:




We can notice a pattern in the number of elements that form after every "step" as shown in the image below: