NFA to DFA
DFA ⊆ NFA.
Epsilon Closure:- ε-closure is also defined for a set of states. The ε-closure of a set of states, P, of an NFA is defined as the set of states reachable from any state in P following ε-transitions.
For this topic refer to either the video itself or the example.
Regular Expression to NFAs
Lexical Specification —> regexp –> NFA –> DFA –> table-driven implementation DFA
NFAs of common regex:
Reference: Thompson’s Construction
Finite Automata I
- Finite automata is an implementation model fr regex which is a specification language for Lexical Analysis.
- A finite automata consists of:
∑: set of input alphabets
S: set of states
n: start state
F ⊆ S: accepting state(s)
transition function: state1—>(input) state2
- L(FA) = set of accepted strings
- In FA, string is matched when at the end if the input, pointer for the states is on the one of the accepting state(s), otherwise like in case if pointer is stuck or at the end the pointer is not on any accepting state(s) then matching fails.
- Notations are as follows:
- STATE -> CIRCLE
- START STATE -> CIRCLE having edge with NO SOURCE
- ACCEPTING STATE -> TWO CONCENTRIC CIRCLES
- TRANSITION -> EDGE CONNECTING TWO STATES