Questions tagged [closure-properties]
Questions about operations on objects of some kind that result in objects of the same kind.
361
questions
0
votes
2
answers
40
views
What can i say about L1 given that L2, L1L2 and L2L1 are regular?
I found this question in one of our past exams, and I'm not to sure about the correct answer.
I have a language L1 (which i don't know anything about) and another language L2, which is regular, the ...
- 11
1
vote
1
answer
41
views
P NP R RE closures
I wrote the following table for all the closures in those classes.
is anything there incorrect?
also, would appreciate help with coNP and coRE closures. couldn't find much information about it online.
- 53
1
vote
1
answer
130
views
is the class NP closed under set difference?
I know P is closed under all Boolean operations, but what about NP?
is NP closed under set difference and symmetric difference?
is this table accurate?
Edit:
updated table:
- 53
0
votes
0
answers
18
views
Theory of computation
I am trying to look answer for this question of toc please help me find the answer.
The question is :
Construct epsilon NFA(Non deterministic finite automata) for regular expression (0+1)*1(0+1)
- 1
3
votes
1
answer
142
views
context-free shuffle for two-letter alphabets
The operation of shuffle takes two words and merges their symbols, keeping the symbols of each of the strings in the right order. It can be recursively defined by $x \parallel \varepsilon = \...
- 29.5k
0
votes
1
answer
60
views
Why these languages are closed under union or concatenation?
This is a question in my text book that I cannot understand the solution provided for that:
In each case below, give a simple descreption of the smallest set of languages that contains all the "...
- 11
0
votes
0
answers
25
views
Why is the collection of decision problems closed under set operations?
Most of the proofs of such properties that I see involve informally using algorithms or invoking Turing machines as needed. But it's not clear to me how are we using set operations on instances of ...
user153634
0
votes
2
answers
204
views
If L = L1 U L2 is regular, L2 is the complement of L1 (which means L1 ∩ L2 = Ø), and we're given that L and L2 are regular, is L1 regular?
L1, L2, and L are not finite. We're given that L and L2 are regular. However, L1 ∩ L2 is empty, since L2 is the complement of L1.
Is L1 regular under the property that regular languages are closed ...
- 1
0
votes
2
answers
85
views
Intersection of different languages
Consider L1 = Any language generated by a machine M1
L2 = Any language generated by a machine M2
Machine can be – FA, PDA, LBA, or TM
Assuming Machine M2 is more powerful than M1
Let L3 = L1 $\cap$ ...
2
votes
1
answer
93
views
Does this DFA prove closure under Perfect Shuffle?
I'm self studying Introduction to Theory of computation and I'm a bit confused about a problem definition. I'm trying to understand and verify whether my proof is correct or not.
Question: Prove that ...
- 123
0
votes
2
answers
77
views
Show for every $CFL$ $L$ that's not $REG$ exists $L_1,L_2$ with $L_1$ is $REG$ and $L_1 \subseteq L_2$ and $L_2$ is not $REG$ and $L \subseteq L_2$
i want to show that for all $CFL$ and not $REG$ languages $L \subseteq \{0,1\}^*$
exists $L_1,L_2\subseteq\{0,1\}^*$ with:
$L_1$ is $REG$
$L_2$ is $CFL$ and not $REG$
$L_1 \subseteq L_2 $
$L \...
- 7
1
vote
1
answer
66
views
Is LR(1) closed under union?
Suppose I have two LR(1) languages $L_1$, $L_2$. Is $L_1 \cup L_2$ also LR(1)?
References to proofs would be very helpful.
- 39
2
votes
0
answers
46
views
Is LR(1) closed under concatenation?
Suppose I have two LR(1) languages $L_1$, $L_2$. Is
$L_1 L_2$ (their concatenation) guaranteed to also be LR(1)?
References to proofs would be very helpful.
- 39
3
votes
1
answer
102
views
Exotic closure of regular languages
Let $L_1 \subseteq \{0,1\}^{*}$ be a regular language, and let $L_2 \subseteq \{0,1\}^{*}$ be some (not necessarily regular) language.
Show that
$$L=\left\{ \sigma_{1}\#\sigma_{2}\dots\#\sigma_{n}\mid\...
- 161
0
votes
0
answers
36
views
Regular, CFL, non-CFL infinite closures [duplicate]
I was wondering about infinite closure properties.
Are the Regular languages closed under infinite union? Infinite intersection?
Probably not, by taking $\forall n>0~~L_n=\{a^nb^n\}\in RL$, then $\...
- 239
5
votes
1
answer
231
views
Is the set of languages satisfying the pumping lemma closed under concatenation?
Let $L$ be the set of all languages that satisfy the pumping lemma, including non-regular languages that satisfy it. Is the set $L$ closed under concatenation?
I couldn’t prove it or find a ...
2
votes
2
answers
84
views
Prove irregularity of a language using closure properties
Given the language $L=\{a^{j+1}b^kc^{j-k}|j\ge k\ge 0 \}$ I need to prove that it is not a regular language using closure properties.
I was having a trouble handling $a^{j+1}$ so I tried to prove this ...
- 261
0
votes
1
answer
44
views
If $L$ is finite and $R$ is not regular, then $R\cup L$ is not regular
Prove/Disprove: If $L$ is finite and $R$ is not regular, then $R\cup L$ is not regular.
I think that this one is true, but I am stuck:
Since $R$ is not regular, it is infinite, so $R \cup L$ is also ...
- 5
3
votes
1
answer
263
views
Is NL closed under complemenrt?
I am trying to understand if NL is closed under complement or not. By NL i mean the non-deterministic-logspace complexity. I suppose that the answer is linked to the fact that we don't even know if L =...
0
votes
1
answer
166
views
Prove that $\{xyz \mid zyx \in A \}$ is regular if $A$ is regular
Does the following work and is there anything possibly simpler?
Let $X = (Q, \Sigma, \delta, s, F)$ be a DFA for $A$.
Intuitively, we want to "remember" (or guess) two states $p$ and $q$ ...
-2
votes
2
answers
697
views
Prove that the class of regular languages is closed under three operation
We define an operation three on strings as three(c1c2c3c4c5c6...) = c3c6... then the above-described definition is extended to languages. Prove that the class of regular languages is closed under this ...
- 1
0
votes
1
answer
249
views
Prove the class of regular languages is closed or not closed under the operations below
Suppose $A$ and $B$ are both languages over $\Sigma=\{0,1\}$. We use $n_0(x)$ and $n_1(x)$ to represent the number of $0$s and $1$s in the string $x$ respectively. Consider the following two ...
- 3
2
votes
1
answer
1k
views
Why are Recursive Enumerable Languages closed under union?
Union of two REL is closed under union. I don't understand how is it closed. I followed this link. The have stated:
Here the trick is to simulate both M1 and M2 “simultaneously”. In other words, we
...
- 45
1
vote
1
answer
74
views
Is there distinction between $(C/poly)\cap(coC/poly)$ and $(C\cap coC)/poly$?
Let $C$ be an uniform complexity class for example $NL$ or $NP$. Is there distinction between $(C/poly)\cap(coC/poly)$ and $(C\cap coC)/poly$?
- 2,861
3
votes
1
answer
143
views
Closure of context-sensitive languages under inverse language substitution
We define language substitution for a Context-Sensitive Language (CSL) $S$ over an alphabet $\Sigma$ is a map from $\Sigma$ into CSL's, for example: $f(abc) = L_1(a) L_2(b) L_3(c)$ such that (I guess) ...
2
votes
1
answer
156
views
Proof that class of languages accepted by DPDA by empty stack is not closed under union
My first intuition was to take two languages $L_1$ and $L_2$ (symbol $d$ at the end is to fulfill prefix property):
$$L_1 = \{ a^i b^i c^j d : i,j \ge 0 \} \mathrm{\ \ and\ \ } L_2 = \{ a^i b^j c^j d :...
- 125
1
vote
1
answer
393
views
Closure of context-free languages under left-half [duplicate]
The regular languages are known to be closed under the operation "left half":
$$
\operatorname{left}(L) = \{ x \in \Sigma^* : xy \in L \text{ for some } y \in \Sigma^* \text{ s.t. } |x|=|y| \...
- 274k
-1
votes
2
answers
289
views
Prove by contradiction that the language with unequal number of a's and b's is not regular
Consider the language
$$L = \{w \mid w \text{ has an unequal number of a’s and b’s}\}$$
where Σ = {a, b}.
Prove that L is not regular.
Hint: Try proof by contradiction.
Would this be the right Answer:
...
- 33
1
vote
1
answer
63
views
Classes of Functions Closed Under Polynomial Composition - Papadimitriou Exercise 7.4.4
I am studying Computation complexity using Papadimitrious's book: "Computational Complexity".
I am trying to do Problem 7.4.4:
"Let $C$ be a class of functions from nonnegative ...
- 300
2
votes
1
answer
127
views
Definition of Closed Under Left Polynomial Composition
I am studying Computation complexity using Papadimitrious's book: "Computational Complexity".
While doing Problem 7.4.4, I came across the definition of what it means for a class of ...
- 300
3
votes
2
answers
2k
views
Given L is a regular language, prove that Perm(L) is Context-Free
Given a regular language $L$ defined over $\Sigma = \{0, 1\}$. We define a new language $$Perm(L) = \{w \mid \exists x \in L, w \in perm(x)\}, $$ where $perm(x)$ is the set of all permutations of the ...
- 271
3
votes
2
answers
66
views
Language equivalency for modified CFG closed over intersection
Suppose "CFG+" was created, where it is identical to standard context-free grammars in every way, but rather than rules being limited to unions, was also closed over intersections, both ...
- 133
1
vote
1
answer
80
views
Show that the Language is irregular
I was solving some problem from past test, there was this question:
Use the closure property of regular language to show the language $L$ is not regular
$$L =\{ a^3 b^n c^{n-3} \mid n>3\} $$
I ...
- 13
1
vote
1
answer
1k
views
Regular languages closed under prefix operation
Suppose that $D$ is a regular language over an alphabet $A$. How can I prove that the following language is also regular?
$$ \mathrm{LANGUAGE}_2(D) := \{ d \mid d,t \in A^* \text{ and } dt \in D \} $$
...
- 21
1
vote
1
answer
60
views
Using closure properties, prove that $L=\{a^kb^ra^m|k,r,m\ge0 \text{ and } m=k+r\}$ is not regular
I'm trying to prove that $L=\{a^kb^ra^m|k,r,m\ge0 \text{ and } m=k+r\}$ is not regular and, although it's trivial to prove it via pumping lemma, I'm having troubles trying to find a way to prove it ...
- 239
1
vote
1
answer
198
views
Which closure properties are always valid between regular, context-free and non context-free languages?
I am making a scheme that respresents some closure properties (union, intersection, complement and concatenation) for regular languages, context-free languages, decidable languages and RE languages. ...
- 343
-1
votes
1
answer
82
views
Prove that the class of regular languages is closed under the Kleene + operation. That is, show that if L is regular, then so is $L^{+}$
This is my attempt at a proof:
Let $E$ be a $REGEX$ accepting $L$. We claim the $REGEX$ $E^{'} = E^{+}$ accepts L. i.e. $L(E^{+}) = (L(E))^{+}$
$L^{+}$ is regular since there is a $REGEX$ $E^{+}$ ...
0
votes
1
answer
36
views
How do i prove this language is regular? [duplicate]
I have this language {0+1+0+} and i need to prove it is regular,i had the idea to use the closure properties but i can find any regular languages to unify perhaps.Any ideas?
- 13
0
votes
1
answer
115
views
Relationship between Kleene Star of a subset of regular language and the regular language
If $L(R_1) \subseteq L(R_2) \subseteq L(R_3)$ then $L(R_1)^* \subseteq L(R_2)^* \subseteq L(R_3)^*$. Does this also imply that $L(R_1)^* \subseteq L(R_3)$?
- 11
1
vote
1
answer
52
views
Regularity of a language constructed from a know regular language
I'm working through so textbook questions on regular languages, and came across a problem that amounts to showing the following language is regular, given that $A$ is a regular language:
$$
\{x|\...
- 63
0
votes
1
answer
252
views
PDA kleene star construction
I know how to prove that CFL are closed under kleene star operation using CFG.
I can't find online or in class notes a proof using PDA.
I would appreciate description of the basic idea (not formal).
- 109
0
votes
0
answers
107
views
How to show that language L is NOT context-free?
True or false: To show that a language L is not context-free, one can alternatively show that the union between L and a known context-free language is not context-free.
I know that you can prove ...
1
vote
1
answer
108
views
closure of Context free grammer to homomorphism using PDA
I was looking online, on sipser book, and on lecture notes and I can't find a proof to closure of context free languages to homomorphism that using PDA instead of CFG.
I'm not looking for a full and ...
- 109
0
votes
1
answer
140
views
Complement of $0^n1^n | n \in \mathbb{N}$
I know why A is irregular by Closure properties of irregular language. I also know the complement of $ \{ 0^n 1^n | n \in \mathbb{N}\}$ is $A = \{ 0^i 1^j| i \neq j\} \cup (0 \cup1)^*(1)(0 \cup1)^*0(0 ...
2
votes
1
answer
25
views
Decidability of a language and inclusion between two other languages
I have this assignement that asks to say if the following statement is true or false, and possibly justifying the answer:
"Let L₁, L₂ be decidable languages.
For every language L s.t. L₁ ⊆ L ⊆ L₂, L ...
- 21
0
votes
1
answer
70
views
How to define an automata for zig zag concatenation? [duplicate]
I have two DFAs one for language A and one for language B.
I'm asked to make an FDA that is the zig-zag concatenation of letters of A and letters of B.
This is described by the following: {w: w = $a_1 ...
- 251
1
vote
1
answer
303
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 \...
- 251
1
vote
1
answer
1k
views
Strings of infinite length?
Suddenly a thought came to my mind and I thought of resolving it as follows.
We know that:
String is a finite sequence of symbols from an alphabet $\Sigma$
i.e. we cannot have an infinite sequence ...
- 1,092
4
votes
3
answers
99
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$ ...
- 207
1
vote
0
answers
72
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 (...
- 11