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

learn more… | top users | synonyms

0
votes
2answers
83 views

Is intersection of regular language and context free language is “always” context free language

I have read that intersection of regular language and context-free language is always context-free. Most of the places an standard example has been used to prove this, e.g., \begin{align*} L_1 &= ...
-3
votes
1answer
65 views

proving that pp closed under cook reductions [closed]

I tried to prove or disprove that pp is closed under cook reductions. anyone has a idea or link to a answer?
-1
votes
1answer
44 views

when can I know if a class (complexity) is closed under reduction (cook/karp)

How do I know if a class let's say PP , is closed under cook reduction or not closed? I understand the concept of reduction (how to use it mainly) , but still can't figure out the meaning behind it, ...
3
votes
2answers
174 views

Proving that PP is closed under symmetric difference

I want to prove that PP is under symmertic difference. let A be a language in PP and B likewise. I tried showing that : (A\B) U (B\A) in PP , so by show each in PP and then showing that it's closed ...
-1
votes
1answer
74 views

Turing Machine and decidability

so the thing is that i have to prove that if the language $L ⊆ \Sigma^*$ is decidable then both languages are also decidable. $$P_1(L) = \{w ∈ Σ\mid \text{ For every prefix v of w, we have }v ∈ L\},$$ ...
3
votes
1answer
60 views

How to Trace Path in Proof that Regular Languages are Closed Under Reversal

I'm self studying automata theory and I need help with proving that regular languages are closed under reversal. I have a basic proof, but am unsure about last statement in my proof. Is this ...
-1
votes
1answer
54 views

Show that P is closed against the Kleene star

I have that question that looks kinda easy at first but it is quit hard. Let $L\in P$. Prove that $L^*\in P$ my approach: I tried to generate a turing machine but I got stuck with the thing of ...
1
vote
1answer
52 views

Why DCFL is not closed under kleene star?

I have read somewhere that DCFL is not closed under kleene star. but I haven't found any example
2
votes
1answer
112 views

Is NEXP = co-NEXP?

It is known that $\mathsf{NL}=\mathsf{Co{-}NL}$ and unknown if $\mathsf{NP}=\mathsf{Co{-}NP}$. But what about $$\mathsf{NEXP}=\mathsf{Co{-}NEXP}?$$ Is it known whether these two classes are equal?
0
votes
1answer
98 views

Finding the mistake(s) within this “proof” of NP being closed for complement

For my classes in theoretical computer science the following proof must be shown to be wrong. However, this is the first time I am attempting myself at this topic, so I would be thankful for some help:...
6
votes
1answer
83 views

Why do we study closure properties of formal languages?

In automata theory we study formal languages like Regular, CF, CS and etc. and each of them have their own closure properties under union, intersection, star and etc. . I like to know, why it is ...
4
votes
1answer
59 views

Closure properties of the class of inherently ambiguous CFLs

is set of inherently ambiguous context free languages close under operations such that union, intersection, kleene star, concatenation, reverse, complementation and etc. how many of theme are answered?...
3
votes
2answers
80 views

Why are palindrome and not-palindrome both context-free?

Both palindrome and its complement are context-free. This is very interesting. Both are non-deterministic context-free, which in general are not closed under complement. What is it about these two ...
0
votes
1answer
53 views

If L is a regular language then the language replace(L,σ,τ) is also regular

I am stuck at the following problem: Prove that if $L$ is a regular language over some alphabet $\Sigma$ and that $\sigma, \tau \in \Sigma$, Then the language $replace(L,\sigma,\tau)$ is regular. ...
1
vote
1answer
49 views

If a language is X-complete, is its complement is X-complete as well?

I'm looking for an information about closure of complexity complete classes. Is it true that any language, if the language is X-complete, then its complement is X-complete? Why? I was thinking ...
0
votes
1answer
25 views

How to prove that the decidable languages are closed against iteration only by enumerators?

We have the $L\in R$, how can we prove that $L^*\in R$ only by enumerators? I try to use induction, but as I understand I wrong... I'd like to get any help!
2
votes
2answers
43 views

Closure under reversal of regular languages: Proof using Automata

I have been studying the closure properties of regular languages, referencing the book Introduction to Automata Theory, Languages, and Computation by John E. Hopcroft and Jeffery D. Ullman. Under the ...
0
votes
0answers
15 views

Want to show that if P = NP, then P = NP = CoNP [duplicate]

I want to show that if P = NP, then P = NP = CoNP. Essentially, I want to show that if the set of problems which can be solved in polynomial time is exactly the set of problems which can be checked in ...
0
votes
1answer
44 views

If a language is context free, then its complement is decidable

I am having a bit of trouble figuring this out. If L is context-free then we know it is decidable. The class of decidable languages is closed under complement thus, $L$ $\cap$ $L^{c}$, therefore $L^{c}...
0
votes
1answer
215 views

Proving $A$ avoiding $B$ regular if $A$ and $B$ are regular

Suppose we define an operation such that $$A \text{ avoiding } B = \{w \in A \mid w\text{ has no substring in }B\}\,.$$ How can I prove that, if $A$ and $B$ are regular then $A\text{ avoiding }B$ ...
1
vote
1answer
57 views

L closed under logspace reduction

Given two languages $A$ and $B$ I have been asked to show that, if $B \in L$ and we have a logspace reduction $f$ from $A$ to $B$ then $A \in L$. I read the proof that $L$ is closed under logspace ...
-1
votes
1answer
37 views

Is the complement of the given language necessarily in NP?

$A$ is a given language so that $A \in NP$. Assume that $P = NP$. Is $A'$ necessarily in NP? What I did: $A \in NP , P=NP$ $P=coP$ (Can be proven by running a TM $M$ as a decider for P, ...
0
votes
1answer
29 views

Why $A \cap B = \widehat{\widehat{A}\cup \widehat{B}}$ does not holds for the class of Recursively Enumerable Languages?

"The class of Recursively Enumerable Languages is closed under Union, and Intersection but they are not closed under Complement." I know why they are not closed under Complement & why they are ...
-1
votes
1answer
34 views

P is closed under power of integer

I'm new in this area of complexity and I'm trying to get into it by understanding basic proofs. I want to prove that if $L\in P$, so $L^k\in P$, where $k$ is non-negative integer. How to prove it in ...
1
vote
1answer
45 views

Why does the concatenation of the empty set with any language give the empty set? [duplicate]

Why does the concatenation of $\emptyset$ with any language give $\emptyset$. I would like to know the intuitive explanation for it.
1
vote
1answer
60 views

Regular languages closed under quotients with arbitrary languages

When proving that that the quotient of a regular language $R$ and an arbitrary language $B$, I understand you take a DFA $M$ accepting $R$, and then construct a DFA that is the same, but its final ...
1
vote
1answer
68 views

Proving specific prefixes of regular languages are regular

There are particular problems in Kozen that I'm unable to solve, and they seem to be similar to each other. It is showing that sets: $$ \{x \mid \exists y: |y| = 2^{|x|} \text{ and } xy \in A \}$$ $$ ...
8
votes
4answers
152 views

If $L_1L_2$ is regular language then $L_2L_1$ is regular to?

We have two languages: $L_1,L_2$. We know that $L_1L_2$ is regular language, so my question is if $L_2L_1$ is regular to? I try to find a way to prove it... I can't assume of course that $L_1,L_2$ ...
1
vote
1answer
85 views

If two languages together cover all words and one is regular, is the other one as well?

If $L_1$$\subseteq$ $\Sigma^*$, $L_2$$\subseteq$ $\Sigma^*$ , $L_1$ is regular and $L_1$$\cup$ $L_2$ = $\Sigma^*$ then is $L_2$ necessarily regular? I think that the answer is yes, but I'm not sure ...
0
votes
1answer
97 views

How do I prove that a language is deletion closed?

For example, how could I prove that the following language is deletion closed: {$a^k$$b^j$ : $j$, $k$ $\geqslant$ 0} The reason seems obvious to me, I just can't see a way to prove it.
1
vote
1answer
299 views

Why is the complement of a language that is not regular also not regular?

In my lecture notes I we were given two languages and were shown that each of the two languages were not regular. The second was the complement of the first language. To show the second was not ...
7
votes
1answer
121 views

Context-free languages not closed under making them “extension-free”

For a language $L$, define: $$ NE(L) = \{x \in L : x \text{ is not the proper prefix of any string in } L\} $$ I'm trying to show context-free languages are not closed under this operation. I've been ...
1
vote
3answers
167 views

Why is the set of all regular expressions classified as context-free, instead of regular?

As I understand regular languages can be closed under concatenation, so can I concatenate the set of all regular expressions to classify them as regular?
-2
votes
2answers
589 views

Union and intersection of a regular and a non-regular language

Lets say we have $L_1$, which is a regular language and $L_2$ which is not. Are $L_1 \cap L_2$, $L_1 \cup L_2$ , $L_1$ \ $L_2$ and $L_1 \cdot L_2$ are always non-regular languages? We know that two ...
0
votes
0answers
17 views

Proving the closure properties of Finite state transducers [duplicate]

Given $T_1, T_2\colon \Sigma^* \to \Gamma^*$ ($\Gamma$ is output alphabet), let $\Delta(T_1, T_2)$ consist of all input strings $w \in Σ^*$ where $T_1(w) \neq T_2(w)$. Prove that FSTs ...
0
votes
1answer
150 views

Closure properties of finite state transducers

Given $T_1, T_2\colon \Sigma^* \to \Gamma^*$ ($\Gamma$ is output alphabet), let $\Delta(T_1, T_2)$ consist of all input strings $w \in Σ^*$ where $T_1(w) \neq T_2(w)$. Prove that FSTs ...
1
vote
2answers
184 views

If L is regular show that even (L) is also regular

I am stuck on the following question If L is regular show that even(L) is also regular where even(L) = {even(w) : w ∈ L} w is a string in L even(w) is the string obtained by extracting from w the ...
1
vote
1answer
77 views

Closure properties of undecidable languages

I know that the decidable are close under: complementation, union, intersection and concatenation? What about the undecidable languages? I think they are close under complementation, but not under ...
1
vote
1answer
99 views

$\mathbf{NC_2}$ is closed under log-space reduction

I actually have to prove the following : $\mathbf{NL} \subseteq \mathbf{NC_2}$ I have the following approach : I will prove that $\mathbf{PATH} = \{〈D, s, t〉 | \text{D is a directed graph with a ...
2
votes
2answers
222 views

Formal construction of PDA intersecting a DFA

Given the PDA $P = (Q_P,\Sigma,\Gamma_P,\delta_P,F_P)$ and the DFA $D = (Q_D, \Sigma, \delta_D,q_D,F_D)$ What is the 6-tuple definition of the PDA such that: $L(P') = L(P) \cap L(D)$ I don't ...
-1
votes
1answer
69 views

Infinite Union of non-regular languages

Is infinite union of non-regular languages $L_i$ that form a chain such that $L_i\subseteq L_{i+1}$ always non-regular? Or is there a possibility that it be ever regular? Is there an easy way to ...
-1
votes
1answer
59 views

How to prove the linear context free languages are closed under gsm mapping?

I'm stuck on the following question: How to prove the linear context free languages are closed under gsm mapping?
-2
votes
2answers
51 views

Why is the intersection of CFL and RL not always RL?

Suppose M is a CFL and N is aa RL. Then wouldn't the language generated by the intersection of M and N contain strings, some of which are accepted by both DFA and PDA? So if they are accepted by a DFA ...
-3
votes
1answer
104 views

Complement of a Language which is set of Turing Machine descriptions

If $L$ is the set of strings $\langle M\rangle$ such that $M$ accepts all strings of even length and does not accept any strings of odd length. What will be $\overline L$ ? a) set of strings $\...
3
votes
1answer
172 views

How to prove closure property of regular languages using regular expressions?

I know that we can prove closure of two regular languages under operations like union, intersection, concatenation etc. by constructing NFAs for them but how to do the same thing using regular ...
0
votes
1answer
56 views

Regular languages and sets proof

I just have general questions about sets and determining if they are regular languages. i) If A is regular, and A is a subset of B, then B must be regular. ii) If B is regular, and A is a subset of ...
1
vote
1answer
94 views

Does applying a homomorphism to the intersection of two CSLs yield RE languages?

For each language $L \in L(RE)$ there are a homomorphism $h$ and two context-free languages $L_1$ and $L_2$ such that $L = h(L_1 \cap L_2)$. I understand that this is because context-free languages ...
-2
votes
1answer
247 views

Finding a Regular Expression for an Intersection of Two Regular Expressions

Finding a Regular Expression for an Intersection of Two Regular Expressions PAIR of regular expressions is ((ss*)t*) and ((ss*) + (tt*)). How do I find a regular expression that represents the ...
-2
votes
1answer
110 views

Show that the complements of NP-languages with one word per length are in NP as well

Let L be a language over Σ i.e., $L\subseteq Σ^∗$. Suppose L satisfies the > two conditions given below. L is in NP and for every n, there is exactly one string of length n that belongs to ...
5
votes
3answers
341 views

Is an irregular language concatenated with a language with which it has no common symbols irregular?

Here's an example of what I'm talking about. Suppose I have a languages $$ L_{1} = \{a^ib^i \mid i>0\},\\ L_{2} = \{c^i \mid i>0\} $$ and $$ L_{1}L_{2} = \{a^ib^ic^i \mid i>0\} $$ Is it ...