Regular Expression In TOC

Regular expressions in TOC is a powerful mathematical tool used to define regular languages, which are recognized by Finite Automata.  They are similar to arithmetic, logic, and Boolean expressions in representation but different in their operation and purpose.

• Regular expressions are used for representing certain sets of strings in an algebraic fashion.
• Regular expressions generate sets of strings (finite or infinite in number) that always represent a unique and specific regular language.
• Each of these regular languages can be recognized and accepted by a finite automata.

The following figures show the above description of regular expressions in the TOC

Important: If the language (L) is regular, then there must exist a DFA, NFA, or regular expression for that language. Regular expressions, DFAs, and NFAs all have the same computational power

Regular Expression Symbols in TOC

Regular Expression Symbols in Theory of Computation (TOC) include alphabet symbols (a, b), epsilon (ε), empty set (∅), union (+ or |), , and Kleene star (*). These symbols are used to define and construct regular languages that can be recognized by finite automata like DFA and NFA. Here is the table of symbols of RE.

Regular Expression Representation in TOC

Let “R1” and “R2” be two regular expressions; then the representation of the regular expression is given below

• R1 + R2 ≡ R1 U R2 ≡ R1 | R2 ≡ R1,R2

Above are equivalent notations used in regular expressions to represent union (OR choice) between expressions

Note: while represention regular expressions, the power of regular expression can be number, * or +, but cannot use variables in terms of power i.e. m, n etc. Variables as powers, such as a^n, or a^m, are not part of regular expression syntax because “n” and “$m”$are unspecified values. However, in language notation or mathematical descriptions of languages, variables are allowed:

Basic Regular Expressions in TOC

In Theory of Computation (TOC), basic regular expressions are used to describe regular languages. The common regular expressions and their regular languages is given in the following diagram

Important:

Sometimes you find the regular expressions like following

• RE = (a+b)*a*b*

In the above regular expression $(a+b)*$already generates all possible strings over {a,b}, appending a*b* is extra, no need to add it. So we can write

• (a+b)*a*b* = (a+b)*

Operator Precedence in Regular Expressions

The operators used in Regular Expressions are evaluated according to their precedence rules. Parentheses () always have the highest priority and are used to change the evaluation order. The following diagram explains it in detail

Designing Regular Expressions in TOC

In this section, regular languages are given, and we will design the regular expression for them.

RE Example 01: Language Contains “aa” as a substring

If the language contains aa as a substring  over the input alphabets {a,b} Then the regular expression is given below:

• RE=(a+b)* aa (a+b)*

The following diagram shows how the regular expression is obtained, where the language contains "aa" as a substring

Description:

• (a+b)* before aa allows any combination of a and b before the substring aa.
• (a+b)* after aa allows any combination of a and b after aa, ensuring every accepted string contains aa at least once.
• Examples accepted: aa, aab, baa, baab, aaba, bbaabb,....
• Examples rejected: ε, a, b, ab, ba, bab,...

 

RE Example 02: L = {w ∈ Σ* | │w| = 4 }

Let L = {w ∈ Σ* | │w| = 4 } over the input alphabets {a,b} Then the regular expression is given below:

• RE = (a+b)(a+b)(a+b)(a+b)
• RE = ΣΣΣΣ
• RE = (a+b)⁴

Above all, the three regular expressions are equivalent

The following diagram shows how the regular expression is obtained, where the language contains all strings of length 4.

Description:

• Each ((a+b)) represents one position in the string and allows either a or b to appear at that position.
• Four consecutive ((a+b)) terms ensure that every accepted string has exactly 4 symbols, neither more nor less.
• Examples accepted: aaaa, aaab, abab, baba, bbbb, abba, baab,….
• Examples rejected: ε, a, ab, aaa, aaaaa, ababab,….

RE Example 03: Language Contains at least “a”

If the language must contain at least a single”a” over the input alphabets {a,b} Then the regular expression can be written in various ways, as given below:

• RE= (a+b)* a (a+b)* // “a” anywhere in string
• RE =b* a (a+b)*    // first “a” point of view
• RE = (a+b)* a b*   // last “a” point of view

Above all, the three regular expressions are equivalent

The following diagram shows how the regular expression is obtained, where the language contains "a" as a substring

Description:

• RE = $(a+b)*a(a+b)*$ represents strings where a occurs anywhere in the string.
• RE = $b*a(a+b)*$ represents strings from the first a point of view, meaning all symbols before the first a must be b.
• RE = (a+b)*a b* represents strings from the last a point of view, meaning all symbols after the last a must be b.
• Examples accepted: a, ab, ba, aaa, bab, abba, bba,….
• Examples rejected: ε, b, bb, bbb, bbbb,….

RE Example 04: Language Contains exactly a single “a”

If the language contains exactly a single”a” over the input alphabets {a,b} Then the regular expression can be written as given below:

• RE= (b)* a (b)* 

The following diagram shows how the regular expression is obtained, where the language contains exactly a single"a" as a substring

RE Example 06: Language Contains at most a single “a”

If the language contains at most a single”a” over the input alphabets {a,b} Then the regular expression can be written in various ways, as given below:

• RE= b* + b*ab* 
• RE = b* (a+ε) b* 

The following diagram shows how the regular expression is obtained, where the language contains at most a single"a" as a substring

RE Example 07: Write RE for the language {01ⁿ01^m | m,n ≥ 1| }

If the language strings start with 0, followed by one or more 1s, then another 0, and again one or more 1s. over the input alphabets {0,1} Then the regular expression can be written as given below:

• RE= 01⁺01⁺

Regular Expressions for Even-Length Strings

Regular expressions for even-length strings are used to represent all strings whose total number of characters is even, such as length 0, 2, 4, 6, and so on. For the input alphabet {a, b}, The regular expression for even-length is given below:

• RE = (ΣΣ)* = ((a+b)(a+b))*

(a+b) means either a or b,(a+b)(a+b) generates strings of length 2

Examples:

• aa
• ab
• ba
• bb

((a+b)(a+b))* Repeats these pairs any number of times because characters are generated in groups of two, the total string length is always even.

Regular Expressions for Odd-Length Strings

Regular expressions for odd-length strings are used to represent all strings whose total number of characters is odd, such as length 1, 3, 5, 7, and so on. For the input alphabet {a, b}, The regular expression for odd-length strings is given below:

• RE = (ΣΣ)*Σ = ((a+b)(a+b))*(a+b)

Examples:

• a
• b
• aaa
• aba
• baa
• bbb
• ….

((a+b)(a+b))*(a+b) Repeats these pairs any number of times because characters are generated in groups of two, the total string length is always odd.

Regular Expressions for three-Length Strings

Regular expressions for three-length strings are used to represent all strings whose total number of characters is exactly 3. For the input alphabet {a, b}, the regular expression for strings of length 3 is given below:

• RE = ΣΣΣ = (a+b)(a+b)(a+b)

Examples: aaa, aab, aba, abb ,baa ,bab, bba, bbb,…. . total length always remains 3.

Regular Expressions for Strings Starting and Ending with Different Symbols

Regular expressions for strings starting and ending with different symbols are used to represent all strings where the first and last characters are different. For the input alphabet {a, b}, the regular expression is given below:

RE = a(a+b)*b + b(a+b)*a

Explanation:

• a(a+b)*b generates strings that start with a and end with b
• b(a+b)*a generates strings that start with b and end with a
• (a+b)* allows any combination of a and b in the middle

Examples generated bya(a+b)*b

• ab
• aab
• abb
• aaab
• abab
• ….

Examples generated byb(a+b)*a

• ba
• bba
• baa
• bbba
• baba
• …..

Because the first and last symbols must be different, strings like aa, bb, aba, and bab are not accepted.

Regular Expressions for Strings Starting and Ending with the same Symbols

Regular expressions for strings starting and ending with the same symbols are used to represent all strings where the first and last characters are the same. For the input alphabet {a, b}, the regular expression is given below:

• RE = a(a+b)*a + b(a+b)*b + (a + b)

Explanation:

• a(a+b)*a generates strings that start with a and end with a
• b(a+b)*b generates strings that start with b and end with b
• (a+b)* allows any combination of a and b in the middle
• a + b is added to include single-character strings

Examples generated by a(a+b)*a

• aa
• aba
• abba
• aaaa
• ababa
• …..

Examples generated by b(a+b)*b

• bb
• bab
• baab
• bbbb
• babab
• …..

Examples generated by a+b

• a
• b

Because the first and last symbols must be the same, strings like ab, ba, aab, and bba are not accepted.

Multiple Regular Expressions to Represent a Language

A single language can often be represented by more than one regular expression (RE). Different regular expressions may generate the same set of strings even though their structures are different.

It is also important to note that every regular expression represents a unique regular language.

Example 1: Language containing all strings over {a, b}

Equivalent Regular Expressions:

• RE₁ = (a+b)*
• RE₂ = (a* b*)*

Accepted strings: ε, a, b, ab, ba, aa, bb, aba, bab,....

Example 2: Language containing strings with at least one a

Equivalent Regular Expressions:

• RE₁ = (a+b)* a (a+b)*
• RE₂ = b* a (a+b)*
• RE₃ = (a+b)* a b*

All represent strings having at least one occurrence of a.

• Accepted strings: a, ab, ba, aba, baa
• Rejected strings: ε, b, bb, bbb

Example 3: Strings starting with a and ending with b

Equivalent Regular Expressions:

• RE₁ = a(a+b)*b
• RE₂ = aa*b + ab(a+b)*b

Both describe strings beginning with a and ending with b.

• Accepted strings: ab, aab, abb, aaab
• Rejected strings: a, b, ba, bb

Convert Regular Expressions to Strings

RE Example 01: RE = (01⁺)*

RE = (01+)* represents strings formed by repeating the pattern 0 followed by one or more 1s any number of times (including zero times).

• Accepted strings: The language may contain an empty string ε, or combinations like 01, 011, 0101, 01101,011011, 0110111 etc.
• Rejected strings: 0 (missing 1), 1 (does not start with 0), 10 (wrong order), 0011 (extra 0),010 (last 0 not followed by 1)

RE Example 02: RE = 1*(01⁺)*

RE = 1*(01+)* represents strings that may start with zero or more 1s, followed by zero or more repetitions of the pattern 0 followed by one or more 1s.

• Accepted strings: The language may contain an empty string ε, or strings like 1, 11, 01, 11101, 1011, 110101, 11101101 etc.
• Rejected strings: 0 (0 not followed by 1), 10 (ends with 0), 0011 (extra 0 before valid pattern), 010 (last 0 not followed by 1), 100 (final 0 missing required 1)

RE Example 03: RE = (0*1*)*, can it generate string 10?

The RE = (0*1*)* can generate every string over input alphabets {0,1} because the outer Kleene closure allows repeating the pattern multiple times. So, string “10” can easily generated.

The following figure explains it

RE Example 04: RE = a*(ba*)*, can it generate all strings over {a,b}?

The RE = a*(ba*)* can generate every string over the input alphabet {a,b}. The following figure explains it

So increasing the power of (ba*) increases the number of bs, while a* allows any number of as anywhere around those bs. Hence all strings over {a,b} can eventually be generated.

Note: In the following instances, we assume that the alphabet Σ is {0,1}. 1. 0*10= {w|w contains a single 1} 2. Σ*1Σ* = {w|w has at least one 1} 3. Σ*001Σ* {w|w contains the string 001 as a substring}.

Regular Expression Identifiers in TOC

Regular expressions (RE) in TOC are formed using alphabet symbols, ε, ∅, and operators like union, concatenation, and Kleene star, which together define regular languages, known as Identifiers of RE. Here is the list of identifiers (rules) in TOC

Let’s Explain Various Categories of Regular Expressions in the TOC. These categories include Basic, start with, end with, and start and end with some characters. Let’s see more than 40 examples that fall under these categories. Each example contains the following

• Derived strings from a given regular expression
• Specific Language is extracted from the given regular expression
• Deterministic Finite Automata (DFA) for a given expression.

Example Proof using Identifiers of Regular Expressions

Prove that (1+00*1) + (1+00*1) (0+10*1)* (0+10*1) is equal to 0*1 (0+10*1)*

LHS = (1+00*1) + (1+00*1) (0+10*1)* (0+10*1)

        = (1+00*1) [ε+ (0+10*1)* (0+10*1)]        
        =(1+00*1) (0+ 10*1)*                          We get, by using  ε + R*R = R* 
        = (ε. 1+00*1) (0+10*1)*                       We, get, by replace 1 with ε.R by using rule  ε.R = R
        =(ε+00*) 1 (0+10*1)*
        = 0*1 (0+10*1)* = RHS

Designing Regular Expressions – Examples

Problem: Design Regular Expression for the following languages over {a,b}

1. Language accepting strings of length exactly 2
2. Language accepting strings of length atleast 2
3. Language accepting strings of length atmost 2

Solution:

Part 01: Language (L) = {aa, ab, ba, bb}
Regular Expression (R) = aa+ab+ba+bb

= a(a+b) + b(a+b)

= (a+b) (a+b)

Part 02: Language (L)= {aa, ab, ba,bb, aaa, bbb, … }

Regular Expression (R) = (a+b) (a+b) (a+b)*

Part 03: Language (L) = {ε, a, b, aq, ab, ba, bb}
Regular Expression (R) = ε+a+b+aa+ab+ba+bb = (ε+ a +b) (ε+a+b)

NFA to Regular Expression Conversion

The process to convert an NFA to a regular expression is given below

Step 01: First, we write the equations (equ.) for each state, starting from the final. For equations, check incoming transitions to the state. Suppose at q3, two transitions are entering into q3 from q1 and q2 for inputs a and b, respectively, then the equation will be written as

• q3 = q1a + q2b

Step 02: Find the equation for each state.

Step 03: Apply the substitute method over equations, so that state symbols (i.e., q1, q2, q3) are removed from the final state equation

Step 04: If all state symbols are removed from the final state equation, only input symbols should remain. It will be the regular expression.

Let explain with an example: consider an NFA 

The following diagram explains the overall mechanism.

DFA to Regular Expression Conversion

By using a similar process discussed earlier, where we convert an NFA to a regular expression.

Consider a DFA

The following diagram explains the overall mechanism.

DFA to Regular Expression Conversion (when the DFA has Multiple Final States)

By using a similar process discussed earlier, where we convert an NFA to a regular expression. Just take the union of final states. Let start

Consider a DFA

The following diagram explains the overall mechanism.

Let’s start with the first category, with its 21 examples

Category 1: Basic Regular Expressions

Here’s a table that explains the basic components of regular expressions. The first column shows the expression, and the second explains its meaning.

Sr.	Regular Expression	Explanation
1	a	Only a single character "a".
2	ab	Sequence "a" followed by "b".
3	(a+b)	Either "a" or "b".
4	(a)*	Zero (ε) or more occurrences of "a".
5	(ab)*	Zero (ε) or more repetitions of the sequence “ab".
6	(a+b)*	Zero (ε) or more symbols from the alphabet {a,b} of any length, any order.
7	(a)+	One or more occurrences of "a".
8	(ab)+	One or more repetitions of the sequence "ab".
9	(a+b)+	One or more symbols chosen from "a" or "b".
10	(10+1)*	Zero (ε) or more repetitions of "10" or "1".
11	(01+10+1)*	Zero (ε) or more repetitions of "01", "10", or "1".
12	(a+b+c+d)*	Zero (ε) or more symbols chosen from "a", "b", "c", or "d".
13	(a+b+c+d)+	One or more symbols chosen from "a", "b", "c", or "d".
14	(ab+bb+cc+dd)*	Zero (ε) or more repetitions of "ab", "bb", "cc", or "dd".
15	101 + (0+1)*1	Either "101" or any combination of 0s and "1s” ending in "1".
16	11 + 00 + 0 + 10*	Either "11", "00", a single "0", or "1" followed by zero or more "0s”.
17	1(0 + 11) + 0(00 + 1)	Either "1" followed by "0" or "11", or "0" followed by "00" or "1".
18	ba + (aa + b)*	Either "ba" or any number of repetitions of "aa" or "b".
19	aa + ba + (aa + b)*	Either "aa", "ba", or any number of repetitions of "aa" or "b".
20	(00)*(0 + 1) + (1)*	Zero (ε) or more "00"s followed by 0 or 1, or any number of "1s”.
21	(001)* + (00)	Zero (ε) or more repetitions of "001", or exactly "00".

Note: All strings derived from step 01 are accepted by the DFA, which is designed in step 02.

Step 02: Possible strings, Language, and DFA for RE = a are given in the following diagram

Example 1.2: Regular Expression = ab

Step 01:  Find the strings that can be derived from the given expression RE = “ab”.. The following figure shows all possible strings that can be derived from RE = “ab”.

Note Again: All strings derived from step 01 are accepted by the DFA, which is designed in step 02.

Step 02: Possible strings, Language, and DFA for RE = “ab” are given in the following diagram

Example 1.3: Regular Expression = (a+b)

Step 01:  Find the strings that can be derived from the given expression RE = (a+b). The following figure shows all possible strings that can be derived from RE = (a+b).

Step 02: Possible strings, Language, and DFA for RE = (a+b) are given in the following diagram

Category 2: Start with Regular Expressions

Here’s a table that explains the second category (starts with) of regular expressions. The first column shows the expression, and the second explains its meaning.

sr.	Regular Expression	Simple Explanation
1	a(a+b)*	Starts with a, followed by any number (even zero) of as or bs in any order.
2	101*(0+1)*	Starts with 10, then zero or more repeats of 1, then zero or more mix of 0s and 1s.
3	bab(a+b)*	Starts with bab, followed by zero or any number of as or bs .
4	aa(aba+bab)*	Starts with aa, followed by zero or any number of the patterns aba or bab.
5	(a(bb)*)(a+b)*	Starts with a, then zero or more bbs, then zero or any number of as or bs in any order.
6	1(0+1)(00+11)*	Starts with 1, then either 0 or 1, then zero or more repeats of 00 or 11.
7	a+b+c(ab+bb+cc)*	One"a", One “b”, or starts with"cand then zero or more repeats of ab, bb, or cc patterns.
8	a+b+c+d(ab+bb+cc+dd)*	One"a", One “b”, One “c” or starts with"dand then zero or more repeats of ab, bb, cc, or dd patterns.
9	aba(a+b)* + bab(a+b)*	Either starts with aba or bab, followed by zero or any number of as or bs

Example 2.2: Regular Expression = 101*(0+1)*

Step 02: Possible strings, Language and DFA for RE = 101*(0+1)* are given in the following diagram

Example 2.3: Regular Expression = bab(a+b)*

Step 02: Possible strings, Language and DFA for RE = bab(a+b)* are given in the following diagram

Example 2.4: Regular Expression = aa(aba+bab)*

Step 02: Possible strings, Language and DFA for RE = aa(aba+bab)* are given in the following diagram

Example 2.5: Regular Expression = (a(bb)*)(a+b)*

Step 02: Possible strings, Language and DFA for RE = (a(bb)*)(a+b)* are given in the following diagram

Example 2.6: Regular Expression = 1(0+1)(00+11)*

Step 02: Possible strings, Language and DFA for RE = 1(0+1)(00+11)*  are given in the following diagram

Example 2.7: Regular Expression = a+b+c(ab+bb+cc)*

Step 02: Possible strings, Language and DFA for RE = a+b+c(ab+bb+cc)* are given in the following diagram

Example 2.8: Regular Expression = a+b+c+d(ab+bb+cc+dd)*

Step 02: Possible strings, Language and DFA for RE = a+b+c+d(ab+bb+cc+dd)* are given in the following diagram

Example 2.9: Regular Expression = aba(a+b)* + bab(a+b)*

Step 02: Possible strings, Language, and DFA for RE = aba(a+b)* + bab(a+b)*  are given in the following diagram

 

Category 3: End with Regular Expressions

These regular expressions describe patterns that match strings ending with specific sequences. Each one shows how a string can end after following certain rules or repetitions.

Sr.	Regular Expression	Simple Explanation
1	(a+b+c+d)*ab	Any mix of a, b, c, d (including empty), ending with ab.
2	(aaa+bbb)*ba	Repeats of aaa or bbb (or none), ending with ba.
3	(a+b+c)*abc	Any mix of a, b, or c (including empty), ending with abc.
4	(0+1)*101*	Any mix of 0s and 1s, followed by 10, and then any number of 1’s.
5	(a+b)*a(a+b)b	Any mix of a and b, then an aa or ab,and ending with b.
6	(00+11)*1(0+1)	Repeats of 00 or 11 (or none), followed by 1, and then either 0 or 1.

Example 3.1: Regular Expression = (a+b+c+d)*ab

Step 01:  Find the strings that can be derived from the given expression RE = (a+b+c+d)*ab. The following figure shows all possible strings that can be derived from RE = (a+b+c+d)*ab

Step 02: Possible strings, Language and DFA for RE = (a+b+c+d)*ab are given in the following diagram

Example 3.2: Regular Expression = (aaa+bbb)*ba

Step 01:  Find the strings that can be derived from the given expression RE = (aaa+bbb)*ba. The following figure shows all possible strings that can be derived from RE = (aaa+bbb)*ba

Step 02: Possible strings, Language and DFA for RE = (aaa+bbb)*ba are given in the following diagram

Example 3.3: Regular Expression = (a+b+c)*abc

Step 01:  Find the strings that can be derived from the given expression RE = (a+b+c)*abc. The following figure shows all possible strings that can be derived from RE = (a+b+c)*abc

Step 02: Possible strings, Language and DFA for RE = (a+b+c)*abc are given in the following diagram

Example 3.4: Regular Expression = (0+1)*101*

Step 01:  Find the strings that can be derived from the given expression RE = (0+1)*101*. The following figure shows all possible strings that can be derived from RE = (0+1)*101*

Step 02: Possible strings, Language and DFA for RE = (0+1)*101* are given in the following diagram

Example 3.5: Regular Expression = (a+b)*a(a+b)b

Step 01:  Find the strings that can be derived from the given expression RE = (a+b)*a(a+b)b. The following figure shows all possible strings that can be derived from RE = (a+b)*a(a+b)b

Step 02: Possible strings, Language and DFA for RE = (a+b)*a(a+b)b are given in the following diagram

Example 3.6: Regular Expression = (00+11)*1(0+1)

Step 01:  Find the strings that can be derived from the given expression RE = (00+11)*1(0+1). The following figure shows all possible strings that can be derived from RE = (00+11)*1(0+1)

Step 02: Possible strings, Language and DFA for RE = (00+11)*1(0+1) are given in the following diagram

Category 4: Start and End with Regular Expressions

These regular expressions describe patterns that match strings that start and end with specific sequences. Each one shows how a string can start and end after following certain rules or repetitions.

Example 4.1: Regular Expression = 1(1+0)*1 + 0(1+0)*0

Step 01:  Find the strings that can be derived from the given expression RE = 1(1+0)*1 + 0(1+0)*0. The following figure shows all possible strings that can be derived from RE = 1(1+0)*1 + 0(1+0)*0

Step 02: Possible strings, Language, and DFA for RE = 1(1+0)*1 + 0(1+0)*0 are given in the following diagram

Example 4.2: Regular Expression = 11(0+1)(00)

Step 01:  Find the strings that can be derived from the given expression RE = 11(0+1)(00). The following figure shows all possible strings that can be derived from RE = 11(0+1)(00)

Step 02: Possible strings, Language, and DFA for RE = 11(0+1)(00) are given in the following diagram

Example 4.3: Regular Expression = 00(11)*101

Step 01:  Find the strings that can be derived from the given expression RE =00(11)*101. The following figure shows all possible strings that can be derived from RE =00(11)*101

Step 02: Possible strings, Language, and DFA for RE =00(11)*101 are given in the following diagram

Example 4.4: Regular Expression = aba(aa+b)*ba

Step 01:  Find the strings that can be derived from the given expression RE = aba(aa+b)*ba. The following figure shows all possible strings that can be derived from RE = aba(aa+b)*ba

Step 02: Possible strings, Language, and DFA for RE = aba(aa+b)*ba are given in the following diagram

Example 4.5: Regular Expression = b*(aaa+bbb)*ba

Step 01:  Find the strings that can be derived from the given expression RE = b*(aaa+bbb)*ba. The following figure shows all possible strings that can be derived from RE = b*(aaa+bbb)*ba

Step 02: Possible strings, Language, and DFA for RE = b*(aaa+bbb)*ba are given in the following diagram

Example 4.6: Regular Expression = a(a+b)*ba+a

Step 01:  Find the strings that can be derived from the given expression RE = b*(aaa+bbb)*ba. The following figure shows all possible strings that can be derived from RE = a(a+b)*ba+a

Step 02: Possible strings, Language, and DFA for RE = a(a+b)*ba+a are given in the following diagram

Example 4.7: Regular Expression = 0+1(0+1)*10

Step 01:  Find the strings that can be derived from the given expression RE = 0+1(0+1)*10. The following figure shows all possible strings that can be derived from RE = 0+1(0+1)*10

Step 02: Possible strings, Language, and DFA for RE = 0+1(0+1)*10 are given in the following diagram

Example 4.8: Regular Expression = (11)*(0+1)(00)

Step 01:  Find the strings that can be derived from the given expression RE = (11)*(0+1)(00). The following figure shows all possible strings that can be derived from RE = (11)*(0+1)(00)

Step 02: Possible strings, Language, and DFA for RE = (11)*(0+1)(00) are given in the following diagram

Example 4.9: Regular Expression = (1)*(0+1)*(00)*

Step 01:  Find the strings that can be derived from the given expression RE = (1)*(0+1)*(00)*. The following figure shows all possible strings that can be derived from RE = (1)*(0+1)*(00)*

Step 02: Possible strings, Language, and DFA for RE = (1)*(0+1)*(00)* are given in the following diagram

Example 4.10: Regular Expression = 10(101+0+1)*1

Step 01:  Find the strings that can be derived from the given expression RE = 10(101+0+1)*1. The following figure shows all possible strings that can be derived from RE = 10(101+0+1)*1

Step 02: Possible strings, Language, and DFA for RE = 10(101+0+1)*1 are given in the following diagram

Example 4.11: Regular Expression = ac(a+b+c)*ba

Step 01:  Find the strings that can be derived from the given expression RE = ac(a+b+c)*ba. The following figure shows all possible strings that can be derived from RE = ac(a+b+c)*ba

Step 02: Possible strings, Language, and DFA for RE = ac(a+b+c)*ba are given in the following diagram

Example 4.12: Regular Expression = d(a+b+c)*bad

Step 01:  Find the strings that can be derived from the given expression RE = d(a+b+c)*bad. The following figure shows all possible strings that can be derived from RE = d(a+b+c)*bad

Step 02: Possible strings, Language, and DFA for RE = d(a+b+c)*bad are given in the following diagram

Example 4.13: Regular Expression = acd(a+b+c)*bad

Step 01:  Find the strings that can be derived from the given expression RE = acd(a+b+c)*bad . The following figure shows all possible strings that can be derived from RE = acd(a+b+c)*bad

Step 02: Possible strings, Language, and DFA for RE = acd(a+b+c)*bad are given in the following diagram

Example 4.14: Regular Expression = bb(a+b)*aa(aa+bb)

Step 01:  Find the strings that can be derived from the given expression RE = bb(a+b)*aa(aa+bb). The following figure shows all possible strings that can be derived from RE = bb(a+b)*aa(aa+bb)

Step 02: Possible strings, Language, and DFA for RE = bb(a+b)*aa(aa+bb) are given in the following diagram

Example 4.15: Regular Expression = (aa+bb)((aa)*+b)*ba

Step 01:  Find the strings that can be derived from the given expression RE = (aa+bb)((aa)*+b)*ba. The following figure shows all possible strings that can be derived from RE = (aa+bb)((aa)*+b)*ba

Step 02: Possible strings, Language, and DFA for RE = (aa+bb)((aa)*+b)*ba are given in the following diagram

Types of Regular Expressions in TOC

As we know, regular languages are either finite or infinite. So, Regular expressions can be written for both finite and infinite languages. So, types of Regular expressions are of two types

I. Finite Regular Expressions

Finite Regular expressions are used to represent the finite regular languages. So, the length of finite regular expressions is always limited.  Following are the various examples of finite regular expressions

Example 01: Write the regular expression for the language which has no string.

Solution: Language for the given example is given below

L = { } //empty string

Regular expression for the above language is given below

L(R) = Φ

Example 02: Write the regular expression for the language with a string with zero length.

Solution: Language for the given example is given below

L = { ε } //single string

Regular expression for the above language is given below

L(R) = ε

Example 03: Write the regular expression for the language with a string with a single length over ∑ = {a, b}.

Solution: Language for the given example is given below

L = { a,b } //string with single length

A regular expression for the above language is given below

L(R) = (a+b)

Example 04: Write the regular expression for the language with a string with the length of two over ∑ = {a, b}.

Solution: Language for the given example is given below

L =  (a,b).(a,b) = { aa,ab,ba,bb } //string with length of two

A regular expression for the above language is given below

L(R) = (aa+ab+ba+bb)

Example 05: Write the regular expression for the language with a string of three over ∑ = {a, b}.

Solution: Language for the given example is given below

L = (a,b).(a,b). (a,b) = { aaa,abb,aab,baa……..,bbb } //string with length of three

Regular expression for the above language is given below

L(R) = (aaa + abb + aab + baa+……..+ bbb)

Example 06: Write the regular expression for the language with strings with an at-most length of 2 over ∑ = {a, b}.

Solution: Language for the given example is given below

L = (ε,a,b).( ε,a,b) = { ε, a ,b, aa,ba……..,bb } // strings with at-most length of 2

Regular expression for the above language is given below

L(R) = (ε+a+b).( ε+a+b)

Example 07: Write the regular expression for the language with strings “Not More than two a’s and one b” over ∑ = {a, b}.

Solution: Language for the given example is given below

L = { ε, a ,b, aa,aba, aab…….. } // strings with Not More than two a’s and one b

Regular expression for the above language is given below

L(R) = { ε + a + b + aa +aba + aab+…….. }

Example 08: Write the regular expression for the finite language, which accepts all the strings, having the length exactly two over ∑ = {a, b}.

Solution: Language for the given example is given below

L = {aa, ab, ba, bb} // only 4 strings are possible for given condition

Regular expression for the above language is given below

L(R) = {aa + ab +ba+bb}

II. Infinite Regular Expressions

Infinite regular expressions are used to represent the infinite regular languages. So, the length of infinite regular expressions is always unlimited. Let explain various examples 

Example 01: Write the regular expression for the language that accepts all the strings having all combinations of a’s over ∑ = {a}.

Solution: Language for the given example is given below

L = { ε, a, aa, aaa, aaaa, aaaaa, ……….. }

A regular expression for the above language is given below

L(R) = a*

Example 02: Write the regular expression for the language that accepts all the strings having all combinations of a’s except the null string over ∑ = {a}.

Solution: Language for the given example is given below

L = {a, aa, aaa, aaaa, aaaaa, ……….. }

A regular expression for the above language is given below

L(R) = a⁺

Example 03: Write the regular expression for the language that accepts all the strings, which has any number of a’s and b’s over ∑ = {a, b}.

Solution: Language for the given example is given below

L = {a, b, ab, ba, aab, aba, aaba ……….. }

Regular expression for the above language is given below

L(R) = (a+b)*

Example 04: Write the regular expression for the language that accepts all the strings, having only one “b” and any numbers of “a” over ∑ = {a, b}.

Solution: Language for the given example is given below

L = {b, ab, aba, abaa, abaaaa, aaaaabaaaaaaa……….. } // all strings having only one “b”

Regular expression for the above language is given below

L(R) = a*ba*

Example 05: Write the regular expression for the language that accepts all the strings, which are starting with 1 and ending with 0, over ∑ = {0, 1}.

Solution: The language for the given example is given below

L = {10, 100, 11010, 1110, 1111000, ……….. } // starting with 1 and ending with 0

Regular expression for the above language is given below

L(R) = 1(0+1)*0

Example 06: Write the regular expression for the language that accepts all the strings having even length, over ∑ = {0}.

Solution: Language for the given example is given below

L = { ε, 00, 0000, 000000, 00000000, ……….. }

Regular expression for the above language is given below

L(R) = (00)*

Example 07:Write the regular expression for the language which accepts all the strings, having the first symbol should be “b” and the last symbol should be “a” over ∑ = {a, b}.

Solution: Language for given example is given below

L = {ba, baa, baba, bbaa, baaaa, babbbba……….. } // unlimited strings are possible for given condition

Regular expression for above language is given below

L(R) = b (a+b)* a

Operations on Regular Languages in Automata

There may be various operations in regular languages. Let “R” be a Regular expression over the alphabet Sigma if R is

1. If regular expression (R) is equal to Epsilon (ε), then the language of Regular expression (R) will represent the epsilon set, i.e. { ε}. A mathematical equation is given below,

2. If regular expression (R) is equal to Φ, then the language of Regular expression (R) will represent the empty set, i.e. { }. The mathematical equation is given below,

3. If regular expression (R) is equal to an input symbol “a,” which belongs to sigma, then the language of Regular expression (R) will represent the set which has “a” alphabet, i.e. {a}. A mathematical equation is given below,

4. The union of two Two Regular Expressions will always produce a regular language. Suppose R1 and R2 are two regular expressions. IF R1= a, R2=b then R1 U R2 =a+b So L(R1 U R2) = {a,b}, still string “a,b” is a regular language.

Hence, the above equation shows that {a,b} is also a regular language.

Note: The intersection of two Two Regular Expressions will always produce a regular language.

5. Concatenation of two Two Regular Expressions will always produce a regular language. IF R1= a, R2=b then R1.R2 =a.b So L(R1.R2) = {ab}, still string “ab” is a regular language

Hence, the above equation shows {ab} is also a regular language.

6. Kleene closure of Regular Expression (RE) is also a regular language

If R1 = x and (R1)* is still a regular language

• In a regular expression, x* means zero or more occurrences of x. It can generate { ε, x, xx, xxx, xxxx, …..}
• In a regular expression, x⁺means one or more occurrence of x. It can generate {x, xx, xxx, xxxx, …..}

7. If R is regular, (R) is also a regular language

Note: Only the above mentioned 7 rules are used for regular expressions. By the combination of above 7-rules more regular Expressions can be created.

Arden’s Theorem in Regular Expressions

Arden’s Theorem is used to find the regular expression of a language from a system of regular equations (usually derived from a finite automaton).

If P and Q are two Regular Expressions over Σ, and if P does not contain ε, then the following equation in R given by R = Q + RP has a unique solution i.e. R = QP*

There are two methods to prove the Arden’s Theorem, both of which are valid

Method 01: Look at the following diagram

Method 02: Look at the following diagram

Use of Regular Expressions in TOC

The main uses of regular expressions in TOC  are

• Pattern Recognition: Represent patterns that can be recognized by finite automata (DFA and NFA).
• Compiler Design: Used in lexical analysis to tokenize input strings during compilation.
• Automata Conversion: Enable conversion between regular expressions and finite automata for language recognition.
• Theoretical Analysis: Help analyze and prove properties of languages within formal language theory.

Key Points about Regular Expressions

Here are main key points about regular expressions in TOC

•  Any terminal symbol, i.e., symbols ∈ Σ, including empty and null, are regular expression.
•  The Union of two regular expressions is also a regular expression.
•  The Concatenation of two regular expressions is also a regular expression.
•  The iteration (or Closure) of a regular expression is also a regular expression.
•  The regular expressions over Σ are precisely those obtained recursively by the application of the above rules once or several times.