Questions tagged [closure-properties]
Questions about operations on objects of some kind that result in objects of the same kind.
3
votes
2answers
45 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 ...
2
votes
1answer
36 views
How to use homomophism in closure proofs?
I am having a hard time understanding homomorphism. All I seem to understand is that it is a substitution. When I look at examples of proving closure of a particular operation over a regular language, ...
0
votes
1answer
36 views
operate infinite times over a regular language
Let $T:Σ^*\to Σ^*$ be an operation such that $T(L)$ is regular for all regular languages $L \in Σ^*$.
Is it possible to prove $T^∞(L)$ is regular?
$T^∞(L)=\bigcup_{i=1}^{\infty}{T^{i}\left(L\right)}$...
1
vote
1answer
38 views
Why proving that two languages used to merge into a regular language are not necessarily regular isn't possible with closure properties?
Let $L$ be a regular language over alphabet $\Sigma$. $L$ is the result of merging $2$ languages letter by letter that is for $a_1a_2...a_n\in L_1, b_1b_2...b_n\in L_2, L=a_1b_1a_2b_2...a_nb_n$. $\...
2
votes
2answers
56 views
How to prove certain parts of one regular language restricted by another regular language is also regular?
I’ve encountered the following difficult question that I don’t know how to solve.
$L_1$ and $L_2$ are regular languages over the same $\Sigma$. $$\begin{align}L^\wedge=&\{σ_1σ_2...σ_n\mid n\ge1, \...
0
votes
2answers
49 views
if $L_1$ and $L_2$ are languages over the same alphabet and $L_1 \cap L_2$ is context free, at least one of them must be context free
I am having a hard time understanding if this would be true or false, can someone point me in the right direction?
3
votes
1answer
38 views
unambiguous context-free languages and complementation
I was considering the following two natural questions about the relationship between unambiguity and complementation for the class of context-free languages:
Is the complement of an unambiguous ...
3
votes
3answers
111 views
If $L$ is a regular language, then $s(L)$ is also regular
...where $s$ is a substitution that replaces each symbol of each string in $L$ with a regular expression.
For example, if $L=a^*b$ and $s(a) =ab, s(b) = b^*$, we have $s(L) = (ab)^*b^*$.
My ...
2
votes
1answer
89 views
Closure of regular languages under deleting a 1 from each even run of 1s
Let $R$ be a regular set over the alphabet $\{0, 1\}$. Give a machine construction to prove that the set obtained by deleting one 1 from each even length block of 1’s is also regular, and using ...
2
votes
2answers
91 views
Finding if the given language is regular or not
I have the language $$L = \{a^mb^nc^o| \, m + n + o > 5\}$$
where $m,n,o$ are non-negative integers.
I have to find whether the language is regular or not.
My attempt:
I feel it should be non ...
0
votes
1answer
109 views
Finite state automaton for the reverse of the language, and multiple starting states
I am studying about Finite State Automaton, and I found that the when reversing a language (i.e., transforming $L$ to $L^R$), I have to add new start state. Why is that?
Also, can a Finite State ...
2
votes
1answer
61 views
Show that RP is closed under concatenation
I'm trying to prove the following problem:
Show that $RP$ is closed under concatenation
Now, let's say that the two languages are $L_{1}$ and $L_{2}$ (both in $RP$). Then I accept a word iff the ...
3
votes
1answer
108 views
Is the union of NP Complete language and a finite language (in P) NP Complete?
Let there be a language $A$ which is NP complete and language $B$ which is a finite language, is the union of $A \cup B$ NP complete language?
5
votes
1answer
86 views
Have any natural complexity classes been proven not to be closed under complement?
Many important (non-deterministic) complexity classes like NP are believed not to be closed under complement. But have any of them been proven not to be?
I'm sure one could construct some contrived ...
1
vote
1answer
33 views
Proving that Pre(L) is regular using automatas: Should I prove that Pre(L) is the semantic of the new automata?
Let $L$ be a regular language, and $Pre(L)$ be the set of all words that are prefix of some word in $L$. Prove that $Pre(L)$ is regular.
My proof:
Let $M = (\Sigma, Q, \delta, q_0, F)$ be an ...
2
votes
2answers
56 views
Proving $L'=\{uv : u \in L \; \land v \in L^R \; \land |u|=|v|\}$ is a CFL with closure properties [duplicate]
Given a language $L$ over $\Sigma=\{a,b\}$ let us define
$L'=\{uv : u \in L \; \land v \in L^R \; \land |u|=|v|\}$
Prove: if $L$ is regular, then $L'$ is a context free language.
I know how to ...
0
votes
0answers
32 views
Show that the set $\{uv | u \in L \ and\ v \notin L\}$ is regular
The full question is:
Let $L$ be a regular language over $\{a, b, c\}$. Show that the set $\{uv\ |\ u \in L \ and\ v \notin L\}$ is regular
I have the following answer, but I'm not sure if it's ...
0
votes
0answers
32 views
Dependency of operations of languages
I've struggled in the closure properties of the general class of languages because I couldn't use any automata concept and grammars.
In specific, I'm interested in dependency of operations.
(The ...
4
votes
1answer
536 views
Proving that if L is regular. Then L′ = {ww : w ∈ L} is regular
I believe this statement to be true. And here's my reasoning:
Based on regular languages properties, the concatenation of two regular languages is regular. And since L′ = L · L, it follows that L′ ...
0
votes
1answer
199 views
Why is the intersection of these two Languages Recursively Enumerable, not Recursive?
I am only several days exposed to computational theory, so my understanding is quite slim: in a question, it says that for a regular language L1 and a recursively enumerable but not recursive language ...
0
votes
1answer
301 views
Class P is closed under concatenation
Proving that Class P is closed under concatenation.
The answer is given below:
But I do not know why stage 2 is repeated at most O(n), could anyone explain this for me please?
1
vote
1answer
93 views
Proving that $\{0^i10^i : i \ge 1\}$ is non-regular, using only closure results
I have been stumped on the following question for a few hours now, I feel like I am missing some "aha" moment.
$\text{Suppose that } \{ a^nb^n : n \ge 1 \} \text{ is non-regular.}$
$\text{Prove ...
1
vote
1answer
484 views
Is the union of two non-regular context-free languages always non-regular?
I had this question in my HW:
Prove of disprove: If $L_1$ and $L_2$ are non-regular context free languages then $L_1 ∪ L_2$ is not regular.
My intuition is that it is wrong. I thought about the ...
1
vote
0answers
91 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 $ = ...
3
votes
2answers
86 views
Constructive Proof on Regular Languages
As an assignment, I've to come up with constructive proofs for the following languages to be regular supposing A and B are two distinct regular languages.
$$L_1=\{w│w^R∈A\}$$
$$L_2=\{w│w=a_1 b_1,…,...
0
votes
1answer
806 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 ...
5
votes
2answers
66 views
Can the regular image of a context-free language be undecidable?
I just need to know the truth or falsity of a simple statement.
Let $L_1$ be a context-free language over an alphabet which contains some number of characters $\Sigma$, as well as a single, special ...
1
vote
2answers
129 views
XOR of two NP-Complete languages
Given two NP-Complete languages A and B, show that the language:
$L = A\bigoplus B =\{a\bigoplus b \mid a \in A, b \in B, |a|=|b|\}$
is not necessarily NP-Complete.
Remember $a\bigoplus b$ when $|...
4
votes
1answer
100 views
Complement of Mealy machine
How could one reasonably define and construct the complement of a deterministic Mealy machine?
My intuition is that the complement should give exactly the opposite of output strings after a specific ...
2
votes
1answer
91 views
context free grammar not closed under relative complement using product construction of pda and dfa
Hello friends need a bit of help,
I Know that
given: $$L_1 \in L_{cfg}, L_2 \in L_{reg}$$ $$L_2/L_1\notin L_{cfg}$$
because if it was contex free it would imply that $L_{cfg} $ is closed under ...
4
votes
1answer
137 views
How to prove that a transformed language is regular using an NFA
I am trying to prove that if a language $ L $ of binary strings (i.e. a subset of [01]*) is regular then so is the transformed language $ plus (L) $ consisting of ...
0
votes
0answers
164 views
Closure under swap operator
I am stuck on this problem and unsure how to proceed. I understand how to show that two languages are closed under regular operators, but not one like the 'swap' operator.
Let swap : {a, b}∗ → {a, b}∗...
1
vote
2answers
79 views
Does this proof work for infinite regular languages
My proof was deemed false because it does not work for infinite regular languages, but I don't understand why.
Prove: "If we remove one string from any nonempty regular set, the resulting set is ...
0
votes
0answers
34 views
Why is it not obvious $coNP = NP$? [duplicate]
I can't find a mistake in reasoning : Let $M_1$ NTM (Non Deterministic Turing Machine) that solves $L$ in polynomial-time. So then $x \in L \Leftrightarrow M_1(x) = 1$. Finally our new NTM $M_2$ that ...
1
vote
1answer
472 views
Closure of Turing-recognizable languages under homomorphism
I've proven that the Turing-recognizable languages are closed under concatenation and I need to show that they are closed under homomorphism.
But what's really the difference? Doesn't closure under ...
0
votes
0answers
10 views
Choose a specific regular language to prove a language is not regular [duplicate]
I've tried a few tricky languages such as D = { w | w has an equal number of occurences of 01 and 10 as substrings} but I don't have the means to prove this one as being not regular (and I cannot ...
0
votes
0answers
20 views
Give an example of a language where both L and ¬L is not semidecidable? [duplicate]
I know ¬H is not semidecidable so I was thinking of creating a language that combines both H and ¬H. Therefore L would be undecidable for ¬H and ¬L would be undecidable for H. Is this a proper ...
1
vote
0answers
129 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 ...
0
votes
1answer
232 views
What happens during the DFA reversal construction if the initial state is final?
The steps in reversal of DFA are :-
Make final state as initial state. If there are more than 1 final state, then make a new start state with epsilon transitions to these states.
Change all initial ...
1
vote
4answers
561 views
Why can't we say that NP is closed under complement given that we can say it is closed under intersection
I found online solutions which prove the closure of NP under intersection in the following way: given machines $M_1,M_2$ for accepts nondeterministically languages $L_1,L_2$, we construct the ...
0
votes
1answer
53 views
On clarification of intersection of classes definition
How do you define $\oplus P\cap PP$?
$L\in\oplus P$ iff $\exists\mbox{ NTM }M:\forall x,\#acc_M(x)\mod2\equiv0$.
$L\in PP$ iff $\exists\mbox{ NTM }M:\forall x,\#acc_M(x)>\#rej_M(x)$.
Consider ...
0
votes
1answer
48 views
Using closure properties to show that $L_1=\{a^lb^mc^m|l,m\ge 0\} \cup L(b^*c^*)$ is regular or not
i'm trying to figure out whether this Union $\left [ L_1=\{a^lb^mc^m|l,m\ge 0\} \cup L(b^*c^*)\right]=K$ is regular or not, now since regular languages are closed under intersection, so i assume $K$ ...
0
votes
1answer
52 views
Closure of a CFL under specific operation
Consider the following operation on language $L$:
$\mathrm{inv}(L) = \{ xy^Rz \mid x,y,z\in \Sigma^*, xyz\in L \}$
I understand that if $L$ is regular, then $\mathrm{inv}(L)$ is regular too, and ...
2
votes
1answer
207 views
If $L$ is recursively enumerable (or recursive) then so is $L′$
Given a language $L \subset \{0, 1 \}^*\#\{0, 1 \}^*$ and a language $$L'=\{u \in \{0,1\}^* | \textrm{ There is a word }w \in \{0,1\}^* \text{, so } u\#w \in L\}$$
Prove or disprove:
If $L$ is ...
0
votes
1answer
274 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$ ...
1
vote
1answer
288 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 ...
0
votes
2answers
181 views
Are the regular languages closed against injecting single letters?
Let $L$ an arbitrary regular language and
$\qquad L_2 = \{uav : uv \in L\}$.
Am I correct to say that this language is not regular by saying:
$L$ has an even number of $a$'s. So $u$ and $v$ have ...
1
vote
1answer
302 views
Complement of DPDA
I read that we can find complement of DPDA by just complementing(toggling) the states of DPDA.
Why can't we do the same with NPDA ?
Also is DCFL closed under complement just because we can toggle ...
0
votes
1answer
225 views
If L1 ⊆ L2 and L2 is regular, then L2 − L1 is regular [closed]
I'm having trouble being 100% sure about this answer. I feel like it's false but I'm having trouble coming up with a complete answer. Can someone explain this step by step?
Thanks.
2
votes
1answer
271 views
Closure property of recursively enumerable language
I read that recursively enumerable languages are closed under intersection but not under set difference.
We know that, $A \cap B = A - ( A - B)$.
Now for LHS (left-hand side) to be closed under ...
