DFA Example on Counting 1
In this class, We discuss DFA Example on Counting 1.
The reader should have prior knowledge of counting examples. Click here.
First Example: Design DFA That accepts strings containing four zeros and atleast two ones.
The input symbols are Σ={0,1}.
Counting four zeros logic was discussed in our previous classes.
Similarly, logic to check atleast two ones is also discussed.
We need to combine both the logic.
The below diagram shows the complete DFA.
The horizontal layer identifies the four zeros.
The vertical layer identifies atleast two ones.
Because the zeros are counted, and they need not be consecutive. The logic is complex.
For understanding, we are explaining the example in layers. DFA does not have layers.
Whenever we see one zero in our input string, we end up in the second vertical layer.
Example: 101 string we end up in state q12.
Similarly, if we encounter one, we end up in a second horizontal layer.
…...more
...more
Show less