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

learn more… | top users | synonyms

4
votes
1answer
373 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 ...
1
vote
0answers
34 views

A construction to show a very restricted substitution closure result for DCFLs

Let $P$ be a deterministic PDA recognizing a deterministic CFL with a binary alphabet. Modify $P$ to identify its reading states (denote this subset of states by $R$) in accordance with the ...
2
votes
3answers
159 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 ...
5
votes
2answers
54 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
56 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 ...
3
votes
1answer
105 views

Prove that context free languages aren't closed under DropMiddle

The question is simple: $\qquad \operatorname{DropMiddle}(L)=\{xy\in\Sigma^* \mid |x|=|y| \land \exists a\in\Sigma\colon xay\in L\}$. Prove that CFL's aren't closed under ...
1
vote
1answer
28 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
63 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 ...
2
votes
1answer
41 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?
3
votes
1answer
161 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 ...
1
vote
2answers
108 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 = ...
2
votes
2answers
326 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 ...
1
vote
2answers
147 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 ...
0
votes
2answers
78 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 ...
1
vote
1answer
59 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 ...
3
votes
1answer
100 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 ...
2
votes
1answer
44 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 ...
1
vote
3answers
144 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 ...
-1
votes
1answer
93 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 ...
2
votes
1answer
122 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 ...
6
votes
3answers
139 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 ...
3
votes
1answer
91 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 ...
-1
votes
1answer
328 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. ...
1
vote
1answer
144 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.
0
votes
1answer
106 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 ...
3
votes
2answers
75 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 ...
2
votes
1answer
470 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 ...
0
votes
2answers
365 views

Are regular languages closed under inverse homomorphism?

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*} ...
1
vote
0answers
1k views

Is the class of non regular languages is closed under complementation?

This is the question I am asked and I am currently proving it using proof by contradiction something like this: Let's take some language L which is non regular. Let's assume compliment of L i.e. ...
0
votes
2answers
85 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
2answers
415 views

Prove Context Free languages not closed under difference?

Given two context-free languages $L_1$ and $L_2$, the language given by the difference of the two languages, $L_1 - L_2$, is (in general) not context-free. Is it possible to prove this without using ...
1
vote
2answers
386 views

Are regular and context free languages closed against making them prefix-free?

For a language L we define: $\qquad A(L) = \{ x \in L \mid \text{ no proper prefix of x is in L} \} $ Are regular / context free languages closed under this operation ? For regular languages I ...
4
votes
1answer
103 views

$\mathbf{NC}$ is closed under logspace reductions

I am trying to solve the question 6.12 in Arora-Barak (Computational Complexity: A modern approach). The question asks you to show that the $\mathsf{PATH}$ problem (decide whether a graph $G$ has a ...
2
votes
2answers
1k views

Complement of Non deterministic Finite Automata

It's known that the complement of a DFA can be easily formed. That is, given a machine $M$, we can construct $M'$ such that $L(M') = \Sigma^* \setminus L(M)$. Is it possible to construct such a ...
5
votes
1answer
137 views

Reference request: proof that if $L \in DCFL$, then $L \Sigma^* \in DCFL$

So, it's fairly easy to prove that if $L \in DCFL$, then $L \Sigma^* \in DCFL$. Basically, you take the DPDA accepting $L$. You remove all transitions on final states, and then for each $a \in \Sigma$ ...
2
votes
1answer
94 views

Space(n) not closed under Karp reductions - what about NTime(n)?

In the book on complexity by Arora and Barak, there is an exercise to show $Space(n)\neq NP$, the proof of which goes by showing that $NP$ is closed under Karp reductions, while $Space(n)$ isn't. To ...
1
vote
1answer
59 views

Is CFL closed against exchanging complementation and reversal?

Let $L$ be a language such that $\overline{L}^R$ (the reversal of the complement of $L$) is context-free. Is then also $\overline{(L^R)} \in \mathrm{CFL}$?
2
votes
2answers
89 views

Proving that CFLs are closed under even-ness using grammars

This is a question from a 2007 exam paper for a course I'm studying, question 2 on page 2. Theorem: Let $L$ be a context-free language. Let $L_{even}$ be the subset of $L$ consisting of all the ...
1
vote
1answer
77 views

Closure of Star-Free Languages under Substitution

Let $L$ be a star-free language over finite alphabet $\Sigma$. A substitution will be a map $\sigma : \Sigma \to \mathcal{P}(\Sigma^*)$. It seems obvious that if $\sigma(a)$ is star-free for every ...
1
vote
2answers
296 views

Why NP is not closed under Turing reduction

The notion of polynomial time Turing reductions (Cook reductions) is an abstraction of a very intuitive concept: efficiently solving a problem by using another algorithm as a subroutine. For ...
2
votes
3answers
901 views

Proof that the regular languages are closed under string homomorphism

Where can I find a proof of this? Thanks!
3
votes
1answer
121 views

What does it mean to say that a language is “effectively closed” under an operation?

I've been reading some formal language theory papers, and I've come across a term that I don't understand. The paper will often refer to a set being "effectively closed under intersection" or other ...
3
votes
2answers
173 views

Prove that $L_1$ is regular if $L_2$, $L_1L_2$, $L_2L_1$ are regular

Prove that $L_1$ is regular if $L_2$, $L_1L_2$, $L_2L_1$ are regular. These are the things that I would use to start. As $L_1L_2$ is regular, then the homomorphism $h(L_1L_2)$ is regular. Let ...
2
votes
1answer
156 views

Prove that context free languages are not closed under swapping prefixes and suffixes

Prove that context free languages aren't closed under this operation: $ A(L) = \{ zyx \mid x,y,z \in \{0,1 \}^*, xyz \in L \} $ Obviously, we need to find a context free language $L$ such that $A(L)$ ...
3
votes
1answer
239 views

Are permutations of context-free languages context-free?

Given a context-free language $L$, define the language $p(L)$ as containing all permutations of strings in $L$ (i.e. all strings in $L$ such that the order of symbols is not important). Is $p(L)$ ...
5
votes
1answer
164 views

Closure under intersection of context free binary trees

Some sets of ordered binary trees can be represented as a CFG with rules of the form A -> aBC A -> b Where A,B,C are ...
10
votes
1answer
274 views

Are context-free languages in $a^*b^*$ closed under complement?

The context-free languages are not closed under complement, we know that. As far as I understand, context-free languages that are a subset of $a^*b^*$ for some letters $a,b$ are closed under ...
5
votes
2answers
1k views

Why isn't the class of Turing-Recognizable languages closed under Complement?

I'm studying Turing Machines and I've already showed how Turing-Decidable is closed for the operations of Union, Intersection, Concatenation, Complement and Kleene Star. Next I did some demonstrations ...
7
votes
2answers
145 views

Regularity of the exact middle of words from a regular language

Let $L$ be a regular language. Is the language $L_2 = \{y : \exists x,z\ \ s.t.|x|=|z|\ and\ xyz \in L \}$ regular? I know it's very similar to the question here, but the catch is that it's not a ...
1
vote
1answer
94 views

How can I show a linear languages are closed against concatenating with regular ones?

This was given as a homework problem but I have already submitted the assignment. I'd like to resolve it at this point for my own satisfaction. Given that $L_1$ is a linear language and $L_2$ is a ...