Skip to main content
4 of 5
edited body

This possibly is a solution to the final question: http://ac.els-cdn.com/0304397585900349/1-s2.0-0304397585900349-main.pdf?_tid=0e733f14-8779-11e7-9492-00000aab0f26&acdnat=1503434146_79c9bc9bf95106214e663bd9b5e7dcb2

or http://ac.els-cdn.com/0304397585900180/1-s2.0-0304397585900180-main.pdf?_tid=d337d502-877a-11e7-a57c-00000aab0f01&acdnat=1503434905_484d36a91ec2b2a425395e7d1a4e41ae

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