Questions tagged [closure-properties]
Questions about operations on objects of some kind that result in objects of the same kind.
306
questions
1
vote
1answer
42 views
Quotient of languages, regular quotient and their closedness
Left quotient is defined as below at this link:
Left quotient of $L1$ by $L2$:
$L1\backslash L2:= \{u\in \Sigma^*|vu\in L1$ for some $v\in L2 \}$
Wikipedia defines it as follows:
$L_1\...
0
votes
1answer
35 views
Are models of computation closed under composition?
It's common to ask whether a particular class of languages $\mathcal{C} \subseteq \mathcal{P}(\Sigma^*)$, for some alphabet $\Sigma$, is closed under complement, or union, or intersection, or ...
0
votes
0answers
75 views
If $L$ is a regular language then so is $L/a =\{w | wa ∈ L\}$, where $L$ is a language over $\Sigma$ and $a \in \Sigma$
I'm trying to work out a proof by construction that $L/a$ would be regular.
$a$ is any final symbol at the end of an accepted string, so I figured the only part of the machine that would have to be ...
2
votes
1answer
52 views
How can the union of two 'context-free but not regular' languages be regular?
I cannot understand how the union of two languages which are context-free but not regular, can result in a regular language:
If $L_1$ and $L_2$ are 'context-free but not regular' languages, defined ...
0
votes
0answers
43 views
Intersection of decision problems?
Say we have two problems $\Pi_1\in NP$ and $\Pi_2\in coNP$. Where does $\Pi_1\cap\Pi_2$ live?
1
vote
1answer
33 views
Is the difference of two context-free languages still context-free?
i am asking myself the following question:
Assuming: A and B are context-free languages, then A - B (difference) must also be context-free language, right?
but I do not know how to prove it.
0
votes
1answer
22 views
Getting from one language to the other using closure properties(automata) [duplicate]
I am trying to deduct how i can, using closure properties, deduct that since the following language is not context free $$L=\left\{abc^{i_1}bc^{i_2}...bc^{i_{2m}}def^{j_1}ef^{j_2}..ef^{j_{2n}}ghq^{k_1}...
1
vote
2answers
76 views
DSPACE(f(n)) closed under complement
I think you can create the complementary language that is an element of DSPACE($f(n)$), where $f(n) \geq \log(n)$ by adding a step to the algorithm that reverses the answer. By that the function $f(n)$...
0
votes
2answers
135 views
Proving that L is not regular using closure properties
I need to show that the following language is not regular.
$$L = \{\ ab^jc^j\ |\ j \geq 0\ \}\ \cup\ \{\ a^ib^jc^k\ |\ i, j, k \geq 0 \ and\ i \neq 1\ \}$$
There is also a hint that it cannot be ...
2
votes
2answers
46 views
Calculate the number of distinct permutations of length n in the closure of a language
I am studying a distance CS course, but there is no tutor available, so I would appreciate your help...
Consider the language $S = \{a, aa, ab\}$
How many distinct words of length $n$ will appear in $...
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 ...
2
votes
1answer
45 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
40 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
60 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
69 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
52 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
58 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
191 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
134 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
103 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
225 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
120 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
210 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
125 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
38 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
102 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
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
693 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
523 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
676 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
249 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
795 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
109 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
140 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
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 ...
6
votes
2answers
87 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
150 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
151 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
142 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
209 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
234 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
98 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
36 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
578 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
26 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
172 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
453 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
871 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
56 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 ...
