# Questions tagged [closure-properties]

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

322 questions
Filter by
Sorted by
Tagged with
334 views

### If pref(L) is regular, does that imply L is regular?

I have this exercise for homework: Say we have a language L. we know that the language pref(L) (all the prefixes of ...
240 views

445 views

### Reverse the input and output of a Mealy machine

Given a Mealy machine $M$, is it possible to construct another Mealy machine $M'$ that generates the reverse outputs from the reverse inputs, and if so, how? That is, for each string $s$, $M(s) = t$ ...
567 views

### Constructing a decider for a language

I'm confused about the idea of constructing a decider for a language and i need some help with it. For example, if i have an enumerator M1 for a language L and another enumerator M2 for the ...
518 views

### If A is NL-complete then complement of A is also NL-complete?

We know that coNL = NL. But, is this also true? If A is NL-complete then complement of A is also NL-complete? I don't see a reason for that it could be true.
612 views

### Under which operations is the class of non-recursive languages a closure?

I am currently studying turing computability and related problems such as the halting problem with a background in formal languages. I know that the class of recursive (decidable) languages is a ...
96 views

### If $R,F \cap R, F \cap \overline{R}$ are regular, is $F$ regular?

Let $R \in REG$. Is it true that if $F\cap R \in REG$ and $F \cap \overline{R} \in REG$ then $F \in REG$? I took $R = \Sigma^{\ast}$ and because $F\cap R \in REG$, $F$ must be regular. Is this the ...
2k views

### Closure properties of undecidable languages

I know that the decidable are close under: complementation, union, intersection and concatenation? What about the undecidable languages? I think they are close under complementation, but not under ...
217 views

### PSPACE languages reducible to other PSPACE languages in polynomial space

Intuitively it makes sense that all PSPACE languages are reducible to other PSPACE languages in polynomial space. But how would I go about actually showing this?
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 ...
177 views

### Don't understand closure under string reversal

I am trying to learn from http://www.cs.uiuc.edu/class/su08/cs273/lectures/lect_06.pdf #2 and I understand everything except for the 2nd line of delta prime prime function, I having breaking down ...
3k views

### Show that the regular languages are closed against taking “the second half” [duplicate]

Given $L$ is regular, the proof that $\mathrm{HALF}(L)$ is regular is pretty straightforward to me (e.g., #11 in this link): simply making a NFA and meeting in the middle with 2 original DFAs, the ...
79 views

### Is CFL closed against exchanging complementation and reversal?

Let $L$ be a language such that $\overline{L}^R$ (the reversal of the complement of $L$) is context-free. Is then also $\overline{(L^R)} \in \mathrm{CFL}$?
838 views

### How can I show a linear languages are closed against concatenating with regular ones?

This was given as a homework problem but I have already submitted the assignment. I'd like to resolve it at this point for my own satisfaction. Given that $L_1$ is a linear language and $L_2$ is a ...
86 views

24 views

### $L = \{\alpha^i \beta^j \gamma^k \vert i,j,k \in \mathbb{N}_0, (i=1) \Rightarrow (j=k)\}$

I am asking this question here, because I am not allowed to comment on the thread that I am actually interested in, but maybe someone can still help me? I alredy found an anwser to the Problem above (...
34 views

### Decidability of equality of expressions involving exponentiation

Let's have expressions that are finite-sized trees, with elements of $\mathbb N$ as leaf nodes and the operations {$+,\times,-,/$, ^} with their usual semantics as the internal nodes, with the special ...
131 views

### Is star closure of reverse of grammar equivalent to reverse of closure of that grammar

I need to proof if that it's true or not. $(G^R)^* = (G^*)^R$ If $G$ is a CFG and $G = \langle V, \Sigma, \delta, S \rangle$ where $V$ = Set of Variables or Non-Terminal Symbols $\Sigma$ = ...
197 views

### Unrestricted grammar is closed under intersection

I want to show that unrestricted grammar is closed under intersection and I don't want to use Turing machine or etc. So I think that we have two grammar $G_1$ and $G_2$ that are restricted for example ...
456 views

### Is PSPACE closed under the following forall-there-exists construction?

Suppose I have a language $L$ (over alphabet $\Sigma$), such that $$w \in L \iff (\forall x \in \Sigma^*) (\exists y \in \Sigma^*) P(x,y,w).$$ and I can give a turing machine that decides $P(x,y,w)$ ...
189 views

### Proving specific prefixes of regular languages are regular

There are particular problems in Kozen that I'm unable to solve, and they seem to be similar to each other. It is showing that sets: $$\{x \mid \exists y: |y| = 2^{|x|} \text{ and } xy \in A \}$$  ...
577 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 ...
240 views

### Formal language properties and finite state machines [closed]

What are properties of a formal language? Which and how would they be needed to prove that some Non-Deterministic finite state machine can accept a given language?
42 views

### Are deterministic context-free languages closed under reversal of languages? [duplicate]

It is well known that context-free languages are closed under the reversal of $L$. My answer to the question "Is the time reversal symmetry of non-deterministic computations important?" notices that ...
1k views

### Turing-recognizable languages closed under star operation

I'm tasked with demonstrating that the class of Turing-recognizable languages is closed under the operation of star, but I'm confused about how this is true. For example, I have a TM to recognize a ...
130 views