Give a formal recursive definition of Regular Expression(RE)
Give a formal recursive definition of Regular Expression(RE)
A recursive definition is characteristically a three-step process:
1. First, we specify some basic objects in the set. The number of basic objects specified must be finite.
2. Second, we give a finite number of rules for constructing more objects in the set from the ones we already know.
3. Third, we declare that no objects except those constructed in this way are allowed in the set.
Any language-defining symbols generated according to some rule are called regular expressions.
A regular expression represents a "pattern“ strings that match the pattern are in the language, strings that do not match the pattern are not in the language.
Example:--
step1:- Every letter of including is a regular expression
step2: if r1 and r2 are regulars expression then
(r1), r1+r2, r1.r2, r1* is also a regular expression
step3: nothing else is a regular expression
Step by step
Solved in 2 steps
