Re: Languages' reflexivity and transitivity and Kleene closure

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

  • Next message: Abi: "Re: complexity of the subgroup problem in free groups" 
    Date: Mon, 12 Jul 2004 00:00:03 +0200

    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

  • Next message: Abi: "Re: complexity of the subgroup problem in free groups"

    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: 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)
    • 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)
    • Re: Socrates and the Liar
      ... Wittgenstein, the statement avoids paradox, OR, the statement refers ... But reflexivity can also be an object property, ... When an observer sees a flow of coordinations of coordinations of behavior through the coordinations of coordinations of doings on the body of languaging beings, then he or she can claim that the beings are beginning to operate in a domain of awareness of parts of their own body. ... The body, and self, arise in language in the same manner as any other object arises in language. ...
      (sci.logic)