DFA is the most important topic of TOC
Deterministic Finite Automata(Q,Sigma,q0 , F)
Let's say
q0 ---a--> q1
Automata ->To determine If the language is finite or infinite
-> If the language is sample or not
DFA(Q,Summation,q0,F)
Q = Set of all finite states
Summation = Set of alpha
Transition = What is the output after reaching in a state
q0 = Start State
F = Set of all final state
F subset of Q
Strings starting with a {a , aa , aaa , ab }
q0 --a--> q1
Summation(a,b)
q0---ab--->q1
.
.
b
.
.
.
q2
S : Q * Summation -> Q
q0
q1
q2 (a,b)
q0a ---- q0
q0b ---- q1
q1a ---- q2
q1b
q1a
q1b
It is an abstract machine that is used to recognize an input sequence . It consist of States , Transitions and input Symbols , Processing each symbol step by step .
It comes in deterministic and non deterministic .
It is widely used in text processing , compilers and network protocols .
Top comments (0)