What is Regular Expression in TOC ?
Regular Expression (RE, regex, regexp) is :
An expression that expresses the set of strings
according to certain syntax rules is considered a regular expression. These
expressions have certain notations which we can describe in the regular
language. This notation involves a combination of strings of symbols from some
alphabet Σ, parentheses, and the operators +, ·, and ∗.
In terms of the theory of computation the regular
can be defined as a language or string accepted by a Finite Automata. We know
that a finite automaton consists of 5 tuples {Q, Σ, δ, q0, F}. A
regular expression is a string on Σ, i.e., it consists of only input alphabets.
Let Σ be an alphabet. The regular expression over Σ and the sets they
denote are:
- Ф is an r.e and denotes an empty set
- є is an r.e and denotes the set { є }
- For each ‘a’ in Σ, a+ is an r.e and denotes the set
{a}
If ‘r’ and ‘s’ are r.e. denoting the languages R
and S respectively the (r+s), (r.s) and (r*) are r.e
that denote the sets RUS, R.S and R* respectively
Basic Operations on Regular Expression
Three basic operations are union, concatenation, and closure.
· The operation of the union on RE:
If R1 and R2
are two REs over Σ, then L(R1 ∪ R2) is denoted by L(R1 + R2).
L(R1 ∪ R2) is a string from R1 or a string from R2.
L(R1 + R2) = L(R1) ∪ L(R2).
· The operation of concatenation on RE:
If R1 and R2
are two REs over Σ, then L(R1 ∩ R2) is denoted by L(R1R2).
L(R1 ∩ R2) is a string from R1 followed by a string
from R2.
L(R1.R2) = L(R1).L(R2)
· The operation of closure on RE:
If R1 and R2 are two REs over Σ, then L(R*) is a
string obtained by concatenating n elements for n ≥ 0.
Kleene’s Closure
It is defined as a set of all strings including null (Λ) obtained from the
alphabets of the set Σ. It is denoted as Σ*.
·
If Σ = {0}, then Σ* = {Λ, 0,
00, 000…}
Do you know What is the Difference between Closure and Kleene’s Closure?
Consider the following examples for a better understanding of Regular Expression
|
Regular
Expression |
Possible
String generated |
In
English, it is described as: |
|
10*1 |
11,
101, 1001, 1001…..} |
Set
of all strings beginning and ending with 1 with any number of 0 in between
the two 1s. |
|
a*b* |
{Λ,
a, b, aa, bb, ab, abb, aab,...} |
Set
of all strings of ‘a’ and ‘b’ containing any number of ‘a’ followed by any
number of ‘b’. |
|
(ab)* |
{Λ,
ab, abab, ababab, …} |
Set
of all strings of a and b with an equal number of a and b containing ‘ab’ as
repetition |
|
(a*
+ b*) c* |
a, aa, aaa, aaa..,
b, bb, bbb, bbb..,c, cc, cc…, ac, aac, acc, b, ,bbc, bcc… |
Any
combination of ‘a’ or any combination of ‘b’ followed by any combination of
‘c’ |
|
(00)*(11)*1 |
{1,
001, 111, 00111, ……} |
Set
of all strings of ‘0’ and ‘1’ with even number of 0 followed by an odd number of
1. |
- Mealy Machine
- Moore Machine
- Rice Theorem
- Brief about Turing Machine
- Multi Dimension Turing Machine
- Multiple Turing Machine
- Parikh Theorem in TOC
- Parse Tree or Derivation Tree
- What do you Understand by Derivation
- MyHill Nerode Theorem
- Minimize Myhill Nerode Theorem
- Push Down Automata
- Know Where we use Automata
- What do you understand by Derivation of Grammar
- What is Context-free Grammar
- Example based on CFG
- Regular Expression in TOC
- What is Two-way infinite Turing machine?
- Example to generate Parse tree from the given grammar
Also Read, some interview tips
- Why Should I Hire You?
- What are your weaknesses?
- What are your greatest strengths?
- Tell me about yourself.
- What's the reason behind leaving your current position at your company?
- Do You Know how the power of Keywords impacts on Resume?
- Top 8 Proofreading Tips and Techniques in 2022.
- Top Ten Technical Resume Writing Tips in 2022.
- Tips for your resume before you get entry to Job Market
- What Questions you can ask HR during the Interview.
- How to make an impressive resume?
- Best Resume writing Technique.
- What Questions you can ask HR during the Interview.
About Tarun Pare
No comments