2
$\begingroup$

Is Every infinite c.e.language infinite or finite union of regular languages including at least one infinite regular language? And is every infinite c.e.language that is not indexed language(that may generated by indexed grammar) infinite union of infinite regular languages?

Third:what class of languages may be finite or infinite union of regular language. And similiarly, :what class of languages may be finite or infinite union of context-free languages

Finally, we try to search for the minimal and simple class of languages finite or infinite union of which is able to form every c.e.language.

Improve this question
$\endgroup$
3

2 Answers 2

Reset to default
5
$\begingroup$

A polynomial - time random language will not have any infinite regular subsets, so there's a counter example to the first question.

For a similar counterexample to the second question, we can increase the level of resource bounded randomness to something like an "EXPSPACE-random" language (since indexed languages are context-sensitive which implies they are in EXPSPACE).

Improve this answer
$\endgroup$
3
  • $\begingroup$ Excellent,Bjørn,a lot of thanks to you. $\endgroup$
    – XL _At_Here_There
    Commented Feb 18, 2014 at 5:21
  • $\begingroup$ A polynomial - time random language looks like immune set in lower level, an infinite sequence $Z\in \{0,1\}^N$is resource-bounded/computable random if there is no computable/resource-bounded martingale that succeeds on $Z$. $\endgroup$
    – XL _At_Here_There
    Commented Aug 23, 2017 at 2:29
  • $\begingroup$ "A polynomial - time random language will not have any infinite regular subsets,", where is this assertion from? Thank you in advance. $\endgroup$
    – XL _At_Here_There
    Commented Aug 23, 2017 at 3:10
0
$\begingroup$

This possibly is a solution to the final question,or this Actully, it is not only relating to Union of languages,but homomorphism and intersection. And there are several other solutions to the question in the reviewing part of the article of the URL.

Dyck language is defined as $S\to SS|[S]|\epsilon$.

Minimal linear grammars are defined as the production rules in the following form:

$S\to uSv|\omega, \omega, u,v\in \Sigma^*$ where $\Sigma^*$ is the Kleene closure.

But according to Bjørn Kjos-Hanssen's post, if I have not misunderstood, it is impossible to have low complexity languages to form higher complexity languages by finite or infinite union

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .