DETERMINISTIC FINITE AUTOMATA (D.F.A)

About D.F.A :-

->In the theory of computation, a branch of theoretical computer science, a deterministic finite automaton (DFA)—also known as deterministic finite acceptor (DFA), deterministic finite-state machine (DFSM), or deterministic finite-state automaton (DFSA)—is a finite-state machine that accepts or rejects a given string of symbols, by running through a state sequence uniquely determined by the string. Deterministic refers to the uniqueness of the computation run. In search of the simplest models to capture finite-state machines, Warren McCulloch and Walter Pitts were among the first researchers to introduce a concept similar to finite automata in 1943.

->It is defined as a five tuple consisting with-

{Q, Σ, δ, q₀, F}

- a finite set of states 'Q'

- a finite set of input symbols called alphabet Σ

- a transition function δ : Q × Σ → Q
- an initial or start state 
- a set of accept states 

-> Finite automata will be Deterministic Finite Automata if the machine reads an input string one symbol at a time. In D.F.A. there is only one path for specific input from the current state to the next state i.e. an automaton that defines at most one transition for each state and each input symbol; the transition function is allowed to be partial. When no transition is defined, such an automaton halts.

-> Deterministic finite automata are always complete: they define a transition for each state and each input symbol.

Examples:-

1. Construct D.F.A. for input strings starting with 'a'.

--> By observing the given condition string should be start with 'a' i.e. {a, aa, aaa, abba, abbaaa, aabbaa.............} but not with 'b' i.e. the restricted cases are {b, bab, baaaa, babbbaa, ...........} 

So the D.F.A. diagram will be:-

- In the above diagram 'q0' is an initial state and the arrow behind it is indicated as a start. Now according to mentioned condition machine will accept string with starting symbol 'a' so at initial state 'q0' when 'a' will given as input that means condition is satisfied and then it directly goes to final state 'q1'(represented by concentric/double circle) where there is the self loop of further inputs of 'a' and 'b' i.e. strings are {abaa, aaaa, abbbaa,...} type. When at start 'q0' input 'b' will given then the condition according to question fails and then it goes to dead state 'qΦ' where the strings starts with 'b' occurs.

2. Constructs D.F.A. for all strings starting with 'a' and ends with 'b'.

--> By observing the given condition string should be start with 'a' and ends with 'b' i.e. {ab, abab, abbab, aaab, abaab.............} and the restricted cases are {a, bbab, baaaa, babaa, ...........} 

So the D.F.A. diagram will be:-

- In the above diagram 'q0' is the initial state where according to given condition in question when 'a' will given at the start it goes to the next state 'q1' because there must be 'a' at start in every string next at state 'q1' when again 'a' will given then it goes under self loop condition because as the minimum possible string will be 'ab' so for reaching to final state there must be 'b' at last or as an last input so when at state 'q1' , input 'b' will given then it finally goes to last or final state 'q2' but the end is not here. Suppose if further an another input 'a' will be given to 'q2' then it goes to or shifts towards state 'q1', it means that only the 'b' will accept at last/final state. Again 'qΦ' is a dead state where the strings that does not meets with the given condition forms.