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
213 views

Language described by inverting accepting states of NFA

Connecting to When states that are not accepting states become accepting states in NFA, what happens?, what is the formal language described by inverting accepting states of NFA? By inverting, I mean ...
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 ...
5
votes
1answer
153 views

Is there $L$ such that $L$ and $\bar L$ are context free, but $L$ is not deterministic context free?

The usual candidates for context free languages whose complement is also context free, but they are not regular are the Deterministic Context Free Languages ($DCFL$). For example, $L=\{a^nb^n\mid n\...
0
votes
1answer
967 views

Union of finite and non-regular language [duplicate]

Question: ($B$ and $C$ are languages) $B$ is finite,$C$ isn't regular: Prove/Disprove: $C\cup B$ isn't regular. Thoughts: My intuition says this is true, but I need an idea to prove it. Since I don'...
1
vote
1answer
142 views

If $g ∘ f$ is primitive recursive, are $f$ and $g$, too?

Assuming I have functions $f, g : \mathbb{N} \to \mathbb{N}$ and I know that $g \circ f$ is a primitive recursive function. What can I tell about $f$ and $g$? Are they primitive recursive as well? Or ...
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
45 views

If $L$ is a $CFL$, then why isn't $L^*$ also $CFL$

I was studying closure properties of CFLs and I came across this. I want to understand why $L^*$ is not a CFL, can anyone explain me in depth with simple examples?
2
votes
1answer
530 views

How to prove that the Myhill-Nerode equivalence classes for L are the same as for its complement?

Given language $L$, I want to show that its Myhill-Nerode equivalence classes are the same as for its complement $\overline{L}$. I am thinking of constructing a DFA $M$ for the Language $L$ so the ...
1
vote
1answer
65 views

Decidability language, intersection

I have two langages $ A, B \in \mathrm{coRE}$. How can I prove that $ A \triangle B= ( A - B) \cup (B - A)$ is also in $\mathrm{coRE}\,$?
2
votes
1answer
2k views

are regular languages closed under division

I am trying to solve this question which appeared in previous exam paper Can someone help me what i am failing to understand For languages $A$ and $B$ define $A \div B = \{x \in \Sigma^{\ast} : xy ...
1
vote
1answer
2k views

Find a CFG for the set of prefixes of a CFL [duplicate]

How do i generate grammar for Prefix of Langauge L, SupposeG=(V,􏰀,P,S)is a context-free grammar generating a CFL L then pref(L) is defined as pref(L)={x∈􏰀∗ : ∃ y such that xy∈L}. I understand for ...
0
votes
1answer
216 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 ...
1
vote
1answer
74 views

Is the extension of every undecidable theory undecidable?

While it is not the case that the extension of every decidable theory is decidable, is it true that: the extension of every undecidable theory undecidable? In other words, given an undecidable ...
1
vote
1answer
317 views

If pref(L) is regular, does that imply L is regular?

I have this exercise for homework: Say we have a language L. we know that the language pref(L) (all the prefixes of ...
5
votes
3answers
11k views

Decidable languages kleene star closure - question on a proof

I read a proof on the closure of decidable languages under kleene star. It begins by saying that the turing machine we want to find would non-determistically split the input string and then use the ...
6
votes
1answer
68 views

Are the complements of $NP$-languages with only $n$ words of length $n$ also in $NP$?

Assuming $\Sigma = \{ 0, 1\}$.. Given a language $L$, such that for each $n\in \mathbb{N}$ we have $n$ words of length $n$ in $L$ and assuming $L\in NP$, can we prove also that $L\in Co-NP$? So it ...
3
votes
2answers
1k views

Prove that the equal-length concatenation of regular languages is context free

If A and B are regular, then prove that $A@B = \{xy \mid x \in A \text{ and } y \in B \text{ and } |x|=|y|\}$ is always context free. So I'm trying to come up with the proof that looks something like ...
1
vote
1answer
1k views

Turing-recognizable languages closed under star operation

I'm tasked with demonstrating that the class of Turing-recognizable languages is closed under the operation of star, but I'm confused about how this is true. For example, I have a TM to recognize a ...
1
vote
1answer
267 views

Concatenation of languages in NP

I have a hard time to understand why the concatenation of two languages over an alphabet (concatenation is in NP), doesn't imply that each of the languages for themselves are in NP. I talked with my ...
7
votes
3answers
2k views

How to XOR automata?

Say we have 3 DFAs. We know how to OR, AND, or NOT them. But how does one XOR them? There is not one single mention of this online. $x\; \mathrm{XOR} \;y\; \mathrm{XOR} \;z = ((x|y)(\neg x|y)|z) (\...
7
votes
1answer
320 views

If L is context-free, must FH(L) be context-free?

Define $FH(L) = \{x \in \Sigma^* : \exists y \in \Sigma^* \text{ with } |x| = |y| \text{ such that } xy \in L\}$. In other words, $FH(L)$ is the set of first halves of even length strings in $L$. ...
1
vote
1answer
2k views

Is Context Free Language closed under perfect shuffle?

Note that this is not shuffle but perfect shuffle, defined as follows: Let $w = a_{1}a_{2} \ldots a_{n}$ and $x = b_{1}b_{2} \ldots b_{n}$ be two strings of the same length. Then the perfect shuffle ...
3
votes
2answers
823 views

If both the concatenation of two languages and the second “half” are regular, is the first too?

Given that $L_2$ is regular and infinite and $L_1 \cdot L_2$ is regular, then $L_1$ is also regular. I need some help on getting started on proving this is the case. My intuition is that if $L_1 \...
8
votes
1answer
3k views

Are DCFLs closed under reversal?

According to this chart, DCFLs are closed under reversal. However, I am not convinced as the intuitive proof (reversing the arrows of the controlling finite state machine and switching the pushes and ...
2
votes
2answers
121 views

Prove that REG is closed against removing all but lexicographicaly largest words (per length)

Let $\Sigma_n = \{0, 1, ... , n-1\}$. Suppose $L \subseteq$ $\Sigma^*_n$, and let $\qquad\displaystyle\mathcal{B}(L) = \{ x \in L : x = \textrm{lex}\max L_m, m \in \mathbb{N}_0 \}$, where $...
10
votes
1answer
376 views

Constructing all context-free languages from a set of base languages and closure properties?

One way of looking at regular expressions is as a constructive proof of the following fact: it's possible to construct the regular languages by starting with a small set of languages and combining ...
0
votes
1answer
112 views

For two regular languages, why is the set of words from one that don't have a subsequence in the other also regular?

In general, a string $x$ is a subsequence of $w = w_1\dots w_n$ if there are integers $i_1<\dots< i_k$ such that $x = w_{i_1}\dots w_{i_k}$. The subsequence is proper if $k < n$ and $k > ...
1
vote
1answer
166 views

Don't understand closure under string reversal

I am trying to learn from http://www.cs.uiuc.edu/class/su08/cs273/lectures/lect_06.pdf #2 and I understand everything except for the 2nd line of delta prime prime function, I having breaking down ...
3
votes
3answers
2k views

Clearing a Confusion regarding the Proof of equal no of a's and b's not being a regular language

I was wondering about its proof. The direct use of pumping lemma here is not a viability. So a certain teacher of mine proved this with the notion that $a^{n}b^{n}$ being a subset of this language $L=\...
1
vote
1answer
3k views

Show that the regular languages are closed against taking “the second half” [duplicate]

Given $L$ is regular, the proof that $\mathrm{HALF}(L)$ is regular is pretty straightforward to me (e.g., #11 in this link): simply making a NFA and meeting in the middle with 2 original DFAs, the ...
1
vote
2answers
771 views

Proving Regularity of Languages that are 1/k of an already known regular language

There is this question in Kozen, that states if a language is regular then the first half would also be regular. Also I found a material on the internet that extends the thinking saying a language ...
0
votes
2answers
252 views

The image of a recursive language under a computable function

Let $f:\Sigma^{*}\to\Sigma^{*}$ be a computable function and let $L$ be a recursive language. Is $f(L):=\left \{{f(w)|w\in L} \right\}$ recursive? Here, I see clearly, that $f^{-1}(L)$ is recursive (...
-1
votes
1answer
1k views

How to construct a DFA for this?

Let $C = shuffle(A, B)$ denote the shuffle $C$ of two languages $A$ and $B$, it consists of all strings $w$ of the form $w = a_1b_1a_2b_2....a_kb_k$, for $k > 0$, with $a_1a_2 ··· a_k \in A$ and $...
-2
votes
1answer
1k views

Is a language closed under string concatenation, repetition, and/or taking substring regular?

Is a language $L$ regular, context-free, context-sensitive, recursively enumerable, or ..., if $L$ is closed under string concatenation, and/or string repetition, and/or taking substring? Somehow ...
0
votes
1answer
540 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 $...
3
votes
1answer
140 views

Generators of families of langauges?

From Wikipedia's definition of regular langauges The collection of regular languages over an alphabet $Σ$ is defined recursively as follows: The empty language $Ø$ is a regular language. ...
1
vote
1answer
118 views

Set of $\mathsf{NP}$-hard languages closed under set inclusion?

As the title says, my question is whether the set of $\mathsf{NP}$-hard languages is closed under set inclusion, i.e. whether for any $\mathsf{NP}$-hard language $L$, all subsets of $L$ are also $\...
3
votes
1answer
275 views

Situations where Kleene star of A is context-free, but A is not

This question appeared on my Theory of Computer Science final: True | False: $A^*$ is context-free $\implies$ $A$ is context-free. My professor says the answer is false, and I believe him, but am ...
8
votes
2answers
11k views

are NP Complete languages closed under any regular operations?

I have tried looking online, but I couldn't find any definitive statements. It would make sense to me that Union and Intersection of two NPC languages would produce a language not necessarily in NPC. ...
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 ...
2
votes
3answers
818 views

Does there exist a proof of closure of regular languages under regular substitution by giving the corresponding DFA?

Every proof I can find of this result is by way of regular expressions. Is there any "constructive" proof that defines the corresponding DFA (probably NFA)? For instance the proof of concatenation ...
7
votes
1answer
6k views

how to draw a complement of a Turing Machine?

I am now pretty confident on how I would turn something into a Turing Machine. Now my question is how do you convert TM into a complement of a Turing Machine. From what I can remember in Finite ...
8
votes
3answers
2k views

Demonstrate that DPDA is closed under complement by construction

I've been trying for quite some extended time to find a construction so that I can formally demonstrate that a deterministic PDA is closed under complementation. However, it happens that every idea I ...
6
votes
2answers
440 views

Intersection of two NPDAs

Is there a way to take the interection of two NPDAs? I can't seem to find anything that can make that happen, but it seems like the type of thing that is should be relatively trival.
2
votes
0answers
168 views

If $L_1$ is regular and $L_1 \cap L_2$ context-free, is $L_2$ always context-free? [closed]

If $L_1$ is a regular language and $L_1 \cap L_2$ is a context-free language, does it mean that $L_2$ is a context-free language too? I attempted to prove that $L_2$ was not required to be context-...
1
vote
1answer
58 views

Is P closed under subwords? [closed]

Given a language $L\subseteq \Sigma^*$ in $P$, is the language $subwords(L) = \{v\in\Sigma^* : \text{there exist } u,w\in \Sigma^* \text{ with } uvw\in L\}$ that consists of all subwords of words ...
0
votes
2answers
1k 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 ...
3
votes
2answers
2k views

Do Kleene star and complement commute?

I am having hard time solving the following problem. Are there any languages for which $$ \overline{L^*} = (\overline{L})^* $$ Assuming $\emptyset^* = \emptyset$, if I consider $\Sigma = \{a\}$ ...
2
votes
1answer
467 views

CFL not closed under intersection while Turing Decidable are

It makes me wonder that despite of (CFL) being a subset of Turing Decidable languages, Turing Decidable is closed under intersection while CFL is not. Does not Turing Decidable engulf all CFLs?
8
votes
1answer
1k views

Kleene star of an infinite unary language always yields a regular language

Let $L = \{a^n \mid n \ge 0\}$, where $a^0 = \epsilon$ and $a^n = a^{n-1}a$ for all $n \ge 1$. Thus $L$ consists of sequences of $a$ of all lengths, including a sequence of length $0$. Let $L_2$ be ...