Questions tagged [closure-properties]

Questions about operations on objects of some kind that result in objects of the same kind.

308 questions
Filter by
Sorted by
Tagged with
1k views

Symmetric Difference of Turing Recognizable and Finite Languages

Let A be a Turing Recognizable Language and B a finite Language. I want to prove that their symmetric difference is Turing Recognizable. My reasoning: B is finite, therefore the finite number of ...
556 views

Are DCFLs closed under concatenation with a regular language?

I have found various opinions saying they are (a link to one is given in D.W.'s comment). However, a proof that DCFLs themselves are not closed under concatenation found here on StackExchange seems to ...
865 views

120 views

Prove/ Disprove: If $L$ is a CFL then $A(L)$ is a CFL too

Consider the operation $A(L)$: $$A(L) = \{ w: w\in L \land w_R \notin L \}$$ where $w_R$ is the reverse of $w$. Prove/ Disprove: if $L$ is a CFL language so does $A(L)$. I am almost certain ...
119 views

Question on NP $\cap$ coNP

I'm struggling with a past paper question and would appreciate any hints: Suppose $L_1, L_2 \in$ NP $\cap$ coNP and $L_1 \oplus L_2 = \{ x : x$ is in exactly one of $L_1$ or $L_2 \}$. Then ...
1k views

61 views

170 views

Union, Intersection, Difference, etc. of different types of languages

I am preparing for a competitive exam (GATE) in which questions are asked in Automata about operations among different types of languages. For example, If $L_1$ is recursive & $L_2$ is ...
45 views

If $L$ is a $CFL$, then why isn't $L^*$ also $CFL$

I was studying closure properties of CFLs and I came across this. I want to understand why $L^*$ is not a CFL, can anyone explain me in depth with simple examples?
65 views

Decidability language, intersection

I have two langages $A, B \in \mathrm{coRE}$. How can I prove that $A \triangle B= ( A - B) \cup (B - A)$ is also in $\mathrm{coRE}\,$?
2k views

68 views

Are the complements of $NP$-languages with only $n$ words of length $n$ also in $NP$?

Assuming $\Sigma = \{ 0, 1\}$.. Given a language $L$, such that for each $n\in \mathbb{N}$ we have $n$ words of length $n$ in $L$ and assuming $L\in NP$, can we prove also that $L\in Co-NP$? So it ...
2k views

Find a CFG for the set of prefixes of a CFL [duplicate]

How do i generate grammar for Prefix of Langauge L, SupposeG=(V,􏰀,P,S)is a context-free grammar generating a CFL L then pref(L) is defined as pref(L)={x∈􏰀∗ : ∃ y such that xy∈L}. I understand for ...
322 views

If L is context-free, must FH(L) be context-free?

Define $FH(L) = \{x \in \Sigma^* : \exists y \in \Sigma^* \text{ with } |x| = |y| \text{ such that } xy \in L\}$. In other words, $FH(L)$ is the set of first halves of even length strings in $L$. ...
Note that this is not shuffle but perfect shuffle, defined as follows: Let $w = a_{1}a_{2} \ldots a_{n}$ and $x = b_{1}b_{2} \ldots b_{n}$ be two strings of the same length. Then the perfect shuffle ...
I just started a course called 'Automata and Formal Languages'. I'm having difficulty in proofing\disproofing this equality. $(L_{1} \circ L_{2})^{+} = L_{1}^{+} \circ L_{2}^{+}$ Where: \$ L_{1}...