Questions tagged [closure-properties]
Questions about operations on objects of some kind that result in objects of the same kind.
339
questions
1
vote
1answer
59 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
...
1
vote
1answer
58 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$?
3
votes
1answer
62 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
1answer
49 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 :...
1
vote
1answer
32 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| \...
-1
votes
2answers
41 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:
...
0
votes
1answer
33 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 ...
2
votes
1answer
43 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 ...
3
votes
2answers
739 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 ...
3
votes
2answers
44 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 ...
1
vote
1answer
40 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 ...
1
vote
1answer
111 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 \} $$
...
1
vote
1answer
36 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 ...
1
vote
1answer
84 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. ...
-1
votes
1answer
35 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
1answer
28 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?
0
votes
1answer
34 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)$?
1
vote
1answer
37 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|\...
0
votes
1answer
91 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).
0
votes
0answers
58 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
1answer
29 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 ...
0
votes
1answer
59 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
1answer
22 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 ...
0
votes
1answer
31 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 ...
1
vote
1answer
157 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 \...
1
vote
1answer
296 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 ...
4
votes
3answers
94 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
39 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
36 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
149 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
327 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
30 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
291 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
236 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=...
0
votes
1answer
90 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
629 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
1answer
152 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
98 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
316 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
31 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
118 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
645 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
58 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 $...
7
votes
3answers
290 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 ...
3
votes
1answer
62 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
97 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
102 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
76 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
107 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 ...
