Test 3 Q3 review - Problem Solving

Below is the last question in test 3 i did hours ago. I wrote down the proof briefly which may not be that convincible, so i decide to prove it again.

Prove L(1*(0+e)1*(0+e)1*) = L2, the language has at most two zeros.

To prove the equivalence, we actually prove that for any element x , it can be represented by
L(1*(0+e)1*(0+e)1*) or L2. The former one looks a little bit complicated but actually it is possible to simplify it to make the proof much easier and shorter. By applying the distributivity, the transformation is going to be like:
L(1*(0+e)1*(0+e)1*) <=> L((1*0+1*e)(1*0+1*e)1*) , apply identity and annihilator for concatenation here, we get L((0+1*)(0+1*)1*), then apply idempotence of Kleene star, the simplest form is L((0+1*)(0+1*)).
Now, we are really just proving L((0+1*)(0+1*)) = L2.

In first part, we prove L((0+1*)(0+1*)) is a subset of L2.
L2 tells us how we rewrite L((0+1*)(0+1*)), that is to say, the number of zero is crucial.
It's definitely true by just looking at L((0+1*)(0+1*)), but we need demonstrate it with stronger reason. All cases include zero-free, one zero and two zeros. (0+1*) has either one zero or repetition of 1 or e. Then the concatenation of two (0+1*) has two zeros at most which satisfies L2. Then x \in L((0+1*)(0+1*)) implies x \in L2.

In second part, we prove L2 is a subset of L((0+1*)(0+1*)).
In this part, the setting for the typical elemtent x depends on L((0+1*)(0+1*)).
Since there are at most two zeros, i don't think there are too much things to worry about.
We just ensure x can be zero-free or with one zero or with two zeros.
x = (0+1/e/1*)(0+1/e/1*), (0+1*) is satisfying the language L((0+1*)(0+1*)) here.
Hence, the proof is done.

For such questions, once the languages on both sides are well understood, the proof will be just following the formal procedure.

Chapter Seven Review

#############
Formal Language:
#############
Any set of strings can be empty, finite, or infinite.
Length of string: s, number of symbols in s, ex: "+"=1, "e"=0.

#############
Regular Expressions(Regex):
#############
Basis : empty, empty string, one-symbol character;
Kleene star can be used to restrict the pattern of a regex:
even or odd numbers of some characters;
Idempotence of Kleene star: R** = R*
Distributivity: (A(B+C)) = (AB+AC), ((B+C)A) = (BA + BC)

Proving equality of two languages => Prove mutual inclusion:
1. Analyze the pattern of a language and divide into pieces if possible;
2. Transformations: in general case, expand some terms to make up the equality;
3. Check from both directions, conclusion.

###
FSA
###
Proof procedure, induction:
Basis: x=e, &*(q_e,x)=q_e. P(e) true.
Induction Step: Assume x = x'a, assume P(x'). Analyze the cases.
In all cases, x = x'a and &*(s,x) = &*(q_e,x'a)=&(&*(q_e,x'),a)
according to our induction hypothesis.
Then using the transistions functions, we prove P(x') => P(x), in all cases.

####
NFSA
####
Difference: Each transition takes the machine to a subset of states rather than a unique
state.

Notes:
Every regex has equivalent NFSA.
Every NFSA has equivalent DFSA.