Relationship of RE, NFA and DFA
Course : Compilation Techniques
1. Relationship of RE, NFA and DFA
For understanding the relationship between finite automata and regular expression,First, we can check these two separately
Regular Expression: It is the language that is used to describe the language and is accepted by finite automata.
Regular expressions are the most effective way to represent any language. Let Σ be an alphabet that denotes the input set.
The RE over Σ will be defined as follows −
- Φ is a RE for an empty set.
- ε is a RE and denotes the set { ε} and it will be a null string.
- For each ‘a’ in Σ ‘a’ is a regular expression and denotes the set {a}.
- If r and s RE denoting the language.
- L1 and l2 respectively then,
- r+s is equivalent to L1 U L2 union
- rs is equivalent to L1L2 concatenation
- r* is equivalent to L1* closure
The r* is known as Kleen closure or closure which indicates the occurrence of r for an infinite number of times.
Finite Automata(FA): It is an abstract computing device. This is a mathematical model of the system with discrete states, inputs, outputs and a set of transitions from state to state that occurs on input symbols from the alphabet Σ.
FA is defined as a 5-tuples
M=(Q, Σ, δ,q0,F)
Where,
- Q: Finite set called states.
- Σ: Finite set called alphabets.
- δ: Q × Σ → Q is the transition function.
- q0 ∈ Q is the start or initial state.
- F: Final or accept state.
let us understand the relation between them.
Step by step
Solved in 2 steps with 1 images
