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

learn more… | top users | synonyms

9
votes
1answer
225 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 ...
1
vote
1answer
44 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 ...
1
vote
0answers
46 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 ...
0
votes
1answer
61 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 > ...
3
votes
3answers
117 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 ...
0
votes
1answer
35 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
66 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 ...
-2
votes
0answers
16 views

Prefix closure of the language [duplicate]

If Σ is a finite set of symbols and α is a word in Σ ∗ , then a word β in Σ ∗ is said to be a prefix of α if α = β γ for some γ ∈ Σ ∗ . For example, the prefixes of the word abbab are λ , a , ab , abb ...
-1
votes
1answer
89 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 ...
0
votes
2answers
99 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 ...
-2
votes
1answer
83 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? ...
0
votes
1answer
39 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
125 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
3answers
111 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 ...
1
vote
1answer
63 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
29 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 ...
3
votes
2answers
355 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. ...
1
vote
3answers
296 views

Is the class NP closed under complement?

Is the class $\sf NP$ closed under complement or is it unknown? I have looked online, but I couldn't find anything.
5
votes
1answer
517 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 ...
2
votes
3answers
182 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
58 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
66 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
116 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
33 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
79 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
79 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
184 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
170 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 = ...
3
votes
2answers
679 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
247 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
83 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
132 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
117 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
53 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
307 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
111 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
140 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
178 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
95 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
478 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
191 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
124 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
581 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
479 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
96 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
456 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
440 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
114 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 ...