Questions tagged [closure-properties]
Questions about operations on objects of some kind that result in objects of the same kind.
76
questions
12
votes
7answers
1k 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-...
13
votes
2answers
1k 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)=\{...
9
votes
3answers
2k 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-...
6
votes
2answers
19k 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 ...
3
votes
3answers
2k 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 ...
7
votes
1answer
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 ...
8
votes
1answer
6k 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 \...
2
votes
1answer
2k 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 ...
20
votes
2answers
1k 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 ...
1
vote
1answer
137 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 ...
8
votes
1answer
1k views
Kleene star of an infinite unary language always yields a regular language
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 ...
8
votes
1answer
3k 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 ...
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
3answers
3k 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
1answer
366 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 ...
2
votes
3answers
354 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^*\}$...
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*}
\...
8
votes
3answers
2k views
Demonstrate that DPDA is closed under complement by construction
I've been trying for quite some extended time to find a construction so that I can formally demonstrate that a deterministic PDA is closed under complementation. However, it happens that every idea I ...
3
votes
2answers
2k 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 ...
11
votes
3answers
4k 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 ...
3
votes
1answer
620 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 ...
1
vote
3answers
7k views
Proof that the regular languages are closed under string homomorphism
Where can I find a proof of this? Thanks!
14
votes
2answers
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 ...
11
votes
1answer
3k 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 ...
6
votes
2answers
426 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.
6
votes
3answers
150 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 ...
3
votes
2answers
1k 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
-1
votes
1answer
1k 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 $...
11
votes
1answer
3k 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....
2
votes
2answers
2k 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\}$ ?
1
vote
1answer
3k 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.
1
vote
1answer
5k 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 ...
0
votes
1answer
212 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 ...
0
votes
1answer
76 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 ...
0
votes
1answer
2k 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 ...
8
votes
2answers
11k 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. ...
12
votes
4answers
13k 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 ...
7
votes
4answers
10k views
Is the class NP closed under complement?
Is the class $\sf NP$ closed under complement or is it unknown? I have looked online, but I couldn't find anything.
2
votes
2answers
16k 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 ...
6
votes
1answer
1k views
Closure properties of linear context-free languages
Under what operations are linear context-free languages closed? Suppose $L_1, L_2$ are two linear context free languages. Are there any guarantees about $L_1 \cup L_2$, $L_1 \cap L_2$, $\overline{L_1}...
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 ...
3
votes
2answers
8k 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 ...
7
votes
1answer
4k views
How to prove that context sensitive languages are closed under intersection and complement?
This is a question from the exam of our "Automata and Formal Languages" course. There is a question where asked to prove or disprove that any "relative complement" operation between two context ...
5
votes
3answers
11k 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 ...
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 ...
13
votes
2answers
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$ ...
10
votes
1answer
372 views
Constructing all context-free languages from a set of base languages and closure properties?
One way of looking at regular expressions is as a constructive proof of the following fact: it's possible to construct the regular languages by starting with a small set of languages and combining ...
8
votes
1answer
566 views
Proving closure under complementation 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: ...
8
votes
2answers
302 views
Regularity of the exact middle of words from a regular language
Let $L$ be a regular language.
Is the language $L_2 = \{y : \exists x,z\ \ s.t.|x|=|z|\ and\ xyz \in L \}$ regular?
I know it's very similar to the question here, but the catch is that it's not a ...
7
votes
1answer
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 ...
