DFSA

I had some problems understanding how to create the state transition table for a given DFSA. I knew how to form transition tables using circuits but this one is a bit different. I read this great book: "Introduction to automata theory languages and computation 2nd edition by John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman" and the bank-store-customer example they used made it clear to me.

I used an example from the book and tried to solve it.

Problem 1: Design a DFSA that accepts a string that has the sequence "01" somewhere in the string

Solution: Let L be the language where:

{x01y where x and y are any strings of 0's and 1's}

So that means "01", "11010", "100011" ε L
but "100", 110000", "000", "111" is not contained in L.

Let q0 be the starting state. Now since we need to find string "01" we need a 'variable' to store the previous character so that we can compare. Let q1 be the state when we see a zero. So when we are in q1 and we see a "1", we can move to a final state q2 which is the accepting state. Now, if we are in q1 and we still encounter a "0" character, we shall stay in the same state. Similarly if we are in q0 and find a "1", its useless since the string desired should start with "01".

Finally once we step into q2, we dont have to worry if we encounter a "0" or "1" anymore since we will remain in q2 no matter what. (By the way, if i remember, in a JK flip-flop system, this is denoted by capital X which means 'dont care' state).

So our transition table looks as follows:

∂(q0, 1) = q0

∂(q0, 0) = q1
∂(q1, 0) = q1
∂(q1, 1) = q2
∂(q2, 0) = q2
∂(q2, 1) = q2

and our state diagram looks like:

Now what if we try and modify it and say we want it to accept any string containing the string "0101"

Problem 2: Design a DFSA that accepts a string that has the sequence "0101" somewhere in the string

So our state transition table will change and we have to introduce new states q3 and a final accepting state q4. So if we start at q0 and find a "1", its pretty useless and we remain in the same state q0. but if we find a "0" means that it is the start of the substring we are looking for. So we jump to state q1. Now from q1, if we find a "0" as the next character, we are back to square 1 so we jump back to q0. But if we find a 1, we jump to q2. Similarly, if we get a "0" while being in state q3, its useless since its not forming the substring we are looking for and we jump back to q0. But if we find a "1", then we jump to the final accepting state q4. Once we are in state q4, we 'dont care' about the incoming characters since we have already found our substring and we remain in state q4.

So our transition table becomes:

∂(q0, 1) = q0 ---------- ∂(q0, 0) = q1

∂(q1, 0) = q0 ---------- ∂(q1, 1) = q2

∂(q2, 0) = q3 ---------- ∂(q2, 1) = q0

∂(q3, 0) = q0 ---------- ∂(q3, 1) = q4

∂(q4, 0) = q4 ---------- ∂(q4, 1) = q4

And our state diagram would look like this:

I must thank Danny for showing us jFlap. Its a great tool to analyse state diagrams and find flaws.