5
votes
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
2
votes
Accepted
is the class NP closed under set difference?
It is unknown whether $\mathsf{NP}$ is closed under set-difference.
If $\mathsf{NP}$ were known to be closed under set-difference then we would know that $\mathsf{NP} = \textsf{co-NP}$.
Indeed, for $L ...
- 27.5k
1
vote
Accepted
What can i say about L1 given that L2, L1L2 and L2L1 are regular?
I thought about it a bit after posting the question and came up with a counter-example for the second (and wrong) assumption:
L1 = { 0^p | p is a prime number} (Not a regular language), L2 = 0* (...
- 11
1
vote
Accepted
1
vote
Why these languages are closed under union or concatenation?
We have sets in different levels here: sets of words (languages) and sets of languages.
To avoid confusion I will call the latter a "family" of languages.
A family of languages $\mathcal F$ ...
- 29.6k
1
vote
If L = L1 U L2 is regular, L2 is the complement of L1 (which means L1 ∩ L2 = Ø), and we're given that L and L2 are regular, is L1 regular?
The language L1 is L \ L2. Take the FSMs for L and L2, create a new state machine whose states are pairs of states of these two FSMs, transitioning accordingly, and the accepting states are those that ...
- 27.8k
1
vote
If L = L1 U L2 is regular, L2 is the complement of L1 (which means L1 ∩ L2 = Ø), and we're given that L and L2 are regular, is L1 regular?
If $L_1$ is the complement of $L_2$ and $L_2$ is regular then $L_1$ must be regular since regular languages are closed under complement. Furthermore, since $L_1$ and $L_2$ are complements and $L = L_1 ...
- 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 ...
D.W.♦
- 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