Regular Expression Basics and rules in theory of automata

By: Prof. Dr. Fazal Rehman Shamil | Last updated: December 11, 2024

In the Theory of automata, languages can be defined with different techniques. Some of these are mentioned below;

• Language definition by using the Descriptive definition
• Language definition by using the Recursive definition
• Language definition by using the Regular Expressions (RE)
• Language definition by using the Finite Automaton(FA)

What is a regular expression?

Regular expressions are used to generate patterns of strings. A regular expression is an algebraic formula whose value is a pattern consisting of a set of strings, called the language of the expression.

What are the rules for developing regular expressions?

Rule:

R.E =  a⁺

Valid Strings = a, aa, aaa, aaaa, aaaaa,……….

Language: Language of all strings that can generate one a and can also generate multiple a’s together.

Note: This example is for  a⁺. Similarly, you can generate the regular expression for any other alphabet like b⁺, c⁺, 0⁺ or 1⁺  and for any other alphabet. 

• When + is used as a power, then it represents a loop that can run null time or any time.
• When + is used as an operator between operands, then it represents the or operator with the help of which we can chose the right side or left side.

 

---

Rule:

R.E =  a^*

Valid Strings = Λ, a, aa, aaa, aaaa, aaaaa,……….

Language: Language of all strings that can generate Null(Λ), one a and can also generates multiple a’s together.

Note: This example is a^*. Similarly, you can generate a regular expression for any other alphabet like b^*, c*, 0^* or 1^*  and for any other alphabet.

Detailed tutorial on what is meaning of null or epsilon

---

Rule:

R.E =  a

Valid Strings = a

Language: Language of all strings that can generate only one a or it can generate only one b. Nothing else.

---

Rule:

R.E =  (a+b)

Language: Language of all strings that can generate only one a or it can generate only one b. Nothing else.

Valid Strings = a, b

---

Rule:

Every string that is part of the language should be accepted by the R.E and every string that is not part of the language should be rejected by the R.E.

• If 99% strings that are part of the language and are accepted by the R.E and if only 1% string is the string that is part of the language and is rejected by the R.E, then R.E is still wrong.
• If 99% strings that are not part of the language and are rejected by the R.E and if only 1% string is the string that is not part of the language and is accepted by the R.E, then R.E is still wrong.

For example;

Language = language of all those strings starting with a, defined over ∑=(a,b)

Accepted strings: a, aa, aba…………

Rejected strings: b, ba, bb, bab, ………

R.E =a(a+b)^*

Practice:

Now, let’s check how strings can be accepted by R.E. 

R.E =a(a+b)^*

Strings: a, aa, ab, aab, aaab, aba, ababab,………

Similarly, another example is

Language= language of all those strings starting with b, defined over ∑=(a,b)

Accepted strings: b, ba, bb, bab,…………

Rejected strings: a, aa, ab, aba,……..

R.E = b(a+b)*

Practice:

Now let us check that how strings can be accepted by R.E

R.E =b(a+b)^*

Strings: b, ba, bb, bab, baab, bba, bbabab,………

A regular expression for the language of all those strings in which NO bab occurs in the string. defined over {a,b}
solution:  R.E= a*b*a*

 

---

Regular expression for the set of all strings of a’s and b’s that have at least 2 a’s.

(a+b)* a (a+b)* a (a+b)*

Valid strings={aa, aaa, baa,aab, aba, abba,…}

InValid strings={a, b, baa,abb, abb, abbb,…}

 

---

Regular expression for the set of all strings whose first symbol from the right end is a 0.
L = (0+1)*0
Regular expression for the set of all strings whose second symbol from the right end is a 0.
L = (0+1)*.0.(0+1)
Regular expression for the set of all strings whose 3rd symbol from the right end is a 0.
L = (0+1)*.0.(0+1).(0+1)

Describe the strings that are represented by the regular expression (0+1)*.0.(0+1).(0+1).

Valid Strings={0000,1000, 1010, and many other similar strings}

Regular expression for the strings that do not contain a as a string defined over {a,b}

(b)*

Regular expression for the strings that do not contain single a as a string defined over {a,b}

(aa+b)*

---

A regular expression for the language of all
those strings having even length strings and
starting with a
or
odd length strings
starting with b

RE = a(aa+bb+ab+ba)*(a+b) + b(aa+bb+ab+ba)*

Download Slides

Regular Expression Basics and rules Slides PPT

Similar regular Expression

1. Regular expressions for all non empty strings
2. Regular expressions for all non empty strings of even length
3. Regular expressions for all non empty strings of odd length

More Examples of Regular Expression 

1. Regular Expression for no 0 or many triples of 0’s and many 1 in the strings.
2. RegExp for strings of one or many 11 or no 11.
3. Regular expressions for all non empty strings
4. Regular expressions over {a, b} for all non empty strings of even length
5. Regular expressions for all non empty strings of odd length
6. A regular expression for ending with abb
7. A regular expression for all strings having 010 or 101.
8. Regular expression for Even Length Strings defined over {a,b}
9. Regular Expression for strings having at least one double 0 or double 1.
10. Regular Expression of starting with 0 and having multiple even 1’s or no 1.
11. Regular Expression for an odd number of 0’s or an odd number of 1’s in the strings.
12. Regular Expression for having strings of multiple double 1’s or null.
13. Regular Expression (RE) for starting with 0 and ending with 1.
14. RE for ending with b and having zero or multiple sets of aa and bb.
15. A regular expression of the second last symbol is 1.
16. RE for starting with 1 having zero or multiple even 1’s.
17. Regular Expression for multiple a’s and multiple b’s.
18. RE for exactly single 1 many 0’s |exactly single a many b.
19. A regular expression for strings starting with aa and ending with ba.
20. A regular expression for the language of all consecutive even length a’s.
21. A regular expression for the language of all odd-length strings
22. A regular expression for the language of all even length strings but ends with aa.
23. A regular expression for the language of an odd number of 1s.
24. A regular expression for the language of even length strings starting with a and ending with b in theory of automata.
25. A regular expression for the language of all even length strings but starts with a.
26. A Regular Expression for the Language of all strings with an even number of 0’s or even number of 1’s.
27. A regular expression for the language of all those strings end with abb.
28. A regular expression for string having must 010 or 101.
29. Regular expression of  strings begin with 110
    Regular expression of  strings begin and end with 110
    Regular expression of strings containing exactly three consecutive 1’s.
30. A Regular Expression of all strings divisible by 4.
31. A Regular Expression Strings that does not contain substring 110.
32. Regular expressions for all strings with at least one a
33. Regular expressions for all strings with at least two a’s
34. Regular expressions for All strings with exactly two b
35. Regular expressions for at least one a and at least one b
36. Regular expression form end in a double letter (two a’s or two b’s)
37. Regular expression for All strings containing exactly one a

Closure Properties of Regular Expressions

• Union
• Intersection
• concatenation
• Kleene closure
• Complement

Tutorial: Regular Expression

A detailed tutorial of the regular expression is here in the link of regular expression tutorial. This page contains the practice questions of regular expressions with solutions.

Tutorial covering the topics

• Give a regular expression.
• Describe the strings of the regular expression.
• write a regular expression.
• create all strings from regular expression.
• Generate all strings from regular expression.
• Extract all strings from regular expression.
• Find all strings from regular expression.
• Examples of regular expression.
• What is * in regular expression?
• What does + mean in regular expression?
• What is a “.” in regular expression?
• What does the regular expression r=(a+b+c)*?