# Regular Expression Basics and rules in theory of automata

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 1:**

**R.E **= **a ^{+}**

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

**Explanation:** It 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 2:**

**R.E** = ** a ^{*}**

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

**Explanation:** It 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 3:**

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

**Explanation:** It can generate only one a or it can generate only one b. Nothing else.

**Strings** =** a, b**

**Rule 4:**

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

- Regular expressions for all non empty strings
- Regular expressions for all non empty strings of even length
- Regular expressions for all non empty strings of odd length

## More Examples of Regular Expression

- Regular Expression for no 0 or many triples of 0’s and many 1 in the strings.
- RegExp for strings of one or many 11 or no 11.
- Regular expressions for all non empty strings
- Regular expressions over {a, b} for all non empty strings of even length
- Regular expressions for all non empty strings of odd length
- A regular expression for ending with abb
- A regular expression for all strings having 010 or 101.
- Regular expression for Even Length Strings defined over {a,b}
- Regular Expression for strings having at least one double 0 or double 1.
- Regular Expression of starting with 0 and having multiple even 1’s or no 1.
- Regular Expression for an odd number of 0’s or an odd number of 1’s in the strings.
- Regular Expression for having strings of multiple double 1’s or null.
- Regular Expression (RE) for starting with 0 and ending with 1.
- RE for ending with b and having zero or multiple sets of aa and bb.
- A regular expression of the second last symbol is 1.
- RE for starting with 1 having zero or multiple even 1’s.
- Regular Expression for multiple a’s and multiple b’s.
- RE for exactly single 1 many 0’s |exactly single a many b.
- A regular expression for strings starting with aa and ending with ba.
- A regular expression for the language of all consecutive even length a’s.
- A regular expression for the language of all odd-length strings
- A regular expression for the language of all even length strings but ends with aa.
- A regular expression for the language of an odd number of 1s.
- A regular expression for the language of even length strings starting with a and ending with b in theory of automata.
- A regular expression for the language of all even length strings but starts with a.
- A Regular Expression for the Language of all strings with an even number of 0’s or even number of 1’s.
- A regular expression for the language of all those strings end with abb.
- A regular expression for string having must 010 or 101.
- 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. - A Regular Expression of all strings divisible by 4.
- A Regular Expression Strings that does not contain substring 110.
- Regular expressions for all strings with at least one a
- Regular expressions for all strings with at least two a’s
- Regular expressions for All strings with exactly two b
- Regular expressions for at least one a and at least one b
- Regular expression form end in a double letter (two a’s or two b’s)
- 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)*?