Analysing Regular Expressions
Only the first couple examples are included in these notes. See the lecture video for additional examples of regular expressions and their languages.
Examples
For the alphabet:
\[\Sigma=\\{0,1\\}\]-
0 followed by any nmber of 1s:
\[01^* = 0(1^*) = \{0, 01, 011, 0111, \ldots\}\] -
0 followed by any number of 1s then 01:
\[(01^*)(01) = \{ 001, 0101,01101,011101,\ldots\}\] -
Strings of length 1:
\[0+1=\{0,1\}\] -
All strings in the alphabet:
\[(0+1)^*=\{\epsilon,0,1,00,01,10,11,\ldots\}\] -
Any string that ends with 010:
\[(0+1)^*010\] -
Any string that contains that pattern 01:
\[(0+1)^*01(0+1)^*\]
Complex Example
Consider the following regular expression:
\[((0+1)(0+1))^*+((0+1)(0+1)(0+1))^*\]We can split it into the following fundamental parts:
-
Strings of even length:
\[((0+1)(0+1))^*\]This is as it is any number of strings of length 2.
-
Strings of length a multiple of 3:
\[((0+1)(0+1)(0+1))^*\]This is because is is any number of string of length 3.
The $+$ operator combines these two languages and as such the definition is:
All strings whose length is even or a multiple of 3.