Automata-2018
Deterministic Finite Automata
Deterministic Finite Automata is a kind of Finite Automata that has only one state for each input. So, every state can determine one state. For instance:
- for input 1, State A only can determine State B
- for input 0, State A only can determine State C
Therefore, we can say this Finite Automata is deterministic because of that rule and also DFA has an initial state and final states like other kind of Finite Automata. The only difference of DFA is that it doesn’t have more than one initial state in a grammar.
Deterministic Automata is identified by this 5 properties which are (Q, ∑, δ, q0, F)
- Q is a finite set of states
- ∑ is a finite set of input symbols
- δ is a transaction that indicatives the next state with given an input and current state.
- q0 is initial state and also one of the states of Q
- F is set of final states, it can be more than one and also subset of Q
Transition Diagram
Transition diagram represents what is the next state for each states of Q. It is based on the grammar that is given before.
As you see shown above, there is a sample transition diagram that has one initial state and one final state and each state (to make it easier we use ( a,b,c,d ) instead of (q0 ,q1,q2,q3) ) goes one state for each input(0,1). This grammar is:
- w has both an even number of 0’s and an even number of 1’s
Transition Matrix
Transition matrix is a table that do the same function with transition diagram. It shows the next statement for current statement with an input which is given.
| Current State | Next State for Input 0 | Next State for Input 1 |
|---|---|---|
| -> * a | c | b |
| b | d | a |
| c | a | d |
| d | b | c |
Accept or Reject
These values of Transition Diagram and Matrix consist of a grammar that is generate with rules. We give an input value to program to see this input is accepted or rejected for the grammar. To do this, we can use transition diagram or transition matrix easily but to specify the operation step by step, we use yield notations.
Here is an example of yield notation for given grammar above:
-Q: {a,b,c,d}
-∑: {0,1}
-start state : a
-final state : a
input: 1001
(a, 1001) ⊢ (b, 001) ⊢ (d, 01) ⊢ (b, 1) ⊢ (a, ε)
a is final state, then ACCEPT
input: 11001
(a, 11001) ⊢ (b, 1001) ⊢ (a, 001) ⊢ (c, 01) ⊢ (a, 1) ⊢ (b, ε)
b is not final state, then REJECT
You can practice with my DFA sampling application which is written in JAVA. On this link you can download the jar file: DFA Sampling Application
Also, visit my GitHub profile page: https://github.com/merveozdemir
REFERENCES
For transition diagram:
https://compilandoconocimiento.com/author/compilandoconocimiento/page/4/
Other:
This page was made by Merve Özdemir