Example of Regular Expression

Ex. 6:
Find a regular expression corresponding to the language of all strings over the alphabet { a, b } that contain no more than one occurence of the string aa.

Solution:
If there is one substring aa in a string of the language, then that aa can be followed by any number of b. If an a comes after that aa, then that a must be preceded by b because otherwise there are two occurences of aa. Hence any string that follows aa is represented by ( b + ba )*. On the other hand if an a precedes the aa, then it must be followed by b. Hence a string preceding the aa can be represented by ( b + ab )*. Hence if a string of the language contains aa then it corresponds to the regular expression ( b + ab )*aa( b + ba )* .

If there is no aa but at least one a exists in a string of the language, then applying the same argument as for aa to a, ( b + ab )*a( b + ba )* is obtained as a regular expression corresponding to such strings.

If there may not be any a in a string of the language, then applying the same argument as for aa to , ( b + ab )*( b + ba )* is obtained as a regular expression corresponding to such strings.
Altogether ( b + ab )*( + a + aa )( b + ba )* is a regular expression for the language.

More examples

Ex. 5:
Describe as simply as possible in English the language corresponding to the regular expression (( a + b )3)*( #+ a + b ) .

Solution:
(( a + b )3) represents the strings of length 3. Hence (( a + b )3)* represents the strings of length a multiple of 3. Since (( a + b )3)*( a + b ) represents the strings of length 3n + 1, where n is a natural number, the given regular expression represents the strings of length 3n and 3n + 1, where n is a natural number.

More examples

Ex. 4:
Describe as simply as possible in English the language corresponding to the regular expression a*b(a*ba*b)*a* .

Solution:
A string in the language can start and end with a or b, it has at least one b, and after the first b all the b's in the string appear in pairs. Any numbe of a's can appear any place in the string. Thus simply put, it is the set of strings over the alphabet { a, b } that contain an odd number of b's.
We will continue examples in next post..

Examples of Regular Grammars and Regular Expressions

Ex. 2:
Find a regular expression corresponding to the language of all strings over the alphabet { a, b } that contain exactly two a's.

Solution:
A string in this language must have at least two a's. Since any string of b's can be placed in front of the first a, behind the second a and between the two a's, and since an arbitrasry string of b's can be represented by the regular expression b*, b*a b*a b* is a regular expression for this language.


Ex. 3:
Find a regular expression corresponding to the language of all strings over the alphabet { a, b } that do not end with ab.

Solution:
Any string in a language over { a , b } must end in a or b. Hence if a string does not end with ab then it ends with a or if it ends with b the last b must be preceded by a symbol b. Since it can have any string in front of the last a or bb, ( a + b )*( a + bb ) is a regular expression for the language

Formal Definition of Regular Grammar:

Regular Grammar and Regular Expressions are different.

We have discussed Regular expressions. Let’s see Regular Grammar.

Formal Definition of Regular Grammar:

In Computer Science, a right regular grammar is a formal grammar (N, Σ, P, S) such that all the production rules in P are of one of the following forms:
1. A → a - where A is a non-terminal in N and a is a terminal in Σ
2. A → aB - where A and B are in N and a is in Σ
3. A → ε - where A is in N and ε denotes the empty string, i.e. the string of length 0.

Formal Definition of Regular expression:

Regular expressions can be expressed in terms of formal Language Theory, Regular expressions consist of constants and operators that denote sets of strings and operations over these sets, respectively. Given a finite alphabet Σ the following constants are defined:

(empty set) ∅ denoting the set ∅
(empty string) ε denoting the set {ε}
(Literal character ) a in Σ denoting the set {a}
and the following operations:
(concatenation) RS denoting the set { αβ | α in R and β in S }. For example {"ab", "c"}{"d", "ef"} = {"abd", "abef", "cd", "cef"}.
(alternation) R|S denoting the set union of R and S.
(Kleene Star )R* denoting the smallest superset of R that contains ε and is closed under string concatenation. This is the set of all strings that can be made by concatenating zero or more strings in R. For example, {"ab", "c"}* = {ε, "ab", "c", "abab", "abc", "cab", "cc", "ababab", ... }.
The above constants and operators form a Kleene Algebra.

Many textbooks use the symbols ∪, +, or ∨ for alternation instead of the vertical bar.To avoid brackets it is assumed that the Kleene star has the highest priority, then concatenation and then set union. If there is no ambiguity then brackets may be omitted. For example, (ab)c is written as abc and a|(b(c*)) can be written as a|bc*.
After this we will discuss formal definition of Regular Grammar.

Automata Step by Step

Today, we will discuss “Regular expressions”.

Regular expressions:

A regular expression (also "RegEx" or "regex”) is a string that is used to describe or match a set of strings, according to certain syntax rules. The specific syntax rules vary depending on the specific implementation, programming language, or library in use. Additionally, the functionality of regex implementations can vary between versions

In another words, a regular expression, often called a pattern, is an expression that describes a set of strings. They are usually used to give a concise description of a set, without having to list all elements. For example, the set containing the three strings Handel, Händel, and Haendel can be described by the pattern "H(ä|ae?)ndel" (or alternatively, it is said that the pattern matches each of the three strings). In most formalism, if there is any regex that matches a particular set then there are an infinite number of such expressions.