Re: Languages' reflexivity and transitivity and Kleene closure

From: Hans Hüttel (hans_at_cs.auc.dk)
Date: 07/13/04 

Date: Tue, 13 Jul 2004 09:10:18 +0200

ZZambia wrote:
> Hans Hüttel <hans@cs.auc.dk> wrote in message news:<40f1b86b$0$212$ba624c82@nntp04.dk.telia.net>...
>
>>ZZambia wrote:
>>
>>
>>>Please help me in solving this formal exercise:
>>>
>>>The language X is defined over S* (S alphabet)
>>>
>>>Well, X is said to be "transitive" if X^2 is contained in X
>>>Also, X is said to be "reflexive" if E (empty word) is contained in X.
>>>
>>>Now, we want do explain why for every language L defined over S*, L*
>>>(the Kleene closure of L) is the smallest transitive and reflexive
>>>language that contains L.
>>>(Namely, by contruction L is included properly in L*)
>>>
>>>To do so, we must demonstrate both (1) and (2):
>>>
>>>(1) L* is reflexive and transitive.
>>>
>>>(2) if L is included in Y, then also L* is included in Y, for every
>>>regular set Y proven to be reflexive and transitive.
>>>
>>>Any suggestion welcome in solving (1) and (2) given the previous
>>>facts.
>>
>>As I always tell my students: Go back to the definitions and see how
>>they can help you! In this case, this means applying the definitions of
>>transitivity and reflexivity that you yourself have presented above.
>>
>>Hans
>
>
>
> Thank you for your reply Hans, but to be more specific, I already used
> he defs. I rewrote in the head of message to resolve (1) (obviously,
> L* contains E and L^2, and so it's reflexive and transitive).
>
> My doubt is centered in demonstration of (2). I tried to do the
> following sequence:
>
> a) as we know X reflexive and transitive, and L is contained in X,
> then also L^2 is in X (elements of L are also elements of X, and we
> can use tranisitivity to assert what we asserted);
>
> b) L^2 may be expressed as LL and so LL is contained in X;
>
> c) if LL is contained in X, also (LL)^2 is contained in X, for the
> reason we expressed in (a);
>
> d) repeating steps (b) and (c) "i" times we get that (LL)^(2*i) is
> contained in X, demonstrating that every odd concatenation of L is in
> X ì, plus L itself by hypotesis;
>
> e) L* if the set of L^i plus E ... and is formed by even and odd
> concatenation of L. How to continue (if the above is correct) ???

One word: Induction.

Hans

Relevant Pages

  • Re: Languages reflexivity and transitivity and Kleene closure
    ... >> regular set Y proven to be reflexive and transitive. ... > transitivity and reflexivity that you yourself have presented above. ... demonstrating that every odd concatenation of L is in ...
    (comp.theory)
  • Re: Equivalence relations and "is a sibling of"
    ... error lies in thinking that the relation "is a sibling of" and the ... I never touched on the question of transitivity. ... with reflexivity, and you were wrong to claim that "is a sibling of" ... xy and x suffers disease D and y suffers disease D ...
    (sci.math)
  • Re: Languages reflexivity and transitivity and Kleene closure
    ... > The language X is defined over S* ... > (the Kleene closure of L) is the smallest transitive and reflexive ... transitivity and reflexivity that you yourself have presented above. ...
    (comp.theory)
  • Testing for the equivalence relation
    ... an equivalence relation (ie. it implies reflexivity - in contrast to ... Reflexivity of the relation is implied because ... If x R y and y R x, then x R x (by the definition of transitivity), ...
    (comp.databases.theory)