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
0
votes
1answer
595 views

Proof that finite automata is closed under intersection

I'm looking at a proof that says that: If $M_1=(Q_1, \Sigma , q_1, A_1, \delta)$ and $M_2=(Q_2, \Sigma , q_2, A_2, \delta)$ are two finite automata(FA) then $M=M_1 \cup M_2$ is also an FA. We define $...
0
votes
2answers
2k views

Proving that context-free languages are closed under inserting symbols [closed]

This is a theoretical computer science question, regarding the proof of whether or not context-free languages are closed under an operation. This means basically that any context-free language which ...
0
votes
1answer
1k views

Proof that recursive languages are closed under concatenation

I can't figure out a proof that recursive languages are closed under concatenation. I know this is easy for most of the people but unfortunately my professor is not very good at explaining the ...
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 ...
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)}$...
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?
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 ...
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?
0
votes
1answer
563 views

What happens during the DFA reversal construction if the initial state is final?

The steps in reversal of DFA are :- Make final state as initial state. If there are more than 1 final state, then make a new start state with epsilon transitions to these states. Change all initial ...
0
votes
1answer
56 views

On clarification of intersection of classes definition

How do you define $\oplus P\cap PP$? $L\in\oplus P$ iff $\exists\mbox{ NTM }M:\forall x,\#acc_M(x)\mod2\equiv0$. $L\in PP$ iff $\exists\mbox{ NTM }M:\forall x,\#acc_M(x)>\#rej_M(x)$. Consider ...
0
votes
2answers
227 views

Show that RE is closed against right-quotient

I have a problem that I have no idea how to approach. I've been looking at using mapping reductions, but I can't find a way to apply it. Assume some alphabet $\Sigma$ and two languages $A, B \...
0
votes
1answer
517 views

How do I prove that a language is regular? [duplicate]

In order to prove that the following language is regular, would I use a pumping lemma? The set $A$ of all strings that are substrings of some string in $L$, where $L \subseteq\Sigma^*$. $L$ Must be ...
0
votes
2answers
134 views

If L is a regular language then the language replace(L,σ,τ) is also regular

I am stuck at the following problem: Prove that if $L$ is a regular language over some alphabet $\Sigma$ and that $\sigma, \tau \in \Sigma$, Then the language $replace(L,\sigma,\tau)$ is regular. ...
0
votes
1answer
353 views

Closure properties of finite state transducers

Given $T_1, T_2\colon \Sigma^* \to \Gamma^*$ ($\Gamma$ is output alphabet), let $\Delta(T_1, T_2)$ consist of all input strings $w \in Σ^*$ where $T_1(w) \neq T_2(w)$. Prove that FSTs ...
0
votes
1answer
214 views

Infinite Union of non-regular languages

Is infinite union of non-regular languages $L_i$ that form a chain such that $L_i\subseteq L_{i+1}$ always non-regular? Or is there a possibility that it be ever regular? Is there an easy way to ...
0
votes
1answer
145 views

How to prove the linear context free languages are closed under gsm mapping?

I'm stuck on the following question: How to prove the linear context free languages are closed under gsm mapping?
0
votes
2answers
165 views

Proving that a derived language is regular [duplicate]

Suppose I have a DFA recognizing a regular language $L$, how do I prove that $$\text{lefthalf}(L)= \{ w_1 \mid \exists w_2 \in \Sigma^* ,w_1w_2 \in L \land \|w_1\| = \|w_2\| \}$$ is also a regular ...
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 ...
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}...
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
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 ...
0
votes
1answer
231 views

Infinite Union of Recursive language

Question Is Infinite Union of Recursive language is Recursive? I know it is already posted here, but the i am not getting answer also i want to know if my approach is correct. My Approach/Doubt $...
0
votes
1answer
557 views

Finite substitution and regular closure properties

I'm not sure if I get the following definition right: 1.Def: A map $\varphi: \Sigma^{*} \rightarrow 2^{\Delta^{*}}$ is called Substitution iff: $\forall u,v \in \Sigma^{*}: \varphi(uv)=\varphi(u) \...
0
votes
1answer
359 views

Reflexive transitive closure = (zero or more) Kleene star?

In Alloy Tutorial they denote some reflexive transitive closure with Kleene star saying that they admit zero or more elements at that position. ...
0
votes
1answer
58 views

How to prove that the decidable languages are closed against iteration only by enumerators?

We have the $L\in R$, how can we prove that $L^*\in R$ only by enumerators? I try to use induction, but as I understand I wrong... I'd like to get any help!
0
votes
1answer
774 views

If a language is context free, then its complement is decidable

I am having a bit of trouble figuring this out. If L is context-free then we know it is decidable. The class of decidable languages is closed under complement thus, $L$ $\cap$ $L^{c}$, therefore $L^{c}...
0
votes
1answer
6k views

prove language is Context-free and not regular [duplicate]

I have to prove that $\left \{ a, b \right \}^{\ast} - \left \{ a^ib^i | i\geq 0 \right \}$ is a context-free language and it's not regular. So far I've got that this language is not regular because ...
0
votes
1answer
189 views

Confusing example of a language which may be Context-free or not context-free

Hi so consider the language $L= \{(0^i)(1^j)\mid i=k*j \text{ for some positive }k\}$ Could I not rewrite this as $\{((0^k)^j)(b^j)\mid k>1\}$. Seeing it in this form makes me think of a form $a^n ...
0
votes
1answer
2k views

If L1 ∪ L2 and L1 are regular, is L2 also regular?

This is a problem in a theory of computation book that's stumping me: Suppose that we know that $L_1 ∪ L_2$ and $L_1$ are regular. Can we conclude that $L_2$ is regular? Explain. At first, I ...
0
votes
1answer
621 views

Complexity classes that are closed under subtraction

Are NP or P closed under subtraction? Im having a hard time deciding whether they are or aren't. Question was edited Original question: Im having some hard time figuring out what languages are closed ...
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?
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 ...
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}∗...
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 ...
0
votes
0answers
10 views

Choose a specific regular language to prove a language is not regular [duplicate]

I've tried a few tricky languages such as D = { w | w has an equal number of occurences of 01 and 10 as substrings} but I don't have the means to prove this one as being not regular (and I cannot ...
0
votes
0answers
28 views

Give an example of a language where both L and ¬L is not semidecidable? [duplicate]

I know ¬H is not semidecidable so I was thinking of creating a language that combines both H and ¬H. Therefore L would be undecidable for ¬H and ¬L would be undecidable for H. Is this a proper ...
0
votes
1answer
61 views

Using closure properties to show that $L_1=\{a^lb^mc^m|l,m\ge 0\} \cup L(b^*c^*)$ is regular or not

i'm trying to figure out whether this Union $\left [ L_1=\{a^lb^mc^m|l,m\ge 0\} \cup L(b^*c^*)\right]=K$ is regular or not, now since regular languages are closed under intersection, so i assume $K$ ...
0
votes
1answer
86 views

Closure of a CFL under specific operation

Consider the following operation on language $L$: $\mathrm{inv}(L) = \{ xy^Rz \mid x,y,z\in \Sigma^*, xyz\in L \}$ I understand that if $L$ is regular, then $\mathrm{inv}(L)$ is regular too, and ...
0
votes
0answers
331 views

CFL Intersection with Regular Language prove

how can i prove the following statement : 1- $L_1\subseteq\Sigma^*$ is CFL and $L_2\subseteq\Sigma^*$ is regular Language, then $L_1$\ $L_2$ is CFL . so i want to know what is the method to prove it ...
0
votes
1answer
281 views

Proof Check: The class L is closed under concatenation

I want to prove that the class of all Turing machines that use a logarithmic amount of space is closed under concatenation. The basic idea of my proof is this: given a word, to check if it's in $...
0
votes
0answers
248 views

Writing a constructive proof for closure of a regular language under homomorphism

I've spend the last few days searching online for an example of a constructive proof of regular languages being closed under homomorphism, but I have not seen one. I am mostly unsure of how to show ...
0
votes
0answers
70 views

mapping reduction for every recursive language [duplicate]

how do I prove that for every 2 languages $A,B\in R$ where $A,B \notin \{ \emptyset , \Sigma^* \}$ I can do a reduction $A \leq_m B$? [EDIT] My try: $A$ is decidable therefore it has a turing ...
0
votes
0answers
170 views

Union, Intersection, Difference, etc. of different types of languages

I am preparing for a competitive exam (GATE) in which questions are asked in Automata about operations among different types of languages. For example, If $L_1$ is recursive & $L_2$ is ...
0
votes
1answer
229 views

prove decidability and recognizability

I want to prove that for any language $L_1$ described by a Turing machine and any regular language $L_2$, $L_1 \cap L_2$ is described by a Turing machine that its recognizability and decidability is ...
0
votes
1answer
4k views

Kleene positive closure - help in proofing this claim

I just started a course called 'Automata and Formal Languages'. I'm having difficulty in proofing\disproofing this equality. $ (L_{1} \circ L_{2})^{+} = L_{1}^{+} \circ L_{2}^{+} $ Where: $ L_{1}...
-1
votes
1answer
51 views

P is closed under power of integer

I'm new in this area of complexity and I'm trying to get into it by understanding basic proofs. I want to prove that if $L\in P$, so $L^k\in P$, where $k$ is non-negative integer. How to prove it in ...
-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
votes
1answer
804 views

when can I know if a class (complexity) is closed under reduction (cook/karp)

How do I know if a class let's say PP , is closed under cook reduction or not closed? I understand the concept of reduction (how to use it mainly) , but still can't figure out the meaning behind it, ...
-1
votes
1answer
2k views

Finding a Regular Expression for an Intersection of Two Regular Expressions

Finding a Regular Expression for an Intersection of Two Regular Expressions PAIR of regular expressions is ((ss*)t*) and ((ss*) + (tt*)). How do I find a regular expression that represents the ...

1
3 4 5
6
7