Processing math: 100%
Close
Close Window

Formal Languages With Visualizations

Chapter 5 Identifying Non-regular Languages

Show Source |    | About   «  5.1. Identifying Non-regular Languages   ::   Contents   ::   6.1. Context-Free Languages  »

5.2. Properties

5.2.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 one 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.

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

Example 2: Consider Σ={a,b}, L={wΣw has an even number of as and an even number of bs}

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

R1awb(L)={wΣw has an odd number of as and an odd number of bs}

Proof:

Problem 1 proof

Figure 5.2.1: Problem 1 proof

5.2.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.

TruncPreb(L)={aaab,aa}

Example 2: Consider L={(bba)nn>0}

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

Note

List out possible strings in the language

TruncPreb(L)={a(bba)nn0}

Proof:

Problem 2 proof

Figure 5.2.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.

   «  5.1. Identifying Non-regular Languages   ::   Contents   ::   6.1. Context-Free Languages  »

nsf
Close Window