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
0
votes
1answer
298 views

Proof Check: The class L is closed under concatenation

I want to prove that the class of all Turing machines that use a logarithmic amount of space is closed under concatenation. The basic idea of my proof is this: given a word, to check if it's in $...
0
votes
0answers
257 views

Writing a constructive proof for closure of a regular language under homomorphism

I've spend the last few days searching online for an example of a constructive proof of regular languages being closed under homomorphism, but I have not seen one. I am mostly unsure of how to show ...
0
votes
0answers
72 views

mapping reduction for every recursive language [duplicate]

how do I prove that for every 2 languages $A,B\in R$ where $A,B \notin \{ \emptyset , \Sigma^* \}$ I can do a reduction $A \leq_m B$? [EDIT] My try: $A$ is decidable therefore it has a turing ...
0
votes
0answers
177 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 ...
0
votes
1answer
238 views

prove decidability and recognizability

I want to prove that for any language $L_1$ described by a Turing machine and any regular language $L_2$, $L_1 \cap L_2$ is described by a Turing machine that its recognizability and decidability is ...
0
votes
1answer
4k views

Kleene positive closure - help in proofing this claim

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}...
-1
votes
2answers
133 views

Why L' is not regular?

$$L'=\{ww|w\in L\}$$ I need to give an example of regular language L for which the concatenation of 2's $w$ gives $L'$ which is not regular. How can I give such an example if according to closure ...
-1
votes
1answer
51 views

P is closed under power of integer

I'm new in this area of complexity and I'm trying to get into it by understanding basic proofs. I want to prove that if $L\in P$, so $L^k\in P$, where $k$ is non-negative integer. How to prove it in ...
-1
votes
1answer
843 views

when can I know if a class (complexity) is closed under reduction (cook/karp)

How do I know if a class let's say PP , is closed under cook reduction or not closed? I understand the concept of reduction (how to use it mainly) , but still can't figure out the meaning behind it, ...
-1
votes
1answer
2k views

Finding a Regular Expression for an Intersection of Two Regular Expressions

Finding a Regular Expression for an Intersection of Two Regular Expressions PAIR of regular expressions is ((ss*)t*) and ((ss*) + (tt*)). How do I find a regular expression that represents the ...
-1
votes
1answer
62 views

Prove a Language is Regular [duplicate]

For a language $L\in\Sigma^*$ we define $$ L^*=\{w\mid \exists k\in \mathbb{N}\cup\{0\}, ∃x_1,...,x_k\in L \ (w=x_1...x_k) \} $$ Let $L$ be a regular language over some alphabet $\Sigma$. Prove that $...
-1
votes
1answer
127 views

Turing Machine and decidability

so the thing is that i have to prove that if the language $L ⊆ \Sigma^*$ is decidable then both languages are also decidable. $$P_1(L) = \{w ∈ Σ\mid \text{ For every prefix v of w, we have }v ∈ L\},$$ ...
-1
votes
1answer
208 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
631 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
123 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
400 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
200 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
125 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
130 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
291 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