# 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
250 views

401 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 ...
231 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 ...
94 views

### Prove the following language is regular using closures

How can I prove this language is regular using just closures and homomorphism? $$L = \{a_1b_1a_2b_2\dotsm a_nb_n \mid a_i \in L_1 , b_i \in L_2\}$$ and we know $L_1$ and $L_2$ are regular.
174 views

### Question of DFA closure properties?

I have some question about DFA Language properties. Does closure under intersection and complementation imply closure under union? Does closure under intersection and union imply closure under ...
276 views

### Reflexive transitive closure = (zero or more) Kleene star?

In Alloy Tutorial they denote some reflexive transitive closure with Kleene star saying that they admit zero or more elements at that position. ...
224 views

### Is the union between a regular language and a random language also a regular language?

If not can we draw any conclusion about the newly fromed language, the language that represents the union between a regular language and a non regular language (not context free but a truly random ...
7k views

### Proof that the regular languages are closed under string homomorphism

Where can I find a proof of this? Thanks!
371 views

### Closure of regular languages to shuffle using closure operations

Given a language: $L = \{\; a_1b_1a_2b_2a_3b_3\dots a_nb_n \mid \forall i: a_i,b_i \in \Sigma, a_1\dots a_n \in L_1\ , b_1\dots b_n \in L_2 \;\}$ Also $L_1, L_2$ are regular languages. Using ...
150 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 ...
2k views

### How to prove regular languages are closed under left quotient?

$L$ is a regular language over the alphabet $\Sigma = \{a,b\}$. The left quotient of $L$ regarding $w \in \Sigma^*$ is the language $$w^{-1} L := \{v \mid wv \in L\}$$ How can I prove that $w^{-1}L$ ...
4k views

### If $L$ is a regular language then so is $\sqrt{L}=\{w:ww\in L\}$

I am interested in proving that $\sqrt{L}=\{w:ww\in L\}$ is regular if $L$ is regular but I don't seem to be getting anywhere. If possible I was hoping for a hint to get me going in the right ...
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 ...
246 views

### How do I prove that a language is regular? [duplicate]

In order to prove that the following language is regular, would I use a pumping lemma? The set $A$ of all strings that are substrings of some string in $L$, where $L \subseteq\Sigma^*$. $L$ Must be ...
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 ...
121 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?
796 views

### Should two DFAs be complete before making an intersection of them?

In the slides given by my teacher, the third automaton is the product of the first two: I tried to do the product myself by doing the transition table of both automata at the same time. I got stuck ...
3k views

### How to show that a language {w|ww^R in A} is regular, A being regular?

Been working on my homework and I've been stuck on a question for over a week now. Not really asking for a solution but if someone could point me towards the right direction that would be great, as I ...
509 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 ...
457 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 ...
119 views

171 views

### Smallest class of automata model whose corresponding language class contains CFL and is closed against (dis)allowing nondeterminism in the model

From a comment, an interesting question popped up. The class of CFLs (the languages recognized by PDAs) are obviously not closed under nondeterminism - what I mean by this is that deterministic PDAs ...
526 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 ...
184 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, ...