Tagged Questions

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

learn more… | top users | synonyms

-2
votes
0answers
30 views

Why is $L_1-L_2$ regular for any two regular $L_1,L_2$? [on hold]

How do I show that for any two regular languages $L_1,L_2$, their difference $L_1 - L_2$ is also regular? I tried to solve this but I'm not sure my solution works.
1
vote
1answer
22 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
152 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 ...
6
votes
3answers
831 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) ...
4
votes
1answer
50 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 ...
6
votes
1answer
109 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$. ...
0
votes
1answer
118 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 ...
0
votes
1answer
25 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: $ ...
3
votes
2answers
439 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 ...
2
votes
3answers
96 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 ...
2
votes
1answer
140 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 ...
8
votes
3answers
884 views

Union of regular languages that is not regular

I've come across that question : "Give examples of two regular languages which their union doesn't output a regular language. " This is pretty shocking to me because I believe that regular languages ...
2
votes
2answers
91 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 \}$, ...
9
votes
1answer
253 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
65 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
65 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
72 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
179 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
73 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
80 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 ...
-1
votes
1answer
106 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
107 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
112 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
48 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
122 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
67 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
42 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
616 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
501 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.
6
votes
1answer
670 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
201 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
59 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
73 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
123 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
34 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
124 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
93 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
237 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
239 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
913 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
350 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
87 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
250 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
123 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
102 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 ...
4
votes
3answers
498 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
114 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
144 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 ...
7
votes
3answers
225 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 ...