Skip to main content
5 votes

Does there exist an context free language L such that L∩L^R is not context free?

Consider $L = \{ a^n b^n a^m \mid m,n\ge 1\}$. In fact you can repeat this to get more equalities $\{ a^n b^n a^m b^m a^k \mid k,m,n\ge 1\}$. Etcetera. Note that we can get really fun things: For $ L ...
Hendrik Jan's user avatar
  • 30.8k
2 votes
Accepted

Matroid Closure follows the Closure Operator Properties

For $S \subseteq E$, by 1. you have $cl(S) \subseteq cl(cl(S))$. For the other direction, take any $e \in cl(cl(S))$. We show that $e \in cl(S)$. Suppose not, then $$ rank(cl(S)+e) \geq rank(S+e) > ...
ttnick's user avatar
  • 1,658
2 votes

Are NL-Complete languages closed under any regular operations?

NL-complete languages are in fact closed under complementation. This is not trivial at all and follows from the famous Immerman-Szelepcsényi theorem, which asserts NL = co-NL. (The proof is short but ...
Jean Abou Samra's user avatar
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* (...
pezbecoding's user avatar
1 vote

Are permutations of context-free languages context-free?

No, in general not. For example the MIX language, consisting of equal numbers of $\{a,b,c\}$ in any order is not context-free but is the permutation of the regular language $(abc)^*$.
Alexander Clark's user avatar

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