THEORY OF AUTOMATA (DFA)

Automata theory

is the study of abstract machines and automata as well as the computational problems that can be solved using them

Deterministic Finite Automaton (DFA)

In DFA, for each input symbol, one can determine the state to which the machine will move. Hence, it is called Deterministic Automaton. As it has a finite number of states, the machine is called Deterministic Finite Machine or Deterministic Finite Automaton.

A DFA can be represented by a 5-tuple (Q, ∑, δ, q₀, F) where −

·        Q is a finite set of states.

·        ∑ is a finite set of symbols called the alphabet.

·        δ is the transition function where δ: Q × ∑ → Q

·        q₀ is the initial state from where any input is processed (q₀ ∈ Q).

·        F is a set of final state/states of Q (F ⊆ Q).

Example

String that generates a in start ends on b ?

So we see ab can generate any string ( ab,abab,aabb,abbab) so that can make those.

Another example

1.      ∑*aba∑*(ab)+

2.      States are alphabet of your name.

3.      Generate 10 strings length of 10.

4.      Run transition function on at least 1.

We see that string can be Empty the it can accept only “abaab” if not minimum “abaabaab”

So we create that

5-Tuple

·        Q (A,B,D,U,L,R,E).

·        ∑ (a,b). 

·        q₀ (A). 

·         F (R).

·         δ (A,abaabaab)--|B

δ (B,abaabaab)--|D

δ (D,abaabaab)--|U

δ (U,abaabaab)--|L

δ (L,abaabaab)--|R

δ (R,abaabaab)--|L

δ (L,abaabaab)--|L

δ (L,abaabaab)--|R

·         DFA diagram

R is the end state … so machine is working.

Thank you.