# Questions tagged [closure-properties]

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

308 questions
Filter by
Sorted by
Tagged with
823 views

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 ...
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 ...
444 views

### Given a non-deterministic Mealy machine $M$, if $L$ is regular, is $M(L)$ regular?

Consider a nondeterministic Mealy machine, $M$, defined as follows: $M = (Q, \Sigma, \Delta, \delta, \tau, q_0)$ where $Q$ is a finite set of states $\Sigma$ is an input alphabet $\Delta$ is an ...
112 views

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 ...
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 ...
1k views

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. ...
375 views

### What happens with trios, full trio, (full) semi-AFL, (full) AFL if we require closure under intersection?

Wikipedia says: A trio is a family of languages closed under e-free homomorphism, inverse homomorphism, and intersection with regular language. A full trio, also called a cone, is a trio ...
118 views

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 ...
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 ...
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?
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 ...
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\}$ ...
9k views

### Why is the class of recursively enumerable languages not closed under complementation?

I am having a hard time understanding closure properties of recrusively enumerable languages. I have read the explanation on this site but still unable to fully understand why they are not closed ...
4k views

### Closure of CFL against right-quotient with regular languages

Let $A/B$ = $\{ w \mid wx \in A$ for some $x \in B \}$. Show that if A is context free and B is regular, then $A/B$ is context free. My interpretation of this is is that we need to show that if a ...
204 views

### Regular language concatenation with superset

Let $A$ be some alphabet. $A$ itself is a regular language. $E = A^*$ is regular language over $A$. $E$ is a superset of all languages over $A$, regular or otherwise, i.e $E$ contains every possible ...
3k views

### Kleene star closure of a context free grammar

I have this question about closure of a context free grammar, and if someone can check my answer and see if it makes sense, and if not, what is missing, I would be very grateful. Give an counter-...
504 views

### If $L$ is CFL and $\overline{L}$ is CFL, then is L regular?

I've seen in previous exams that professors marked the theory as correct: If $L$ is CFL and $\overline{L}$ is CFL, then L is regular. I just don't see how this would work. How would we prove such ...
240 views

### Prove that A* is the smallest reflexive and transitive set containing A

I'm trying to learn automata theory on my own and I am running into an issue with the second part of the question: We say B is transitive if $BB\subseteq B$ and reflexive if $\epsilon \in B$ Show ...
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 ...
610 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 ...
526 views

### Is Co-NP closed under taking subset?

I have a question on my homework causing some confusion. If L is a strict subset of L', and L' is a member of Co-NP, is L a member of Co-NP? True of False Now I understand what belonging to Co-...
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 ...
111 views

### Prove the existence of regular $C$ so that: $A \prec C \prec B$

Given $A,B$ regular languages with $A \prec B$. Prove the existence of $C\in L_{\text{regular}}$ so that: $A \prec C \prec B$. Here, $A\prec B$ stands for: $A\subset B$ and $B\setminus A$ is ...
7k views

### Is every subset of a decidable set, also decidable?

Is it true that if A is a subset of B, and B is decidable, than A is guaranteed to be decidable? I believe it would be true because all the subsets of B should also be decidable making A decidable. I'...
3k views

### Is the class of non-regular languages closed against Kleene star?

How to prove that if a language A is not regular then A* isn't regular either? I have tried the usual methods with no result.
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 ...
95 views

### Is $\{s_0 w s_1 : s_0s_1\in L_1, w\in L_2 \}$ context free if $L_1$ and $L_2$ are?

In class, it was alluded to that a language: \begin{equation*} \{s_0 w s_1 : s_0s_1\in L_1, w\in L_2 \} \end{equation*} would be context free, if $L_1$ and $L_2$ are context free. Intuitively, that ...
4k views

### How to prove that context sensitive languages are closed under intersection and complement?

This is a question from the exam of our "Automata and Formal Languages" course. There is a question where asked to prove or disprove that any "relative complement" operation between two context ...
Let $\Sigma$ and $\Delta$ be alphabets. Consider a function $\varphi: \Sigma \rightarrow \Delta^*$. Extend $\varphi$ to a function from $\Sigma^* \rightarrow \Delta^*$ such that: \begin{eqnarray*} \...