Re: Languages' reflexivity and transitivity and Kleene closure

From: ZZambia (mvigliar_at_infinito.it)
Date: 07/12/04 

Date: 12 Jul 2004 01:34:26 -0700

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) ???

Thank you,
ZZambia

Relevant Pages

  • Re: Languages reflexivity and transitivity and Kleene closure
    ... >>transitivity and reflexivity that you yourself have presented above. ... > can use tranisitivity to assert what we asserted); ... 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)