Questions tagged [closure-properties]

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

Filter by
Sorted by
Tagged with
-1
votes
1answer
192 views

Is the complement of the given language necessarily in NP?

$A$ is a given language so that $A \in NP$. Assume that $P = NP$. Is $A'$ necessarily in NP? What I did: $A \in NP , P=NP$ $P=coP$ (Can be proven by running a TM $M$ as a decider for P, ...
-1
votes
1answer
537 views

Prove a language is regular - Regular language of 0's and 1's [duplicate]

I'm new to regular languages and I've been struggling to solve one for a while. The question is: If there exists a regular language L1 which has an alphabet {0,1}, prove that L2 is also a regular ...
-1
votes
1answer
120 views

How to show that certain summations are primitive recursive?

If we have a function $g\colon \mathbb{N}^{k+1} \to \mathbb{N}$ which is primitive-recursive. How to show that the function $f\colon \mathbb{N}^{k+1} \to \mathbb{N}$ with $$f(x_1, \dots, x_k , x_{k+...
-2
votes
2answers
378 views

Why is the intersection of CFL and RL not always RL?

Suppose M is a CFL and N is aa RL. Then wouldn't the language generated by the intersection of M and N contain strings, some of which are accepted by both DFA and PDA? So if they are accepted by a DFA ...
-2
votes
1answer
1k views

Is a language closed under string concatenation, repetition, and/or taking substring regular?

Is a language $L$ regular, context-free, context-sensitive, recursively enumerable, or ..., if $L$ is closed under string concatenation, and/or string repetition, and/or taking substring? Somehow ...
-2
votes
1answer
194 views

Show that the complements of NP-languages with one word per length are in NP as well

Let L be a language over Σ i.e., $L\subseteq Σ^∗$. Suppose L satisfies the > two conditions given below. L is in NP and for every n, there is exactly one string of length n that belongs to ...
-2
votes
1answer
123 views

Proving that REG is reverse-closed against inverse homomorphism

prove/disprove If inverse homomorphism of languages is regular then languages is also regular? Let $h$ be a homomorphism , if $h^{-1}(L)$ is regular then $L$ is also regular?
-2
votes
1answer
176 views

proving that pp closed under cook reductions [closed]

I tried to prove or disprove that pp is closed under cook reductions. anyone has a idea or link to a answer?
-3
votes
1answer
128 views

Prove A² is regular [duplicate]

Suppose that $A$ is a regular language. How can I show that $A^2 = A \cdot A$ is a regular language? Is there a construction?
-3
votes
1answer
269 views

Complement of a Language which is set of Turing Machine descriptions

If $L$ is the set of strings $\langle M\rangle$ such that $M$ accepts all strings of even length and does not accept any strings of odd length. What will be $\overline L$ ? a) set of strings $\...

1
3 4 5 6
7