Questions tagged [closure-properties]
Questions about operations on objects of some kind that result in objects of the same kind.
349
questions
4
votes
1
answer
146
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 ...
0
votes
0
answers
12
views
A simple clarification on polynomiality of sequential construction of Turing Machines through plus construction
Suppose our original $NDTM$ $M_0$ has $N<2^t$ number of acceptance paths. We construct $r$ different $NDTM$s $M_1,\dots,M_r$ with each with $m_1,m_2,\dots,m_r$ acceptance paths respectively where $...
- 17
2
votes
2
answers
60
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 ...
- 241
0
votes
1
answer
27
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
0
votes
0
answers
35
views
Closure under reducibility
Prove that for each $k ≥ 1$, each $Σ_k$ P and $Π_k$ P class of the polynomial-time hierarchy is closed (downwards) under $≤^p_m$-reducibility; i.e., if A $≤^p_m$ B and B ∈ C, then A ∈ C.
- 11
0
votes
0
answers
12
views
Is the closure of a Linear Time Property closed under union and intersection?
Defining the closure of a linear time property $P$ to be the set of all infinite traces $x$ such that the set of prefixes of $x$ is a subset of the set of prefixes of $P$, is $closure(P \cup P') = ...
3
votes
1
answer
114
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
80
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
152
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
82
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
1
vote
1
answer
303
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
...
- 35
1
vote
1
answer
60
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,822
3
votes
1
answer
95
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
79
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
70
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| \...
- 269k
-1
votes
2
answers
75
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
0
votes
1
answer
37
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 ...
- 225
2
votes
1
answer
68
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 ...
- 225
3
votes
2
answers
1k
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 ...
- 261
3
votes
2
answers
51
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
59
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
320
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
53
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 ...
- 229
1
vote
1
answer
121
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
40
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
33
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
71
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
40
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
155
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).
- 111
0
votes
0
answers
81
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
48
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 ...
- 111
0
votes
1
answer
86
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
46
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
185
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
583
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,034
4
votes
3
answers
97
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
55
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
1
vote
0
answers
42
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 ...
- 161
-1
votes
2
answers
154
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 ...
- 219
1
vote
3
answers
431
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 ...
- 21
2
votes
1
answer
32
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 ...
- 121
2
votes
1
answer
335
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 $\...
- 23
1
vote
1
answer
347
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\backslash L_2=...
- 1,547
0
votes
1
answer
116
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 ...
- 131
0
votes
1
answer
852
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 ...
3
votes
1
answer
226
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 ...
- 33
0
votes
0
answers
137
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,822
2
votes
2
answers
446
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.
- 77
0
votes
1
answer
32
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}...
- 95