Regular languages and regular expressions

Difficulty

Easy 25%

Contents

Regular languages and regular expressions

There are two types of regular expressions.

We recall that a grammar G1 = (T, N, S, R) is a right regular expression if the rules of R are of the form: A → aB or A → a with A, B ∈ N and a ∈ T.

Recall that a grammar G2 = (T, N, S, R) is a left-hand regular expression if the rules of R are of the form: A → Ba or A → a with A, B ∈ N and a ∈ T .

A language is regular or rational if and only if there exists a regular grammar generating this language.

The advantage of distinguishing regular grammars on the right or on the left appears during the analysis: if we read the symbols of the word to be analyzed from left to right, then

a regular right-hand grammar will be used for a top-down analysis, from the axiom to the word
a regular left-hand grammar will be used for a bottom-up analysis, from the word to the axiom.

For example, to analyze the word aaabb with the grammar G1, we will construct the derivation S1 ⇒ aS1 ⇒ aaS1 ⇒ aaaU1 ⇒ aaabU1 ⇒ aaabb; while to analyze this word with the G2 grammar, we will construct the derivation aaabb ⇐ U2aabb ⇐ U2abb ⇐ U2bb ⇐ S2b ⇐ S2.

Language and expression

An expression E is a regular expression on an alphabet A if and only if:

E = ∅ or
E = ε or
E = a with a ∈ A or
E = E1 | E2 and E1 and E2 are two regular expressions on A or
E = E1.E2 and E1 and E2 are two regular expressions on A or
E = E^∗₁ summer₁ is a regular expression on A

The operators ∗,. and | have decreasing priority. If necessary, parentheses can be added.

The language L (E) described by a regular expression E defined on an alphabet A is defined by

L (E) = ∅ if E = ∅,
L (E) = {ε} if E = ε,
L (E) = {a} if E = a,
L (E) = L (E1) ∪ L (E2) if E = E1 | E2,
L (E) = L (E1) .L (E2) if E = E1.E2,
L (E) = L (E1)^∗ if E = E^∗₁ summer₁ is a regular expression on A.

The equivalence between regular expressions and regular languages is established by the following two implications:

Any regular expression describes a regular language.
Any regular language can be described by a regular expression.

Trivial equivalence list:

Regular languages and regular expressions

Language and expression

Process of creating an automaton from a regular expression