# Questions tagged [closure-properties]

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

306 questions
Filter by
Sorted by
Tagged with
687 views

### Class P is closed under concatenation

Proving that Class P is closed under concatenation. The answer is given below: But I do not know why stage 2 is repeated at most O(n), could anyone explain this for me please?
249 views

192 views

### Closure of regular languages under non-contiguous subsequence

Suppose there is a language $L$ on alphabet $Σ$. Now consider the language $$S(L) = \{x : wxy ∈ L, w, y ∈ Σ^*\} ∪ \{x : w ∈ L,\text{ and x is a subsequence of w}\}.$$ How to prove that if $L$ ...
323 views

### CFL Intersection with Regular Language prove

how can i prove the following statement : 1- $L_1\subseteq\Sigma^*$ is CFL and $L_2\subseteq\Sigma^*$ is regular Language, then $L_1$\ $L_2$ is CFL . so i want to know what is the method to prove it ...
I have following statements which I must prove or disprove : 1) Let $L$ be a CFL and $k \in N$ then $L^k$ is also a CFL. 2) $L_1 \subseteq L_2 \subseteq L_3$ are Languages, if $L_1$ and $L_3$ are ...
Given $L_1$ and $L_2$ over some alphabet: $L_1@L_2 = \{uv \mid u \in L_1 \land v \in L_2 \land |u|=|v|\}$ The question is: if $L_1$ is regular and $L_2$ is context-free, is $L_1@L_2$ context free? ...