# Tag Info

Accepted

### context-free shuffle for two-letter alphabets

Two letters should be sufficient as the following example shows: let $L_1=\{a^nba^n\mid n\geq1\}$ and $L_2=\{b^nab^n\mid n\geq1\}$. Then we have (L_1\|L_2)\cap a^*b^*a^*b^*=\{a^mb^{n+1}a^{m+1}b^n\...
• 166
Accepted

• 2,590
1 vote

### Intersection of different languages

A general principle that may help: Deterministically-defined language classes (e.g., Regular, Turing-decidable), are typically closed under union, intersection, and complement. Nondeterministically-...
• 6,873
1 vote

### Intersection of different languages

Nope. For several examples, see https://en.wikipedia.org/wiki/Context-free_language#Nonclosure_under_intersection,_complement,_and_difference, Which closure properties are always valid between ...
• 154k
1 vote

### Proving that non-regular languages are closed under concatenation

Concatenation of two non-regular languages may be regular. Constructive Proof: Let $L$ be any non-regular language. Now, we know $L’$ is also non-regular. Consider $(L \cup \{ \epsilon \})$ ; \$(L’ \...

Only top scored, non community-wiki answers of a minimum length are eligible