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.
No comments:
Post a Comment