9/17, 9/19 - Regular Expressions and Finite Automata 2.8

Question 1

Theorem 2.8.1

Answer 1

Let L be a language. Then L is regular if and only if there exists a regular expression that describes L. (knowing the proof to this is important)

Question 2

Lemma 2.8.2

Answer 2

Let Σ be an alphabet, and let B, C, and L be languages in
Σ^∗ such that Ee ̸∈ B and 
L = BL ∪ C. 
Then,
L = B^∗C.

Question 3

Lemma 2.8.3

Answer 3

Let n≥1 be an integer and, for 1 ≤ i ≤ n and 1 ≤ j ≤ n, let B_ij and C_i be regular expressions such that Ee ̸∈ B_ij. Let L_1, L_2, … ,L_n be languages that satisfy
L_i = (^nU_j=1 B_ijL_j) ∪ C_i for 1 ≤ i ≤ n.
Then L1 can be expressed as a regular expression only involving the regular
expressions B_ij and C_i.

Question 4

Two parts of proving “Let L be a language. Then L is regular if and only if there exists a regular expression that describes L.”

Answer 4

• In Section 2.8.1, we will prove that every regular expression describes a regular language.
• In Section 2.8.2, we will prove that every DFA M can be converted to a regular expression that describes the language L(M).

These two results will prove Theorem 2.8.1.

Question 5

For L = BL ∪ C.

Answer 5

This process hopefully convinces you that any string u in L can be written as the concatenation of zero or more strings in B, followed by one string in C. In fact, L consists of exactly those strings having this property:
Let Σ be an alphabet, and let B, C, and L be languages in
Σ^∗ such that Ee ̸∈ B and Then
L = BL ∪ C. L = B^∗C.