Contains 101
Contains 101¶
Our last DFA example looks for a pattern. This is a simplification of something like DNA pattern analysis. We would have a huge string of letters representing the DNA and pattern we need to find. Again, a DFA might be able to solve our pattern.
The pattern we will look for is 101. We want to find a 101 someone in a file of ones and zeros. We need 4 states.
q0 we have not seen any of the pattern
q1 we only have a one.
q2 we have seen 10 must missing final 1.
q3 we have seen entire pattern 101.
We have 4 states and 2 symbols. This means we must have \(4 * 2=8\) states. Every state must have a symbol for every transition.
The DFA below covers this pattern. Study the transitions to figure out why they make sense.
The source code for the DFA is given below.
#This DFA Accepts the Language
#L={ contains 101 with sigma={0,1} }
#Define DFA Properties
symbols=(0,1)
states=(q0,q1,q2,q3)
start=q0
accept=(q3)
#Define Transition Table
if q0 and 0 then q0
if q0 and 1 then q1
if q1 and 0 then q2
if q1 and 1 then q1
if q2 and 0 then q0
if q2 and 1 then q3
if q3 and 0 then q3
if q3 and 1 then q3