Questions tagged [closure-properties]
Questions about operations on objects of some kind that result in objects of the same kind.
313
questions
3
votes
3answers
61 views
$\mathcal{G} = \{ v_2 v_4 \ldots v_{k} : v_1 v_2 v_3 v_4 \ldots v_{k-1} v_{k} \in \mathcal{L}, \text{ $k$ even} \} $ is context free language
Let $\mathcal{L}$ be context free language over alphabet $\Sigma$. Define $\mathcal{G}$ as
$$\mathcal{G} = \{ v_2 v_4 \ldots v_{k} : v_1 v_2 v_3 v_4 \ldots v_{k-1} v_{k} \in \mathcal{L}, \text{ $k$ ...
1
vote
0answers
21 views
$L = \{\alpha^i \beta^j \gamma^k \vert i,j,k \in \mathbb{N}_0, (i=1) \Rightarrow (j=k)\}$
I am asking this question here, because I am not allowed to comment on the thread that I am actually interested in, but maybe someone can still help me?
I alredy found an anwser to the Problem above (...
1
vote
0answers
29 views
Decidability of equality of expressions involving exponentiation
Let's have expressions that are finite-sized trees, with elements of $\mathbb N$ as leaf nodes and the operations {$+,\times,-,/$, ^} with their usual semantics as the internal nodes, with the special ...
-1
votes
2answers
126 views
Why L' is not regular?
$$L'=\{ww|w\in L\}$$
I need to give an example of regular language L for which the concatenation of 2's $w$ gives $L'$ which is not regular.
How can I give such an example if according to closure ...
1
vote
3answers
136 views
Show that if A is regular, then the subset containing only even language strings, is also regular
A language A, even(A) is the subset of A consisting of those strings in A of even length:
even(A) = { x∈A | |x| is even}
I need to use closure properties show ...
2
votes
1answer
27 views
Policies for handling symbols leaking out of a lexical scope
Suppose it's possible for a symbol to escape the scope in which it is defined. What are considered the possible policies for handling that? I mean possible in the sense of what choices of language ...
2
votes
1answer
113 views
Prove/disprove: If $𝐿_1$ is a finite language but not empty and $𝐿_2$ is NOT regular then $𝐿_1 \circ 𝐿_2$ is NOT regular
That what I have so far, but I am not sure at all.
Assume toward contradiction that $𝐿_1 \circ 𝐿_2$ is regular.
Define $\Sigma' = \{\sigma'|\sigma\in\Sigma\} $.
Define a regular substitution $\...
1
vote
1answer
58 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
51 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
1answer
163 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
71 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
46 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?
2
votes
2answers
115 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
24 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
92 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
205 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
49 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
194 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
48 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
42 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
74 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$. $\...
3
votes
2answers
83 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
53 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
67 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
290 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
162 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
106 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
258 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
153 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
301 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?
6
votes
1answer
152 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
40 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
150 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
33 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
936 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
866 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
973 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
271 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
913 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
129 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
206 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
98 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
210 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
181 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
183 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
228 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
346 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
102 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
39 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 ...
