Automata Regular Expressions

Regular Expressions

Regular expressions are also referred as rational expressions, which are used to describe the algebraic description of regular languages. It is generally a sequence of characters that is used to find a string in language. Regular expressions play an important role in computer science applications, which involves:

  • It is used by many text editors and utilities to search block of text for certain pattern.
  • It is also used to design the compliers for programming languages.

Like other expressions, such as arithmetic expressions, logical expressions etc., regular expression also have permitted symbols and operators. Only defined symbols can be used to build a regular expression. For example:

 (a U b) a*

The regular expression has two parts:

First is (a U b) and second is a*

The symbols a and b are shorthand for sets {a} and {b}. In this (a U b) means ({a} U {b}). In this, {a, b} and {a}* means that the language consisting of all strings having any number of a’s (e.g. ?, a, aa….}.

Both expressions and parts are combined to form the value of the entire expression.

Formal Definitions Used in Regular Expression

Let R be a regular expression over alphabet ?, then:

  • ?, is a regular expression denoting by set {?}.
  • ? is a regular expression used for representing an empty set ?.
  • In regular expression, the union of any two regular expressions R1 and R2 is written as R1+ R2, which is also a regular expression denoting the set {a U b}.
  • In regular expression, the concatenation of any two regular expressions, say R1 and R2 is written as R1R2, which is also a regular expression denoting the set {ab}.
  • The closure of any regular expressions R written as R* is also a regular expression denoting the set {R*}.

Note: Do not confuse with regular expression ? and ?. The expression ? denotes the language containing only a single string, or we can say that empty string. On the other hand ? represents the language that does not contain any strings.

Operators used in Regular Expression

We have following permitted operators for building regular expressions:

  • Union
  • Concatenation (or dot)
  • Closure (or star)

Union:

The Union of two languages P and Q is denoted by P U Q, which is the set of strings that are in either P or Q or in both.

Example:

If P = {1, 2} and Q = {a, b}

P U Q = {1, 2, a, b}

Concatenation:

The Concatenation of two languages P and Q is denoted by P.Q, which is the set of strings that can be formed by taking any string in P concatenating it with any string in Q.

Example:

If P = {a, b} and Q = {?, d}

P.Q = {a, b, ad, bd}

Closure:

The closure of a language P is denoted by P*, which defines the set of those strings that can be formed by taking any number of strings from P with repetitions and concatenations of strings. 

Example:

If P = {1, 2}*

P= {?, 1, 2, 11, 22, ………..}

Precedence of Regular Expression Operators

If we are using parenthesis with regular expressions, then the evaluation of regular expression is performed on the basis of operator’s precedence. For Regular expression, the order of precedence is given below:

  • The star operator (*) has highest precedence.
  • Concatenation operator (.) has next precedence.
  • Union operator (+) has lowest precedence.

Examples of Regular Expression

Example 1:

Consider the alphabet ? = {a, b}, and describe the regular expression set for all strings having a single b.

Solution:

The regular expression will be:

R = a*ba*

Example 2:

Consider the alphabet ? = {a, b}, and describe the regular expression set for all strings having bbbb as substring.

Solution:

The regular expression will be:

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

Example 3:

Consider the alphabet ? = {a, b}, and describe the regular expression set for all strings ends with ab.

Solution:

The regular expression will be:

R = (a+b)*ab

Example 4:

Consider the alphabet ? = {a, b, c}, and describe the regular expression set for all strings, which contain no more than three b’s.

 Solution:

The regular expression will be:

R = (? +b) (? +b) (? +b)

This regular expression describes the string containing zero, one, two or three b’s and nothing else.


Related Topics

Pumping Lemma for Context Free Languages

Pumping Lemma for Context Free Languages The Pumping Lemma is made up of two words, in which, the word pumping is used to generate many input strings by pushing the symbol...

3 minutes read.

Automata Chomsky Hierarchy

Chomsky Hierarchy Formal languages: A language with precise syntax and semantics are called formal languages. Noam Chomsky has defined the Chomsky hierarchy in 1956. He is an American scientist and philosopher, and...

3 minutes read.

Automata Regular Expressions

Regular Expressions Regular expressions are also referred as rational expressions, which are used to describe the algebraic description of regular languages. It is generally a sequence of characters that is used...

3 minutes read.

Conversion of DFA to Regular expression

Conversion of DFA to Regular expression To convert the DFA to Regular Expression (RE), we are going to use a method called converting DFA to regular expression by eliminating states. This...

3 minutes read.

Automata Tutorial

What is Automata? Automata is a mathematical model and abstract model, which is used to detect string in various languages. In Automata, Regular language is recognized by Finite state AutomataContext Free language...

4 minutes read.

Automata Greibach Normal Form

Greibach Normal Form In Greibach Normal Form, there is restriction on the position, in which, terminals and variables can appear on right-hand side of production rules. In Greibach Normal Form, every...

4 minutes read.

Push down Automata Acceptance

Acceptance of Language by Push down Automata Push down Automata accepts the language, which is called context free language. Push down Automata = Finite Automata + Auxiliary Memory (Stack) Auxiliary Memory helps Push...

3 minutes read.

Closure Properties of Regular Languages -Automata

Closure Properties of Regular Languages We use the term “Closure” when we talk about sets of things. If we have two regular languages L1 and L2, and L is obtained by...

3 minutes read.

Undecidable Problem of Turing Machine

Automata Undecidable Problem of Turing Machine Undecidable problems areproblems which cannot be solved by any Turing machine. Example: Post Correspondence Problem is the type of undecidable Problem. Post Correspondence Problem Post Correspondence problem is...

7 minutes read.

Finite Automata

Finite Automata Finite state Automata or Finite State Machine is the simplest model used in Automata. Finite state automata accepts regular language. In this, the term finite means it has a...

4 minutes read.

Equivalence of Regular Grammar and Finite Automata

Equivalence of Regular Grammar and Finite Automata Regular Grammar / type -3 grammar A regular grammar or type-3 defines the language called regular language that is accepted by finite Automata.A Regular Grammar...

3 minutes read.

Chomsky's Normal Form - Automata

Chomsky's Normal Form (CNF) In context free grammar, the left-hand side of production rules contains only one variable, and right side may contain any number of variables or terminals in production...

4 minutes read.

Simplification of Context Free Grammar - Automata

Simplification of Context Free Grammar Context Free Grammar has recursive structure. The languages that are accepted with Context Free Grammar are called Context Free Languages. Context Free Grammar has one condition...

3 minutes read.

Ambiguity in Context Free Grammar - Automata

Ambiguity in Context Free Grammar? Context Free Grammar Context Free Grammar has one condition for production rules, which is, on the left-hand side of each rule, there must be only single variable,...

4 minutes read.

Finite Automata with Output

Finite Automata with Output The Finite State machine is similar to Finite Automata, except that it has the additional capacity of producing output. Finite State machine = Finite Automata + Output Capabilities Types...

3 minutes read.

Recursive Language and Recursive Enumerable Language

Recursive Language and Recursive Enumerable Language Before discussing Recursive language and Recursive Enumerable language, let us see what Turing machine responds for some input string. If we have the Turing machine T...

4 minutes read.

Context Free Grammar - Automata

Context Free Grammar Grammar defines a set of rules, and with the help of these rules valid sentences in a language are constructed. A grammar consists of collection of substitution rules,...

3 minutes read.

Minimization of Finite Automata

Minimization of Finite Automata The term minimization refers to the construction of finite automata with a minimum number of states, which is equivalent to the given finite automata. The number of...

4 minutes read.

Pumping Lemma for Regular Languages - Automata

Pumping Lemma for Regular Languages The language accepted by the finite automata is called Regular Language. If we are given a language L and asked whether it is regular or not?...

4 minutes read.

Converting Finite Automata to Regular Expression using Arden’s Theorem

Converting Finite Automata to Regular Expression using Arden’s Theorem The Arden’s Theorem can be applied to find the regular expression recognized by the given transition diagram. This theorem can be applied...

4 minutes read.