Results 1 to 9 of 9

Math Help - Closure relations on a language?

  1. #1
    Newbie
    Joined
    Sep 2011
    Posts
    17

    Closure relations on a language?

    Hi, I'm having a little trouble understand the idea of closure as so many places seem to describe it differently.

    I'm working on an example problem that states "L* is the closure of language L under which relations?"

    From what I gather, for a language to be closed over a relation, it means that applying that relation to any of its elements results in an element that is also in the language. Is this a correct understanding of the term?

    Applying this knowledge to that question, I would think the answers are:
    Union: L U L is in L*
    Concatenation: LL is in L*
    Kleene Star: L* is in L*

    Is this line of reasoning correct, or am I totally missing the mark? Thanks in advance.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785

    Re: Closure relations on a language?

    Quote Originally Posted by LostProjectile View Post
    From what I gather, for a language to be closed over a relation, it means that applying that relation to any of its elements results in an element that is also in the language. Is this a correct understanding of the term?
    Yes. More precisely, consider the definition from "Elements of the Theory of Computation," 2nd edition, by Lewis and Papadimitriou, p. 37:

    Let D be a set, let n\ge 0 and let R\subseteq R^{n+1} be a (n+1)-ary relation on D. Then a subset B of D is said to be closed under R if b_{n+1}\in B whenever b_1,\dots,b_n\in B and (b_1,\dots,b_n,b_{n+1})\in R.
    So, for a set B to be closed under R, the relation R has to be on the superset of B. In particular, if L' is the closure of L under R, R is a relation on words.

    Quote Originally Posted by LostProjectile View Post
    Applying this knowledge to that question, I would think the answers are:
    Union: L U L is in L*
    Union is a ternary relation on languages, not on words.

    Quote Originally Posted by LostProjectile View Post
    Concatenation: LL is in L*
    Yes, when concatenation is considered on words, not languages. In fact, L* is defined as the closure of L under concatenation (plus the empty string).

    Quote Originally Posted by LostProjectile View Post
    Kleene Star: L* is in L*
    Again, (M, M*) is a binary relation on languages.
    Last edited by emakarov; September 8th 2011 at 01:03 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4

    Re: Closure relations on a language?

    The poster should

    precisely define, for his own edification

    S is closed under R

    and

    X is the closure of S under R

    and then

    state more precisely the exact mathematical question that is being being asked.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Sep 2011
    Posts
    17

    Re: Closure relations on a language?

    Sorry if my post was confusing. I am actually using "Elements of the Theory of Computation" by Lewis and Papadimitriou, and I'm talking about problem 1.7.7 on page 46. My professor gave this as a problem we should practice to prepare for an upcoming quiz and I guess my issue is I don't really comprehend the question. I'm confused about what relations I'm working with and find the description of closure fuzzy.

    Thank you for your responses.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4

    Re: Closure relations on a language?

    Please post the question just as it appears in your text.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Sep 2011
    Posts
    17

    Re: Closure relations on a language?

    1.7.7. The Kleene star of a language L is the closure of L under which relations?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4

    Re: Closure relations on a language?

    The Kleene star L* of L is the closure of L under concatenation.

    (Here L is some set of symbols.)

    That's by the definition of 'the Kleene star'.

    But what OTHER relations might L* be the closure of from L?

    So, not having other context (I don't have that book) I would think the question would be better worded:

    Name a relation R such that L* is the closure of L under R. And an obvious answer is: concatenation.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785

    Re: Closure relations on a language?

    Actually, now that I think about it, L* is the closure of L under two relations. I believe the problem is not to give several alternative examples of relations that produce L* from L, but to give the relations that can serve to define L* in the most natural way.

    So, if L is a language in the alphabet \Sigma, then L* is the closure of L under

    R_1=\{(u,v,uv)\mid u,v\in\Sigma^*\}

    and

    R_2=\{(e)\} ( e is the empty string).

    The relation R_1 is an infinite ternary relation, and R_2 is a finite unary relation. By the definition 1.6.3 from the book, which is given in post #2, some language L' is closed under R_1 if uv\in L' whenever u,v\in L'. Also, L' is closed under R_2 if e\in L' since here n = 0 and the assumption b_1,\ldots,b_n\in B from the definition is vacuously true. So, L* is the smallest set containing L and closed under R_1 and R_2. In contrast, L+ is the closure of L under just R_1.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Newbie
    Joined
    Sep 2011
    Posts
    17

    Re: Closure relations on a language?

    That explanation just made it click for me. Thank you so much!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Relations and Functions - Inverse Relations Question
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 13th 2011, 01:20 PM
  2. Replies: 1
    Last Post: September 19th 2011, 02:09 PM
  3. Relation between topological closure and algebraic closure
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: November 4th 2010, 03:45 PM
  4. Replies: 6
    Last Post: February 11th 2009, 01:56 PM

Search Tags


/mathhelpforum @mathhelpforum