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
5
votes
3answers
12k views

Decidable languages kleene star closure - question on a proof

I read a proof on the closure of decidable languages under kleene star. It begins by saying that the turing machine we want to find would non-determistically split the input string and then use the ...
5
votes
1answer
296 views

Closure against the operator $A(L)=\{ww^Rw \mid w \in L \wedge |w| \lt 2007\}$

I would like your help with the following question: Let $L$ be a language, and operator $A(L)=\{\,ww^Rw \mid w \in L\ \wedge\ |w| \lt 2007\,\}$ where $x^R$ is the reversed string of $x$. Which of ...
5
votes
1answer
362 views

The operator $A(L)= \{w \mid ww \in L\}$

Consider the operator $A(L)= \{w \mid ww \in L\}$. Apparently, the class of context free languages is not closed against $A$. Still, after a lot of thinking, I can't find any CFL for which $A(L)$ ...
5
votes
2answers
360 views

Prove that $L_1$ is regular if $L_2$, $L_1L_2$, $L_2L_1$ are regular

Prove that $L_1$ is regular if $L_2$, $L_1L_2$, $L_2L_1$ are regular. These are the things that I would use to start. As $L_1L_2$ is regular, then the homomorphism $h(L_1L_2)$ is regular. Let $h(L_1)...
5
votes
3answers
365 views

Are deterministic and nondeterministic Cellular Automata equivalent?

It seems that in CA context nondeterministic (ND) means probabilistic, not ND as in NFSMs. At least I haven't seen a paper or book which discusses NCAs, without talking about probabilistic CAs. I ...
5
votes
3answers
2k views

Closure of Deterministic context-free languages under prefix

For a formal language $L \subseteq \Sigma^{*}$ I define the set Pref(L) to be: $\text{pref}(L) = \{\alpha \in \Sigma^{*} : \exists \beta \in \Sigma^{*} \text{ such that } \alpha \beta \in L\}$ ie. ...
5
votes
4answers
3k views

Proof that regular languages are closed against taking the even-length subset

This question is on the GRE Computer Science test booklet (not homework). I tried applying closure properties of regular languages but no success. Suppose $L$ is a regular language over $\Sigma = \{0,...
5
votes
1answer
137 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 ...
5
votes
1answer
306 views

Reference request: proof that if $L \in DCFL$, then $L \Sigma^* \in DCFL$

So, it's fairly easy to prove that if $L \in DCFL$, then $L \Sigma^* \in DCFL$. Basically, you take the DPDA accepting $L$. You remove all transitions on final states, and then for each $a \in \Sigma$ ...
5
votes
1answer
270 views

Closure under intersection of context free binary trees

Some sets of ordered binary trees can be represented as a CFG with rules of the form A -> aBC A -> b Where A,B,C are ...
5
votes
1answer
698 views

Deterministic context-free languages are closed under regular right-product

I am looking for a proof for the following problem: For languages $L$ and $R$, if $L$ is deterministic context-free and $R$ is regular, then $LR$ is a deterministic context-free language. Note:...
5
votes
1answer
2k views

Difference between substitution, morphism, and homomorphism

In closure properties, I got confused between substitution and morphism. 1) According to Wikipedia, string substitution means to map letters in a set of alphabets to languages (possibly in a ...
4
votes
2answers
2k views

Why NP is not closed under Turing reduction

The notion of polynomial time Turing reductions (Cook reductions) is an abstraction of a very intuitive concept: efficiently solving a problem by using another algorithm as a subroutine. For example,...
4
votes
1answer
848 views

Proving that if L is regular. Then L′ = {ww : w ∈ L} is regular

I believe this statement to be true. And here's my reasoning: Based on regular languages properties, the concatenation of two regular languages is regular. And since L′ = L · L, it follows that L′ ...
4
votes
3answers
3k views

Show that P is closed against the Kleene star

I have that question that looks kinda easy at first but it is quite hard. Let $L\in P$. Prove that $L^*\in P$ my approach: I tried to generate a Turing machine but I got stuck with the thing of ...
4
votes
1answer
322 views

Is NEXP = co-NEXP?

It is known that $\mathsf{NL}=\mathsf{Co{-}NL}$ and unknown if $\mathsf{NP}=\mathsf{Co{-}NP}$. But what about $$\mathsf{NEXP}=\mathsf{Co{-}NEXP}?$$ Is it known whether these two classes are equal?
4
votes
1answer
330 views

Closure properties of the class of inherently ambiguous CFLs

is set of inherently ambiguous context free languages close under operations such that union, intersection, kleene star, concatenation, reverse, complementation and etc. how many of theme are answered?...
4
votes
1answer
699 views

$\mathbf{NC}$ is closed under logspace reductions

I am trying to solve the question 6.12 in Arora-Barak (Computational Complexity: A modern approach). The question asks you to show that the $\mathsf{PATH}$ problem (decide whether a graph $G$ has a ...
4
votes
3answers
2k views

Proving that recursively enumerable languages are closed against taking prefixes

Define $\mathrm{Prefix} (L) = \{x\mid \exists y .xy \in L \}$. I'd love your help with proving that $\mathsf{RE}$ languages are closed under $\mathrm{Prefix}$. I know that recursively enumerable ...
4
votes
1answer
156 views

Inverse Homomorphisms and Kleene star

The exercise is to prove or give a counterexample to the following proposition with $L \subseteq \Gamma^*$ regular and $h: \Gamma \to \Sigma^*$ a homomorphism. Is there any regular language $L'$ such ...
4
votes
1answer
37 views

Closure operator and set of fixpoint

In chapter 2.2 of Giacobazzi, Roberto; Ranzato, Francesco, Uniform closures: Order-theoretically reconstructing logic program semantics and abstract domain refinements, Inf. Comput. 145, No.2, 153-...
4
votes
1answer
566 views

L closed under logspace reduction

Given two languages $A$ and $B$ I have been asked to show that, if $B \in L$ and we have a logspace reduction $f$ from $A$ to $B$ then $A \in L$. I read the proof that $L$ is closed under logspace ...
4
votes
1answer
903 views

Proof that CFL aren't closed under intersection using synchronous parallel (N)PDA composition

It is well known that the class of CFLs is not closed under intersection as follows e.g. from the following example: $$L_1 \cap L_2 = \left\{ a^mb^mc^n \mid m,n \ge 1 \right\} \cap \left\{ a^mb^nc^n \...
4
votes
2answers
359 views

Does closure against countable union survive union of classes?

A class of languages $\mathcal{C}$ is closed under countable union (cucu) if for all series of languages in $\mathcal{C}$ ($(L_i)_{i\in\mathbb{N}} \in \mathcal{C}^\mathbb{N}$) the language $\bigcup_{i\...
4
votes
1answer
177 views

Complement of Mealy machine

How could one reasonably define and construct the complement of a deterministic Mealy machine? My intuition is that the complement should give exactly the opposite of output strings after a specific ...
4
votes
1answer
479 views

Prove that PP is closed under complement

I found this proof in Wikipedia, but one of the most important steps in it doesn't make any sense to me. I'll explain: By the definition of PP there is a polynomial-time probabilistic algorithm ...
4
votes
1answer
225 views

How to prove that a transformed language is regular using an NFA

I am trying to prove that if a language $ L $ of binary strings (i.e. a subset of [01]*) is regular then so is the transformed language $ plus (L) $ consisting of ...
4
votes
1answer
470 views

Given a non-deterministic Mealy machine $M$, if $L$ is regular, is $M(L)$ regular?

Consider a nondeterministic Mealy machine, $M$, defined as follows: $M = (Q, \Sigma, \Delta, \delta, \tau, q_0)$ where $Q$ is a finite set of states $\Sigma$ is an input alphabet $\Delta$ is an ...
3
votes
3answers
1k views

Why is the set of all regular expressions classified as context-free, instead of regular?

As I understand regular languages can be closed under concatenation, so can I concatenate the set of all regular expressions to classify them as regular?
3
votes
2answers
824 views

If both the concatenation of two languages and the second “half” are regular, is the first too?

Given that $L_2$ is regular and infinite and $L_1 \cdot L_2$ is regular, then $L_1$ is also regular. I need some help on getting started on proving this is the case. My intuition is that if $L_1 \...
3
votes
3answers
2k views

Are regular and context free languages closed against making them prefix-free?

For a language L we define: $\qquad A(L) = \{ x \in L \mid \text{ no proper prefix of x is in L} \} $ Are regular / context free languages closed under this operation ? For regular languages I ...
3
votes
2answers
4k views

Are regular languages closed under inverse homomorphism?

Let $\Sigma$ and $\Delta$ be alphabets. Consider a function $\varphi: \Sigma \rightarrow \Delta^*$. Extend $\varphi$ to a function from $\Sigma^* \rightarrow \Delta^*$ such that: \begin{eqnarray*} \...
3
votes
2answers
7k views

Is every subset of a decidable set, also decidable?

Is it true that if A is a subset of B, and B is decidable, than A is guaranteed to be decidable? I believe it would be true because all the subsets of B should also be decidable making A decidable. I'...
3
votes
2answers
512 views

Proving that PP is closed under symmetric difference

I want to prove that PP is under symmertic difference. let A be a language in PP and B likewise. I tried showing that : (A\B) U (B\A) in PP , so by show each in PP and then showing that it's closed ...
3
votes
3answers
4k views

If L is regular, show that even(L) is also regular

I am stuck on the following question. If $L$ is regular show that $\mathrm{even}(L)$ is also regular, where $\mathrm{even}(L) = \{ even(w) : w \in L \}$, $w$ is a string in $L$ and $\mathrm{even}(w)...
3
votes
3answers
4k views

Closure of CFL against right-quotient with regular languages

Let $A/B$ = $\{ w \mid wx \in A$ for some $x \in B \}$. Show that if A is context free and B is regular, then $A/B$ is context free. My interpretation of this is is that we need to show that if a ...
3
votes
1answer
565 views

If $L$ is CFL and $\overline{L}$ is CFL, then is L regular?

I've seen in previous exams that professors marked the theory as correct: If $L$ is CFL and $\overline{L}$ is CFL, then L is regular. I just don't see how this would work. How would we prove such ...
3
votes
2answers
368 views

Why is the subset of palindromes of a regular language context-free?

Why is $A(L) = \{x \in L \mid x = x^R \}$ context-free if $L$ is a regular language? Trying to understand the approach to determining whether a regular language is context-free.
3
votes
3answers
3k views

Show that regular languages are closed under Mix operations

Let $L_1, L_2$, two regular languages and the operations: $$Mix_1(L_1, L_2) =\{ a_1b_1a_2b_2\ldots a_nb_n | n\ge 0 \land a_1,a_2,\ldots ,a_n,b_1,b_2,\ldots ,b_n\in\Sigma\\ \land a_1a_2\ldots a_n\in ...
3
votes
3answers
3k views

Clearing a Confusion regarding the Proof of equal no of a's and b's not being a regular language

I was wondering about its proof. The direct use of pumping lemma here is not a viability. So a certain teacher of mine proved this with the notion that $a^{n}b^{n}$ being a subset of this language $L=\...
3
votes
1answer
488 views

For a regular language $L$, is $\{xy^Rz:xyz\in L\}$ regular?

For a regular language $L$, is $\{xy^Rz:xyz\in L\}$ regular? [Where $w^R$ is the reverse of $w$] My intuition says it is, as for a regular $L$, the languages $L^*$, $\{y: xyz\in L\}$ and $L^R$ are ...
3
votes
2answers
935 views

Showing Regular Languages are closed under removal of rightmost character

"Show that if L is a regular language without the empty string, then the language in which the rightmost symbol of every string in is removed is also regular." I tried going by closure properties of ...
3
votes
2answers
2k views

Why DCFL is not closed under kleene star?

I have read somewhere that DCFL is not closed under kleene star. but I haven't found any example
3
votes
1answer
282 views

Situations where Kleene star of A is context-free, but A is not

This question appeared on my Theory of Computer Science final: True | False: $A^*$ is context-free $\implies$ $A$ is context-free. My professor says the answer is false, and I believe him, but am ...
3
votes
2answers
96 views

Is $\{s_0 w s_1 : s_0s_1\in L_1, w\in L_2 \}$ context free if $L_1$ and $L_2$ are?

In class, it was alluded to that a language: \begin{equation*} \{s_0 w s_1 : s_0s_1\in L_1, w\in L_2 \} \end{equation*} would be context free, if $L_1$ and $L_2$ are context free. Intuitively, that ...
3
votes
2answers
173 views

Constructive Proof on Regular Languages

As an assignment, I've to come up with constructive proofs for the following languages to be regular supposing A and B are two distinct regular languages. $$L_1=\{w│w^R∈A\}$$ $$L_2=\{w│w=a_1 b_1,…,...
3
votes
2answers
2k views

Why are palindrome and not-palindrome both context-free?

Both palindrome and its complement are context-free. This is very interesting. Both are non-deterministic context-free, which in general are not closed under complement. What is it about these two ...
3
votes
1answer
140 views

Generators of families of langauges?

From Wikipedia's definition of regular langauges The collection of regular languages over an alphabet $Σ$ is defined recursively as follows: The empty language $Ø$ is a regular language. ...
3
votes
2answers
2k views

Do Kleene star and complement commute?

I am having hard time solving the following problem. Are there any languages for which $$ \overline{L^*} = (\overline{L})^* $$ Assuming $\emptyset^* = \emptyset$, if I consider $\Sigma = \{a\}$ ...
3
votes
2answers
9k views

Why is the class of recursively enumerable languages not closed under complementation?

I am having a hard time understanding closure properties of recrusively enumerable languages. I have read the explanation on this site but still unable to fully understand why they are not closed ...

1
2
3 4 5
7