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

learn more… | top users | synonyms

0
votes
1answer
87 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
28 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
32 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 ...
0
votes
1answer
26 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 ...
-1
votes
1answer
30 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
42 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
49 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
55 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
139 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
94 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
207 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
116 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
151 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
104 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
120 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
87 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
69 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
84 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 ...
1
vote
2answers
97 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
63 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
55 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
37 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
102 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
97 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
50 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
64 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
113 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
44 views

Show that $L^c$ is also in NP

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 ...
5
votes
3answers
318 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 ...
0
votes
1answer
49 views

prove language is Context-free and not regular [duplicate]

I have to prove that $\left \{ a, b \right \}^{\ast} - \left \{ a^ib^i | i\geq 0 \right \}$ is a context-free language and it's not regular. So far I've got that this language is not regular because ...
3
votes
1answer
103 views

Symmetric Difference of Turing Recognizable and Finite Languages

Let A be a Turing Recognizable Language and B a finite Language. I want to prove that their symmetric difference is Turing Recognizable. My reasoning: B is finite, therefore the finite number of ...
1
vote
0answers
84 views

Are DCFLs closed under concatenation with a regular language?

I have found various opinions saying they are (a link to one is given in D.W.'s comment). However, a proof that DCFLs themselves are not closed under concatenation found here on StackExchange seems to ...
3
votes
1answer
41 views

Proof that CFL aren't closed under intersection using synchronous parallel (N)PDA composition

It is well known that the class of CFLs is not closed under intersection as follows e.g. from the following example: $$L_1 \cap L_2 = \left\{ a^mb^mc^n \mid m,n \ge 1 \right\} \cap \left\{ a^mb^nc^n ...
1
vote
1answer
81 views

Prove that $S_2$ is closed under union and complement

I'm having trouble proving that $S_2$ is closed under union and complement, even though in this Wikipedia article it says that: It is immediate from the definition that $S_2$ is closed under union ...
0
votes
0answers
30 views

mapping reduction for every recursive language [duplicate]

how do I prove that for every 2 languages $A,B\in R$ where $A,B \notin \{ \emptyset , \Sigma^* \}$ I can do a reduction $A \leq_m B$? [EDIT] My try: $A$ is decidable therefore it has a turing ...
1
vote
1answer
218 views

A and B are Turing recognizable, is A - B Turing recognizable?

If A and B are Turing recognizable, is A - B Turing recognizable? I think that A - B would be Turing recognizable because they're both in the space of Turing recognizability. For example, if A is ...
5
votes
3answers
103 views

Are deterministic and nondeterministic Cellular Automata equivalent?

It seems that in CA context nondeterministic (ND) means probabilistic, not ND as in NFSMs. At least I haven't seen a paper or book which discusses NCAs, without talking about probabilistic CAs. I ...
7
votes
1answer
78 views

Smallest class of automata model whose corresponding language class contains CFL and is closed against (dis)allowing nondeterminism in the model

From a comment, an interesting question popped up. The class of CFLs (the languages recognized by PDAs) are obviously not closed under nondeterminism - what I mean by this is that deterministic PDAs ...
7
votes
1answer
127 views

Is the closure of P under e-free homomorphisms equal to NP?

The context free languages can be obtained as the closure of the Dyck language under the cone operations. The Dyck language $D_2$ is a deterministic context free language, and the cone operations ...
1
vote
0answers
99 views

Formal language properties and finite state machines [closed]

What are properties of a formal language? Which and how would they be needed to prove that some Non-Deterministic finite state machine can accept a given language?
2
votes
1answer
87 views

Prove that regular languages and context-free languages aren't closed under $Perm(L)$

Let the operation $$Perm(L) = \{ w | \exists u \in L \text{ such that } u \text{ is a permutation of } w \}$$ Prove that both regular languages and CFLs aren't closed under $Perm(L)$. I've tried ...
3
votes
3answers
396 views

Show that regular languages are closed under Mix operations

Let $L_1, L_2$, two regular languages and the operations: $$Mix_1(L_1, L_2) =\{ a_1b_1a_2b_2\ldots a_nb_n | n\ge 0 \land a_1,a_2,\ldots ,a_n,b_1,b_2,\ldots ,b_n\in\Sigma\\ \land a_1a_2\ldots a_n\in ...
1
vote
2answers
54 views

Prove/ Disprove: If $L$ is a CFL then $A(L)$ is a CFL too

Consider the operation $A(L)$: $$A(L) = \{ w: w\in L \land w_R \notin L \}$$ where $w_R$ is the reverse of $w$. Prove/ Disprove: if $L$ is a CFL language so does $A(L)$. I am almost certain ...
5
votes
1answer
45 views

Question on NP $\cap$ coNP

I'm struggling with a past paper question and would appreciate any hints: Suppose $L_1, L_2 \in $ NP $ \cap $ coNP and $L_1 \oplus L_2 = \{ x : x $ is in exactly one of $L_1 $ or $ L_2 \} $. Then ...
5
votes
1answer
172 views

Closure properties of linear context-free languages

Under what operations are linear context-free languages closed? Suppose $L_1, L_2$ are two linear context free languages. Are there any guarantees about $L_1 \cup L_2$, $L_1 \cap L_2$, ...
3
votes
2answers
179 views

Proving regular languages are closed under a form of interleaving

I've got the following definitions: $$\mathrm{Interleave}\,(x,y) = \{w_1\dots w_n\mid w_i\in\{x_i,y_i\} \text{ for }i=1, \dots, |x|\}$$ when $x$, $y$ and $w$ are words with $|x|=|y|$ and $w_i$ means ...
2
votes
1answer
44 views

prove that a language is context free given a regular language

R is a regular language over $\Sigma=\{0,1\}$ $Sub(R)=\{0^i1^j \mid \exists w\in R.|w|=i-j \}$ I need to prove that Sub(R) is context free. I know that the quotient of a context free language with a ...
1
vote
1answer
259 views

Proving that non-regular languages are closed under concatenation

How can I prove that non-regular languages are closed under concatenation using only the non-regularity of $L=\{a^nb^n|n\ge1\}$ ?