Thread: Closure relations on a language?

1. 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.

2. Re: Closure relations on a language?

Originally Posted by LostProjectile
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.

Originally Posted by LostProjectile
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.

Originally Posted by LostProjectile
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).

Originally Posted by LostProjectile
Kleene Star: L* is in L*
Again, (M, M*) is a binary relation on languages.

3. 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.

4. 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.

5. Re: Closure relations on a language?

Please post the question just as it appears in your text.

6. Re: Closure relations on a language?

1.7.7. The Kleene star of a language L is the closure of L under which relations?

7. 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.

8. 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$.

9. Re: Closure relations on a language?

That explanation just made it click for me. Thank you so much!