# Questions tagged [closure-properties]

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

91 questions
Filter by
Sorted by
Tagged with
2k views

• 541
8k views

### Easy proof for context-free languages being closed under cyclic shift

The cyclic shift (also called rotation or conjugation) of a language $L$ is defined as $\{ yx \mid xy \in L \}$. According to wikipedia (and here) the context-free languages are closed under this ...
• 30.7k
2k views

### Kleene star of an infinite unary language always yields a regular language [duplicate]

Let $L = \{a^n \mid n \ge 0\}$, where $a^0 = \epsilon$ and $a^n = a^{n-1}a$ for all $n \ge 1$. Thus $L$ consists of sequences of $a$ of all lengths, including a sequence of length $0$. Let $L_2$ be ...
5k views

### Is an inﬁnite union of context-free languages always context-free?

Let $L_1$, $L_2$, $L_3$, $\dots$ be an inﬁnite sequence of context-free languages, each of which is deﬁned over a common alphabet $Σ$. Let $L$ be the inﬁnite union of $L_1$, $L_2$, $L_3$, $\dots$; i....
• 2,193
35k views

### Complement of Non deterministic Finite Automata

It's known that the complement of a DFA can be easily formed. That is, given a machine $M$, we can construct $M'$ such that $L(M') = \Sigma^* \setminus L(M)$. Is it possible to construct such a ...
• 71
4k views

• 251
3k views

• 121
1 vote
11k views

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

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

### Language described by inverting accepting states of NFA

Connecting to When states that are not accepting states become accepting states in NFA, what happens?, what is the formal language described by inverting accepting states of NFA? By inverting, I mean ...
• 1
5k views

### Show that the collection of Turing-recognizable languages is closed under homomorphism [duplicate]

I have seen this question here, Closure of Turing-recognizable languages under homomorphism But actually this question answers the question of "What is the relation between homomorphism and ...
• 149
109 views

### Regular languages and sets proof

I just have general questions about sets and determining if they are regular languages. i) If A is regular, and A is a subset of B, then B must be regular. ii) If B is regular, and A is a subset of ...
608 views

### Proving closure under reversal of languages accepted by min-heap automata

This is a follow-up question of this one. In a previous question about exotic state machines, Alex ten Brink and Raphael addressed the computational capabilities of a peculiar kind of state machine: ...
• 12.9k
3k 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$ ...
• 889
4k views

### Operations under which the class of undecidable languages isn't closed

Do there exist undecidable languages such that their union/intersection/concatenated language is decidable? What is the physical interpretation of such example because in general, undecidable ...
24k views

### What is complement of Context-free languages?

I need to know what class of CFL is closed under i.e. what set is complement of CFL. I know CFL is not closed under complement, and I know that P is closed under complement. Since CFL $\subsetneq$ P I ...
• 123
21k views

### Union of regular languages that is not regular

I've come across that question : "Give examples of two regular languages which their union doesn't output a regular language. " This is pretty shocking to me because I believe that regular languages ...
• 279
### If $L_1L_2$ is regular language then is $L_2L_1$ regular too?
We have two languages: $L_1,L_2$. We know that $L_1L_2$ is regular language, so my question is if $L_2L_1$ is regular too? I try to find a way to prove it... I can't assume of course that $L_1,L_2$ ...