# How to determine if a regular language L* exists

I'm trying to make sense of regular languages, operations on them, and Kleene operations.

Let's say I define a language with the alphabet {x, y}. Let's further say that I place the restriction that there can be no string in the language that contains the substring 'xx'. Thus, my language could be expressed as L = {y, xy, yx}, since that language conforms to the definition.

Could I then argue that there is no language L* since L* could contain LL? That is, can a particular but arbitrarily chosen finite language that conforms to the definition exist, but since LL can't be in L*, L* cannot exist? Or must any L necessarily omit anything preventing L* from existing?

• Saying "L^*" does not exist makes not sense. It does exist, by definition. The question is: what properties does it have? – Raphael Jan 28 '16 at 18:24

Your confusion seems to stem from the incorrect assumption that if a language $L$ has a certain property, then $L^*$ must also have that property. Consider this simpler example. Over the 1-symbol alphabet $\{a\}$ consider the property

$L$ contains no words of length more than three

Then one language with this property is $L=\{a, aaa\}$. Then by the definition of the $^*$ operator \begin{align} L^*&=\{\epsilon\}\cup L\cup LL\cup LLL \cup\dotsm\\ &=\{\epsilon\}\cup\{a, aaa\}\cup\{aa,aaaa, aaaaaa\}\cup\dotsm\\ &=\{\epsilon,a,aa,aaa,aaaa,aaaaa,aaaaaa,\dotsc\} \end{align} In other words, given this $L$, $L^*$ consists of all finite strings of $a$s, which certainly doesn't have the property that $L$ did.

Now of course there are some properties of a language $L$ which are shared by $L^*$: being regular is one such, consisting of just the empty string is another, and consisting of only even-length strings is yet another.

• Ok, that makes a lot of sense. So just because one language L has said property doesn't restrict any other language L' (or whatever) that's in L* from having another completely different property or restriction. That also clears up why L* always exists. – Chris F. Jan 28 '16 at 3:50

$L^*$ always exists. ${}^*$ is an operation on languages, just like ${}^2$ is an operation on numbers – whenever you have a number $x$, there is a number $x^2$ and, similarly, whenever you have a language $L$, there is a language $L^*$. Specifically, $L^*$ is the language of all strings that can be made by concatenating zero or more strings from $L$. That's well-defined for any language $L$.

What you've observed is that $L^*$ might have different properties from $L$. If we take your example of $L = \{y,yx,xy\}$, we see that no string in $L$ has $xx$ as a substring ($L$ is not the only language with this property but that's beside the point). On the other hand, $L^*$ includes the string $yxxy$, which does have $xx$ as a substring. That doesn't mean that $L^*$ doesn't exist; it just means that it doesn't have some property that $L$ has. Well, that's no surprise because $L$ and $L^*$ are often different languages, in which case they can't have exactly the same properties.

• Is it what we call "closure property under Kleene-star"? The Kleene-star operation on languages (from the same family of languages) doesn't mean it will still result with belonging in the same family of languages. – kate Jan 29 '16 at 0:59
• @kate A set $\mathcal{S}$ of languages is "closed under Kleene-star" if, whenever $L\in\mathcal{S}$, we also have $L^*\in\mathcal{S}$. Various classes of languages (such as regular languages, context-free languages, decidable languages) are closed under ${}^*$. But it's possible for a class of languages not to be closed under ${}^*$: one example of this is the class of languages in which no string contains $xx$, as shown by the example in the question ($L$ is in that class but $L^*$ is not). – David Richerby Jan 29 '16 at 1:22

Simply saying that $L$ has the alphabet $\{x, y\}$ and that no string in $L$ contains the substring $xx$ doesn't define a single language - there are infinite such languages. What you call expressing $L = \{y, xy, yx\}$ is actually defining such a language $L$ with three words that happens to have the property of no strings containing $xx$. $L^*$ doesn't have this property, because it contains the word $yxxy$ (as well as infinite other words with double $x$).

I'm not sure exactly what you're trying to prove in the second part of your post. For any language $M$, the Kleene closure $M^*$ always exists; if $M$ is regular, than $M^*$ is also regular by definition. Whether it has the property of containing no words with the substring $x$ depends on the definition of $M$.

• To the first paragraph, agreed on all points. I picture all languages L that conform to the language definition as indexed sets, so L_1 could be just {y}, L_2 could be {<null string>, xy, yx}, and so on. To the second paragraph, I'm trying to see whether it is possible for L* to exist if there are languages (e.g. L_1, L_2, etc...) that do conform to the language definition that can't be part of L* because allowing them to be a subset of L* would violate the language definition. – Chris F. Jan 27 '16 at 22:38
• Continuing my point, I would assume that if that were the case, you couldn't say that a language L exists such that L* conforms to the language definition. – Chris F. Jan 27 '16 at 22:43

$L^*$ exist. You have to see the languages as a set of words. The language $L$ is the infinite set of words formed with the symbols $x$ and $y$ that don't contain the substring $xx$. $L^*$ is the smallest superset of $L$ that contains the empty string $\epsilon$ and is closed under the string concatenation operation.

Note: You don't have to determine if $L^*$ exist. If $L$ is a regular language then by definition $L^*$ exist and it is a regular language too.

• By "closed under the string concatenation operation", do you mean that any concatenation performed on strings in L* yields a valid string in L*? That is, similar to the way addition is a closed operation on the set of natural numbers. – Chris F. Jan 27 '16 at 22:47
• "The language $L$ is the infinite set of words formed with the symbols $x$ and $y$ that don't contain the substring $xx$." No it's not. It's just some language that doesn't have $xx$ in any of its strings. In particular, the question is about the finite language $\{y,xy,yx\}$. Also, you don't need $L$ to be regular for $L^*$ to exist: the operation ${}^*$ is defined for any language. – David Richerby Jan 28 '16 at 1:14
• @DavidRicherby I assume in my answer that the OP is confused about the language because first he gives the definition of an infinite language and then he said it is a finite language. About your final statement I never say the opposite but it is a nice complementation to my answer. – Renato Sanhueza Jan 28 '16 at 2:21
• @CF That is right. :) – Renato Sanhueza Jan 28 '16 at 2:23
• @RenatoSanhueza S/he doesn't define an infinite language. S/he says, "I place the restriction that there can be no string in the language that contains the substring 'xx'." That categorically does not say that $L$ is the language consisting of all strings that don't have $xx$ as a substring; it just says that it's some set of strings, none of which contains $xx$. – David Richerby Jan 28 '16 at 2:28