First of all, I want to explain you what the finite automata (FA) is. Then i will define NFA and DFA after them i will tell how to convert NFA to DFA. So let’s start.
A finite automaton (FA) is a simple idealized machine used to recognize patterns within input taken from some character set or alphabet. The job of an FA is to accept or reject an input depending on whether the pattern defined by the FA occurs in the input. So we can say Finite Automata(FA) is the simplest machine to recognize patterns.
A Finite Automata consists of the following : Formal specification of machine is : { Q, ∑, q, F, δ }. Q : Finite set of states. ∑ : set of Input Symbols. q : Initial state. F : set of Final States. δ : Transition Function.
We can represent a FA graphically, with nodes for states, and arcs for transitions. We execute our FA on an input sequence as follows:
FA is characterized into two types:
Deterministic finite automata - a state machine for which each transition for a state is uniquely determined by it’s input symbol as each state can only have a single move per input symbol. In a DFA, for a particular input character, machine goes to one state only. A transition function is defined on every state for every input symbol. Also in DFA null (or ε) move is not allowed, DFA can not change state without any input character.
Non-deterministic finite automata - a state machine that can have states with multiple transitions for the same input symbol, and that can make “epsilon” moves, for no input at all. NFA is similar to DFA except following additional features:
Due to above additional features, NFA has a different transition function, rest is same as DFA. One important thing to note is, in NFA, if any path for an input string leads to a final state, then the input string accepted.
Some Important Points:
To facilitate understanding of NFA, we convert it to DFA. Let’s make an example to make it easy to understand. Regex of this example is (ab + abb)*.
δ | a | b |
---|---|---|
->*s | { p } | Ø |
p | Ø | { s, p } |
q | Ø | { s } |
Now, lets analyze our example. Our initial state is { s } . There is only one final state and its state { s } again. So in our transition table, we put “->” for showing the initial state. And we put “ * “ for showing the final states. There is empty cluster sign in our table. So that means this table not belongs to DFA. So it belongs to NFA. And there is multiple move choices for p states b symbol. In DFA, it’s input symbol as each state can only have a single move per input symbol. So this table not belongs to DFA. Then its NFA.
Open the application that i have made.. And select the first regex which is (ab + abb)*.When you select the regex, you can see the NFA diagram at below.
Click here to download the application
Let’s convert it to DFA.
Click Go One Step or Move Automatically button
Click Go One Step button or if you clicked Move Automatically button wait 2 sec.
Click Go One Step button or if you clicked Move Automatically button wait 2 sec.
Click Go One Step button or if you clicked Move Automatically button wait 2 sec.
Click Go One Step button or if you clicked Move Automatically button wait 2 sec.
Click Go One Step button or if you clicked Move Automatically button wait 2 sec.
Click Go One Step button or if you clicked Move Automatically button wait 2 sec.
Click Go One Step button or if you clicked Move Automatically button wait 2 sec and you will see the error message that says DFA table is filled.
There is another example for you to see in the application. So if you came up to here I suggest you to complete the other example too.
To see the other examples you have to click the Reset button and then select the other regex. Then you good to go.
http://jacobappleton.io/2015/07/20/regex-iv-from-nfa-to-dfa/#tocAnchor-1-3 https://www.cs.rochester.edu/~nelson/courses/csc_173/fa/fa.html https://www.tutorialspoint.com/automata_theory/deterministic_finite_automaton.htm https://www.geeksforgeeks.org/toc-finite-automata-introduction/