Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
Lets assume that we have access to a oracle (machine that determines without details) for $L^*$, can we calculate $L$ from this machine? The cost of operation is measured by number of queries from oracle.
Can any property of $L$ like being prefix free or regular help?
What if the language be finite and instead of $L^*$ we have an oracle access to $L^k$ for a known $k$?
Consider $L_1 = \{a\}$ and $L_2 = \{a, aa\}$. In this case $L_1^* = L_2^*$. Thus a language is not uniquely determined from its Kleene closure.
Moreover you cannot determine a lot of information about a language from simply querying an oracle. Even if you had access to an oracle for $L$ itself rather than $L^*$, you would not learn much.
That is because you can only ever do a finite number of queries to the oracle. So for a finite number of strings, you know if they are in the language. It could be that every string, which you did not query, is in the language, which would make $L$ regular. Or it could be that none of the strings, which you did not query are in the language, which would also make $L$ regular. It is also possible to simply pick any arbitrary regular language $L'$ and assume that the rest of the strings are in $L$ if they are in $L'$ and vice versa. In that case $L$ would also be regular, because adding or removing a finite number of strings from a regular language would also produce a regular language.
The parts of $L$ which you did not yet query the oracle about could also have a non-regular structure, it could even be non-computable.
There are properties about $L$ which could help. For example if a property about $L$ was stated in such a way, that there would only be a finite number of languages satisfying the property, the problem would get a lot simpler.
For certain properties about $L$, it would even be possible to identify an $L$ from an infinite set of candidates, however such an algorithm would not necessarily terminate, if given an input not satisfying the property.
For example if it is required that $L$ consists of exactly one string, there are infinitely many candidate languages, but knowing the alphabet, it is possible to search for this string and find it in finite time. If this algorithm was executed on $Ø$ (which does not satisfy the property), the algorithm would never terminate.
Being prefix free would certainly help, but this is not the more general situation where the solution is easy.
A language $X$ is a (length variable) code if $X^*$ is a free monoid. This means that if $x_1, ..., x_n$ and $y_1, ..., y_m$ are elements of $X$ such that $x_1 \dotsm x_n = y_1 \dotsm y_m$, then $n = m$ and $x_1 = y_1$, $\ldots$, $x_n = y_n$. This is the case in particular if $X$ is a prefix code, which means that if $x, xu \in X$, then $u = 1$ (the empty word). This is also the case for the dual notion of a suffix code. However, there exist codes which are neither prefix nor suffix, like $\{aa, ba, baa\}$ (Exercise !)
Now, if $X$ is a code, then $X = X^+X^+ \setminus X^+$ where $X^+ = X^* \setminus 1$. Consequently, when $X$ is a code, it is very easy to compute $X$ from $X^*$ and the solution is unique. In particular, if $X^*$ is regular, so is $X$.
