Skip to content

Lecture No. 03

Dated: 25-10-2024

Regular Expression

Imagine we have

\[\Sigma = \{a\}\]
\[L = \{a, aa, aaa, \ldots\}\]

We know that it is represented by \(\Sigma^+\).
Then \(a^+\) would be called the regular expression.

Recursive Definition of Regular Expression

  1. Every letter of \(\Sigma\), including \(\Lambda\) is a regular expression.

  2. If \(r_1\) and \(r_2\) are regular expressions then following are also regular expressions.

    1. \[r_1\]
    2. \[r_1 r_2\]
    3. \[r_1 + r_2\]
    4. \[r_1^*\]

  3. Nothing else is regular expression.

A language maybe be generated by more than one regular expressions

Examples

Imagine we have \(\Sigma = \{a, b\}\) then

Example

A language \(L\) consisting of all combinations of symbols is defined as \((a + b)^*\).
The \((a + b)\) represents a single letter which can be either \(a\) or \(b\).

Example

A language containing at least 1 \(a\) symbol in each string1 is defined as \(b^*ab^*\).

Example

A language containing strings1 of even length is defined as \(((a + b) (a + b))^*\)

References

  1. Read more about strings. ↩↩