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
14 votes
2 answers
2k views

Closure against right quotient with a fixed language

I'd really love your help with the following: For any fixed $L_2$ I need to decide whether there is closure under the following operators: $A_r(L)=\{x \mid \exists y \in L_2 : xy \in L\}$ $A_l(L)=\{...
Jozef's user avatar
  • 1,707
13 votes
1 answer
7k 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 ...
user99163's user avatar
  • 131
10 votes
3 answers
4k views

If $L$ is context-free and $R$ is regular, then $L / R$ is context-free?

I'm am stuck solving the next exercise: Argue that if $L$ is context-free and $R$ is regular, then $L / R = \{ w \mid \exists x \in R \;\text{s.t}\; wx \in L\} $ (i.e. the right quotient) is context-...
Dommicentl's user avatar
12 votes
7 answers
2k views

Is $A$ regular if $A^{2}$ is regular?

If $A^2$ is regular, does it follow that $A$ is regular? My attempt on a proof: Yes, for contradiction assume that $A$ is not regular. Then $A^2 = A \cdot A$. Since concatenation of two non-regular ...
akshay's user avatar
  • 321
9 votes
1 answer
10k views

Prove that regular languages are closed under the cycle operator

I've got in a few days an exam and have problems to solve this task. Let $L$ be a regular language over the alphabet $\Sigma$. We have the operation $\operatorname{cycle}(L) = \{ xy \mid x,y\in \...
user1594's user avatar
  • 541
13 votes
3 answers
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 ...
Hendrik Jan's user avatar
  • 30.7k
8 votes
1 answer
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 ...
Aditya Nambiar's user avatar
12 votes
1 answer
5k views

Is an infinite union of context-free languages always context-free?

Let $L_1$, $L_2$, $L_3$, $\dots$ be an infinite sequence of context-free languages, each of which is defined over a common alphabet $Σ$. Let $L$ be the infinite union of $L_1$, $L_2$, $L_3$, $\dots $; i....
Gigili's user avatar
  • 2,193
7 votes
2 answers
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 ...
Unni's user avatar
  • 71
4 votes
3 answers
4k 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 ...
Elimination's user avatar
2 votes
1 answer
3k views

are regular languages closed under division

I am trying to solve this question which appeared in previous exam paper Can someone help me what i am failing to understand For languages $A$ and $B$ define $A \div B = \{x \in \Sigma^{\ast} : xy ...
User_1234's user avatar
  • 145
20 votes
2 answers
2k views

Are context-free languages in $a^*b^*$ closed under complement?

The context-free languages are not closed under complement, we know that. As far as I understand, context-free languages that are a subset of $a^*b^*$ for some letters $a,b$ are closed under ...
Hendrik Jan's user avatar
  • 30.7k
7 votes
3 answers
449 views

First half of context-free palindromes

If $L\subseteq\Sigma^*$ is a regular language, then $\text{mir}(L) = \{ww^R \mid w\in L\}$ is context-free. This is a nice exercise. Question: does the reverse hold? Thus, if $\text{mir}(L)$ is ...
Hendrik Jan's user avatar
  • 30.7k
3 votes
3 answers
3k 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
user avatar
3 votes
1 answer
799 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 ...
Joey Kaller's user avatar
2 votes
4 answers
2k views

Regularity of “middles” of words from regular language

I need some help with the following problem. Let $L \subseteq \Sigma^*$ be a regular language. I have to prove that the language $P = \{\alpha \mid \beta\alpha\gamma \in L, \beta,\gamma \in \Sigma^*\}$...
user avatar
1 vote
1 answer
235 views

If a language is X-complete, is its complement is X-complete as well?

I'm looking for an information about closure of complexity complete classes. Is it true that any language, if the language is X-complete, then its complement is X-complete? Why? I was thinking ...
Milano's user avatar
  • 339
10 votes
2 answers
18k views

Are NP-Complete languages closed under any regular operations?

I have tried looking online, but I couldn't find any definitive statements. It would make sense to me that Union and Intersection of two NPC languages would produce a language not necessarily in NPC. ...
user16742's user avatar
  • 225
8 votes
1 answer
5k views

Are DCFLs closed under reversal?

According to this chart, DCFLs are closed under reversal. However, I am not convinced as the intuitive proof (reversing the arrows of the controlling finite state machine and switching the pushes and ...
peteykun's user avatar
  • 259
8 votes
1 answer
1k views

If L is context-free, must FH(L) be context-free?

Define $FH(L) = \{x \in \Sigma^* : \exists y \in \Sigma^* \text{ with } |x| = |y| \text{ such that } xy \in L\}$. In other words, $FH(L)$ is the set of first halves of even length strings in $L$. ...
David Smith's user avatar
4 votes
3 answers
13k 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'...
Jen Stone's user avatar
  • 165
3 votes
3 answers
8k 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 $\text{even}(L)$ is also regular. Here $\text{even}(L) = \{ \text{even}(w) : w \in L \}$, $\text{even}(w)$ is the string obtained by ...
Near's user avatar
  • 161
2 votes
1 answer
1k views

How to prove that the Myhill-Nerode equivalence classes for L are the same as for its complement?

Given language $L$, I want to show that its Myhill-Nerode equivalence classes are the same as for its complement $\overline{L}$. I am thinking of constructing a DFA $M$ for the Language $L$ so the ...
User_1234's user avatar
  • 145
2 votes
1 answer
2k views

Prove that regular languages and context-free languages aren't closed under $Perm(L)$

Let the operation $$Perm(L) = \{ w | \exists u \in L \text{ such that } u \text{ is a permutation of } w \}$$ Prove that both regular languages and CFLs aren't closed under $Perm(L)$. I've tried ...
Elimination's user avatar
1 vote
1 answer
371 views

Zigzag concatenation of two languages

Given two regular languages $A,B$ on the same alphabet $\Sigma$, I want to show that the following language is regular: $$ \{a_1b_1 \ldots a_kb_k \in \Sigma^* \mid a_1,\ldots,a_k,b_1,\ldots,b_k \in \...
WindBreeze's user avatar
0 votes
1 answer
3k views

How to construct a DFA for this?

Let $C = shuffle(A, B)$ denote the shuffle $C$ of two languages $A$ and $B$, it consists of all strings $w$ of the form $w = a_1b_1a_2b_2....a_kb_k$, for $k > 0$, with $a_1a_2 ··· a_k \in A$ and $...
James Yang's user avatar
15 votes
2 answers
1k views

Are the Before and After sets for context-free grammars always context-free?

Let $G$ be a context-free grammar. A string of terminals and nonterminals of $G$ is said to be a sentential form of $G$ if you can obtain it by applying productions of $G$ zero or more times to the ...
Alex ten Brink's user avatar
12 votes
1 answer
4k views

Prove that the complement of $\{0^n1^n \mid n \geq{} 0\}$ is not regular using closure properties

I want to prove that the complement of $\{0^n1^n \mid n \geq{} 0\}$ is not regular using closure properties. I understand pumping lemma can be used to prove that $\{0^n1^n \mid n \geq{} 0\}$ is not a ...
anthony34234's user avatar
6 votes
2 answers
1k views

Intersection of two NPDAs

Is there a way to take the interection of two NPDAs? I can't seem to find anything that can make that happen, but it seems like the type of thing that is should be relatively trival.
soandos's user avatar
  • 1,143
6 votes
2 answers
37k views

Union and intersection of a regular and a non-regular language

Lets say we have $L_1$, which is a regular language and $L_2$ which is not. Are $L_1 \cap L_2$, $L_1 \cup L_2$ , $L_1$ \ $L_2$ and $L_1 \cdot L_2$ are always non-regular languages? We know that two ...
Dick Tracy's user avatar
5 votes
2 answers
3k views

Prove that the equal-length concatenation of regular languages is context free

If A and B are regular, then prove that $A@B = \{xy \mid x \in A \text{ and } y \in B \text{ and } |x|=|y|\}$ is always context free. So I'm trying to come up with the proof that looks something like ...
romada's user avatar
  • 89
5 votes
1 answer
10k views

Why does the concatenation of the empty set with any language give the empty set? [duplicate]

Why does the concatenation of $\emptyset$ with any language give $\emptyset$. I would like to know the intuitive explanation for it.
Smrithi.Prabhu's user avatar
5 votes
2 answers
5k 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*} \...
user2524930's user avatar
3 votes
2 answers
3k views

Proving regular languages are closed under a form of interleaving

I've got the following definitions: $$\mathrm{Interleave}\,(x,y) = \{w_1\dots w_n\mid w_i\in\{x_i,y_i\} \text{ for }i=1, \dots, |x|\}$$ when $x$, $y$ and $w$ are words with $|x|=|y|$ and $w_i$ means ...
OrWn's user avatar
  • 68
3 votes
2 answers
12k views

Why is the complement of a language that is not regular also not regular?

In my lecture notes I we were given two languages and were shown that each of the two languages were not regular. The second was the complement of the first language. To show the second was not ...
seno's user avatar
  • 31
3 votes
1 answer
1k views

Space(n) not closed under Karp reductions - what about NTime(n)?

In the book on complexity by Arora and Barak, there is an exercise to show $Space(n)\neq NP$, the proof of which goes by showing that $NP$ is closed under Karp reductions, while $Space(n)$ isn't. To ...
G. Bach's user avatar
  • 2,019
3 votes
2 answers
3k 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 ...
Ryan Lee's user avatar
3 votes
3 answers
7k 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 ...
therealrootuser's user avatar
2 votes
3 answers
6k views

Proving that non-regular languages are closed under concatenation

How can I prove that non-regular languages are closed under concatenation using only the non-regularity of $L=\{a^nb^n|n\ge1\}$ ?
TT8's user avatar
  • 23
2 votes
0 answers
15k views

Is the class of non regular languages is closed under complementation?

This is the question I am asked and I am currently proving it using proof by contradiction something like this: Let's take some language L which is non regular. Let's assume compliment of L i.e. $(L^...
rohan-patel's user avatar
1 vote
3 answers
11k views

Proof that the regular languages are closed under string homomorphism

Where can I find a proof of this? Thanks!
James Shapiro's user avatar
0 votes
1 answer
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 ...
Huge's user avatar
  • 1
0 votes
1 answer
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 ...
Idonotknow's user avatar
0 votes
1 answer
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 ...
user41073's user avatar
16 votes
1 answer
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: ...
Patrick87's user avatar
  • 12.9k
15 votes
2 answers
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$ ...
corium's user avatar
  • 889
12 votes
4 answers
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 ...
user avatar
12 votes
3 answers
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 ...
user432's user avatar
  • 123
12 votes
4 answers
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 ...
Dave's user avatar
  • 279
10 votes
4 answers
1k views

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$ ...
stud1's user avatar
  • 317