A site designed by Ashwarya Rathore and the Team
To convert a Regular Expression to NFA, DFA, Minimized DFA and check input strings.
A regular expression can also be described as a sequence of pattern that defines a string. Regular expressions are used to match character combinations in strings. String searching algorithm used this pattern to find the operations on a string.
Deterministic refers to the uniqueness of the computation. If the machine is read an input string one symbol at a time.
1. In DFA, there is only one path for specific input from the current state to the next state.
2. DFA does not accept the null move, i.e., the DFA cannot change state without any input character.
3. DFA can contain multiple final states. It is used in Lexical Analysis in Compiler.
The finite automata are called NFA when there exist many paths for specific input from the current state to the next state.
1. Every NFA is not DFA, but each NFA can be translated into DFA.
2. NFA is defined in the same way as DFA but with the following two exceptions, it contains multiple next states, and it contains ε transition.
Let X = (Qx, ∑, δx, q0, Fx) be an NFA which accepts the language L(X). We have to design an equivalent DFA Y = (Qy, ∑, δy, q0, Fy) such that L(Y) = L(X). The following procedure converts the NFA to its equivalent DFA −
Create state table from the given NFA.
Create a blank state table under possible input alphabets for the equivalent DFA.
Mark the start state of the DFA by q0 Same as the NFA.
Find out the combination of States {Q0, Q1,... , Qn} for each possible input alphabet.
Each time we generate a new DFA state under the input alphabet columns, we have to apply step 4 again, otherwise go to step 6.
The states which contain any of the final states of the NDFA are the final states of the equivalent DFA.
A Program which convert any RegEx to any Automation and also check String acceptance
Go ahead in below link to start converting now.
This is my Team :-
1. Ashwarya Rathore - RA1811029010056
2. Shefali Rai - RA1811029010062
4. Shipra Kumari - RA1811029010051
3. Pranav Singh - RA1811029010061
5. Arryan Sinha - RA1011029010036