1. Properties and Proving: Problem 1¶

Consider the property Replace_one_a_with_b or R1awb for short. If \(L\) is regular, prove that R1awb(\(L\)) is regular.

The property R1awb applied to a language \(L\) replaces one \(a\) in each string with a \(b\). If a string does not have an \(a\), then the string is not in R1awb(\(L\)).

What does this mean? What are we trying to prove?

Example 1: Consider \(L = \{aaab, bbaa\}\)

IS \(L\) REGULAR? YES, you can apply the property.

\(\mathrm{R1awb}(L) = \{baab, abab, aabb, bbba, bbab\}\)

Example 2: Consider \(\Sigma=\{a, b\}\), \(L = \{w \in \Sigma^{*} \mid w \mathrm{\ has\ an\ even\ number\ of\ } a's \mathrm{\ and\ an\ even\ number\ of\ } b's \}\)

Is \(L\) regular? YES, How do you know? We built a DFA for this language.

\(\mathrm{R1awb}(L) = \{w \in \Sigma^{*} \mid w \mathrm{\ has\ an\ odd\ number\ of\ } a's \mathrm{\ and\ an\ odd\ number\ of\ } b's\}\)

Proof:

Figure 1: Problem 1 proof

2. Properties and Proving - Problem 2¶

Consider the property Truncate_all_preceeding_b's or TruncPreb for short. If \(L\) is regular, prove TruncPreb(\(L\)) is regular.

The property TruncPreb applied to a language \(L\) removes all preceeding b's in each string. If a string does not have an preceeding b, then the string is the same in TruncPreb(\(L\)).

What does this mean? What are we trying to prove?

Example 1: Consider \(L = \{aaab, bbaa\}\)

IS \(L\) REGULAR? YES, you can apply the property.

\(\mathrm{TruncPreb}(L) = \{aaab, aa\}\)

Example 2: Consider \(L = \{(bba)^n \mid n > 0\}\)

Is \(L\) regular? YES. How do you know? We built a DFA for this language.

\(\mathrm{TruncPreb}(L)= \{a(bba)^n \mid n \ge 0\}\)

Proof:

Figure 2: Problem 2 proof

Make a copy of the DFA. For each a arc in the first copy, remove it and instead have the \(a\) arc go to the corresponding destination below.

For each \(b\) arc in the first copy, change the \(b\) to lambda.