9/14 - Regular Expressions 2.7

Question 1

Def. 1

Answer 1

the class of languages that can be described by regular expressions coincides with the class of regular languages.

Question 2

formal (and inductive) definition of regular

expressions :

Answer 2

Let Σ be a non-empty alphabet.
1. Ee is a regular expression.
2. ∅ is a regular expression.
3. For each a ∈ Σ, a is a regular expression.
4. If R_1 and R_2 are regular expressions, then R_1 ∪ R_2 is a regular expression.
5. If R_1 and R_2 are regular expressions, then R_1R_2 is a regular expression.
6. If R is a regular expression, then R^∗ is a regular expression.
You can regard 1., 2., and 3. as being the “building blocks” of regular expressions. Items 4., 5., and 6. give rules that can be used to combine regular expressions into new (and “larger”) regular expressions.

Question 3

Definition 2.7.2

Answer 3

Let Σ be a non-empty alphabet.

1. The regular expression Ee describes the language {Ee}.
2. The regular expression ∅ describes the language ∅.
3. For each a ∈ Σ, the regular expression a describes the language {a}.
4. Let R_1 and R_2 be regular expressions and let L_1 and L_2 be the languages described by them, respectively. The regular expression R_1 ∪ R_2 describes the language L_1 ∪ L_2.
5. Let R_1 and R_2 be regular expressions and let L_1 and L_2 be the languages described by them, respectively. The regular expression R_1R_2 describes the language L_1L_2.
6. Let R be a regular expression and let L be the language described by it. The regular expression R^∗ describes the language L^∗.

Question 4

Definition 2.7.3

Answer 4

Let R_1 and R_2 be regular expressions and let L_1 and L_2 be the languages described by them, respectively. If L_1 = L_2 (i.e., R_1 and R_2 describe the same language), then we will write R_1 = R_2.
Hence, even though (0 ∪ Ee)1^∗ and 01^∗ ∪ 1^∗, are different regular expressions, we write
(0 ∪ Ee)1^∗ = 01^∗ ∪ 1^∗,
because they describe the same language.

Question 5

Theorem 2.7.4 Let R1, R2, and R3 be regular expressions. The following identities hold:

Answer 5

Let R1, R2, and R3 be regular expressions. The following identities hold:
1. R1∅ = ∅R1 = ∅.
2. R1(Ee) = (Ee)R1 = R1.
3. R1 ∪ ∅ = ∅ ∪ R1 = R1.
4. R1 ∪ R1 = R1.
5. R1 ∪ R2 = R2 ∪ R1.
6. R1(R2 ∪ R3) = R1R2 ∪ R1R3
7. (R1 ∪ R2)R3 = R1R3 ∪ R2R3. 8. R1(R2R3) = (R1R2)R3.
9. ∅∗ = Ee.
10. Ee∗ = Ee.
1 1 . ( Ee ∪ R 1 ) ∗ = R 1∗ .
1 2 . ( Ee ∪ R 1 ) ( Ee ∪ R 1 ) ∗ = R 1∗ .
1 3 . R 1∗ ( Ee ∪ R 1 ) = ( Ee ∪ R 1 ) R 1∗ = R 1∗ .
14. R1∗R2 ∪ R2 = R1∗R2.
15. R1(R2R1)∗ = (R1R2)∗R1.
16. (R1 ∪ R2)∗ = (R1∗R2)∗R1∗ = (R2∗R1)∗R2∗.

Question 6

Show (0 ∪ 1)^∗101(0 ∪ 1)^∗ is a regular expression using
Let Σ be a non-empty alphabet.
1. Ee is a regular expression.
2. ∅ is a regular expression.
3. For each a ∈ Σ, a is a regular expression.
4. If R_1 and R_2 are regular expressions, then R_1 ∪ R_2 is a regular expression.
5. If R_1 and R_2 are regular expressions, then R_1R_2 is a regular expression.
6. If R is a regular expression, then R^∗ is a regular expression.

Answer 6

By 3., 0 is a regular expression.
By 3., 1 is a regular expression.
Since 0 and 1 are regular expressions, by 4., 0∪1 is a regular expression.
Since 0∪1 is a regular expression, by 6., (0∪1)^∗ is a regular expression.
Since 1 and 0 are regular expressions, by 5., 10 is a regular expression.
Since 10 and 1 are regular expressions, by 5., 101 is a regular expression.
Since (0 ∪ 1)^∗ and 101 are regular expressions, by 5., (0 ∪ 1)^∗101 is a regular expression.
Since (0 ∪ 1)^∗101 and (0 ∪ 1)^∗ are regular expressions, by 5., (0 ∪ 1)^∗101(0 ∪ 1)^∗ is a regular expression.