Questions tagged [closure-properties]

Questions about operations on objects of some kind that result in objects of the same kind.

Filter by
Sorted by
Tagged with
1 vote
1 answer
43 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 ...
0 votes
2 answers
54 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
0 votes
1 answer
48 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.
1 vote
0 answers
31 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.
3 votes
1 answer
83 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
18 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 $\...
  • 241
5 votes
1 answer
175 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 $...
2 votes
2 answers
63 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 ...
0 votes
1 answer
38 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
13 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
150 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
100 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
345 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 ...
0 votes
1 answer
105 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
462 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
1 answer
61 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,824
3 votes
1 answer
102 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
104 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
1 answer
94 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
2 answers
95 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
1 answer
44 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
1 answer
80 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
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 ...
  • 251
3 votes
2 answers
57 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
1 answer
65 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
1 answer
452 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
1 answer
56 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
131 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
49 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
97 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
43 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
165 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
84 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
54 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
102 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
51 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
1 answer
232 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
1 answer
700 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
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
57 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
44 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
2 answers
156 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
3 answers
450 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 ...
2 votes
1 answer
344 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
394 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,557
0 votes
1 answer
119 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 ...

1
2 3 4 5
8