Questions about operations on objects of some kind that result in objects of the same kind.
0
votes
1answer
87 views
Proof that the regular languages are closed under string homomorphism
Where can I find a proof of this? Thanks!
3
votes
1answer
46 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 ...
-1
votes
0answers
41 views
Is given language regular? [duplicate]
Let $L$ be a regular language. Is $\frac{1}{2}L := \left\{ w: \exists_u |u|=|w| \wedge wu\in L \right\}$ regular too?
I think the answer is YES. But I don't know how to prove it. I was trying to ...
3
votes
2answers
129 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
65 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
54 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)$ ...
4
votes
1answer
47 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 ...
6
votes
1answer
105 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 ...
3
votes
2answers
94 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 ...
6
votes
2answers
71 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
51 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 ...
4
votes
4answers
129 views
Proof that regular languages are closed against taking the even-length subset
This question is on the GRE Computer Science test booklet (not homework). I tried applying closure properties of regular languages but no success.
Suppose $L$ is a regular language over $\Sigma = ...
2
votes
2answers
65 views
Why is the subset of palindromes of a regular language context-free?
Why is $A(L) = \{x \in L \mid x = x^R \}$ context-free if $L$ is a regular language?
Trying to understand the approach to determining whether a regular language is context-free.
4
votes
2answers
82 views
Does closure against countable union survive union of classes?
A class of languages $\mathcal{C}$ is closed under countable union (cucu) if for all series of languages in $\mathcal{C}$ ($(L_i)_{i\in\mathbb{N}} \in \mathcal{C}^\mathbb{N}$) the language ...
6
votes
1answer
82 views
Is there a strictly non-deterministic one-counter language whose complement is one-counter?
Let
$A= \{L \mid L \;\text{is one-counter and \(\bar{L}\) is also one-counter} \}$
Clearly, $\text{Deterministic one-counter} \subseteq A$
Is it the case that $ A = \text{Deterministic ...
3
votes
1answer
93 views
Can we say anything about the complement of a regular language?
Given a regular language $L$, can we say anything about its complement $\overline L$? One thing that is trivial to say is that the DFA's for both languages are equal in size as complementing the ...
1
vote
3answers
130 views
Are the non-regular languages closed under reverse, union, concatenation, etc?
My question: do the non-regular languages have closure properties? For example, if the reverse of L is non-regular, then L is non-regular ? thank you :-)
4
votes
5answers
244 views
Is $A$ regular if $A^{2}$ is regular?
If $A^2$ is regular, does it follow that $A$ is regular?
My attempt on a proof:
Yes, for contradiction assume that $A$ is not regular. Then $A^2 = A \cdot A$.
Since concatenation of two ...
3
votes
1answer
35 views
“Definition of NP via relations and quantifiers; not via NTMs”
I have the following question on an assignment, and despite asking my prof, I can't get a grasp on it..
Let $L_1, L_2$ be languages in ${\sf NP}$. Using the definition of ${\sf NP}$ via relations ...
9
votes
3answers
206 views
Easy proof for context-free languages being closed under cyclic shift
The cyclic shift (also called rotation or conjugation) of a language $L$ is defined as $\{ yx \mid xy \in L \}$. According to wikipedia (and here) the context-free languages are closed under this ...
2
votes
1answer
90 views
Myhill-Nerode and closure properties
It is well known that regular languages are characterized by the Myhill-Nerode equivalence. For language $L$ over $\Sigma^*$ define the equivalence $x\sim_L y$ over $\Sigma^*$ iff for all ...
2
votes
2answers
124 views
Show that the language of strings not in the union of two regular languages is regular
Given languages $L_1,L_2$, defines $X(L_1,L_2)$ by
$\qquad X(L_1,L_2) = \{w \mid w \not\in L_1 \cup L_2 \}$
If $L_1$ and $L_2$ are regular, how can we show that $X(L_1,L2)$ is also regular?
3
votes
1answer
203 views
What is complement of Context-free languages?
I need to know what class of CFL is closed under i.e. what set is complement of CFL.
I know CFL is not closed under complement, and I know that P is closed under complement. Since CFL $\subsetneq$ P I ...
1
vote
1answer
83 views
Closure properties of languages
Let $P$ be a regular language and $Q$ be a context-free language such
that $Q \subseteq P$(For example, let $P = a^*b^*$ and $Q = \{ a^nb^n | n \ge 0\}$). Then which of the following is always ...
3
votes
1answer
91 views
Deterministic context-free languages are closed under regular right-product
I am looking for a proof for the following problem:
For languages $L$ and $R$, if $L$ is deterministic context-free
and $R$ is regular, then $LR$ is a deterministic context-free
language.
...
3
votes
1answer
124 views
Context-free Languages closed under Reversal
In class this week we've been learning about the CFLs and their closure properties. I've seen proofs for union, intersection and compliment but for reversal my lecturer just said its closed. I wanted ...
2
votes
2answers
141 views
Seeking Alternate Proof Regarding Closure Of Recursively Enumerable Languages
So I would like to show that the class of Recursively Enumerable languages are closed under the shrink operation. In other words, $\text{shrink}_a(L) = \{\text{shrink}_a(w)\mid w\in L\}$ and where ...
2
votes
2answers
178 views
Is $\{a^nb^m \mid n,m\ge 0, n\ne m\}$ regular or not? [duplicate]
Possible Duplicate:
Prove that the complement of $\{0^n1^n \mid n \geq{} 0\}$ is not regular using closure properties
Is $L=\{ a^nb^m \mid n,m \ge 0, n\ne m\}$ a regular language?
I ...
6
votes
3answers
184 views
Proving the language which consists of all strings in some language is the same length as some string in another language is regular
So I've been scratching my head over this problem for a couple of days now. Given some language $A$ and $B$ that is regular, show that the language $L$ which consists of all strings in $A$ whose ...
3
votes
1answer
131 views
If $L$ is a regular language, how to prove $L_1 = \{ uv \mid u \in L, |v| =2 \}$ is also regular?
If $L$ is a regular language, prove that the language
$L_1 = \{ uv \mid u \in L, |v| =2 \}$
is also regular.
My idea: $L$ can be represented as a DFA and then you could add 2 consecutive ...
2
votes
1answer
225 views
Given a truth table, force a contradiction
Suppose I have a formula, and a lying witness is attempting to make it evaluate to False.
Given a truth table $c(F_1,…, F_n)$, how could you force a lying
witness to contradict herself?
A ...
8
votes
1answer
270 views
Prove that the complement of $\{0^n1^n \mid n \geq{} 0\}$ is not regular using closure properties
I want to prove that the complement of $\{0^n1^n \mid n \geq{} 0\}$ is not regular using closure properties.
I understand pumping lemma can be used to prove that $\{0^n1^n \mid n \geq{} 0\}$ is not a ...
6
votes
1answer
123 views
Is #P closed under exponentiation? modulo?
The complexity class $\newcommand{\sharpp}{\mathsf{\#P}}\sharpp$ is defined as
$\qquad \displaystyle \sharpp = \{f \mid \exists \text{ polynomial-time NTM } M\ \forall x.\, f(x) = ...
4
votes
1answer
373 views
Prove that regular languages are closed under the cycle operator
I've got in a few days an exam and have problems to solve this task.
Let $L$ be a regular language over the alphabet $\Sigma$. We have the operation
$\operatorname{cycle}(L) = \{ xy \mid x,y\in ...
1
vote
3answers
225 views
Use closure properties to transform languages to $L := \{ a^nb^n : n\in \mathbb N \}$
For the purpose of proving that they are not regular, what closure properties can I use to transform the languages
$L_a = \{ a^*cw \mid w \in \{a,b \}^* \land |w|_a = |w|_b \}$ and
$L_b = ...
5
votes
3answers
408 views
If $L$ is context-free and $R$ is regular, then $L / R$ is context-free?
I'm am stuck solving the next exercise:
Argue that if $L$ is context-free and $R$ is regular, then $L / R = \{ w \mid \exists x \in R \;\text{s.t}\; wx \in L\} $ (i.e. the right quotient) is ...
4
votes
3answers
561 views
Proving that recursively enumerable languages are closed against taking prefixes
Define $\mathrm{Prefix} (L) = \{x\mid \exists y .xy \in L \}$. I'd love your help with proving that $\mathsf{RE}$ languages are closed under $\mathrm{Prefix}$.
I know that recursively enumerable ...
4
votes
1answer
225 views
The operator $A(L)= \{w \mid ww \in L\}$
Consider the operator $A(L)= \{w \mid ww \in L\}$. Apparently, the class of context free languages is not closed against $A$. Still, after a lot of thinking, I can't find any CFL for which $A(L)$ ...
5
votes
3answers
637 views
operations that aren't closed for undecidable languages
Do there exist undecidable languages such that their union/intersection/concatenated language is decidable? What is the physical interpretation of such example because in general, undecidable ...
8
votes
2answers
323 views
Closure against right quotient with a fixed language
I'd really love your help with the following:
For any fixed $L_2$ I need to decide whether there is closure under the following operators:
$A_r(L)=\{x \mid \exists y \in L_2 : xy \in L\}$
...
5
votes
1answer
128 views
Closure against the operator $A(L)=\{ww^Rw \mid w \in L \wedge |w| \lt 2007\}$
I would like your help with the following question:
Let $L$ be a language, and operator $A(L)=\{\,ww^Rw \mid w \in L\ \wedge\ |w| \lt 2007\,\}$ where $x^R$ is the reversed string of $x$. Which of ...
7
votes
1answer
381 views
How to prove regular languages are closed under left quotient?
L is a regular language over the alphabet $\sum = \{a,b\}$. The left quotient of L regarding $w \in \sum^*$ is the language
$$w^{-1} L := \{v: wv \in L\}$$
How can I prove that $w^{-1}$ L is ...
5
votes
1answer
199 views
Proving closure under complementation of languages accepted by min-heap automata
This is a follow-up question of this one.
In a previous question about exotic state machines, Alex ten Brink and Raphael addressed the computational capabilities of a peculiar kind of state machine: ...
8
votes
1answer
338 views
Proving closure under reversal of languages accepted by min-heap automata
This is a follow-up question of this one.
In a previous question about exotic state machines, Alex ten Brink and Raphael addressed the computational capabilities of a peculiar kind of state machine: ...
6
votes
1answer
445 views
Is an infinite union of context-free languages always context-free?
Let $L_1$, $L_2$, $L_3$, $\dots$ be an infinite sequence of context-free languages, each of
which is defined over a common alphabet $Σ$. Let $L$ be the infinite union of $L_1$, $L_2$, $L_3$, $\dots $;
...
2
votes
3answers
423 views
Closure of Deterministic context-free languages under prefix
For a formal language $L \subseteq \Sigma^{*}$ I define the set Pref(L) to be:
$\text{pref}(L) = \{\alpha \in \Sigma^{*} : \exists \beta \in \Sigma^{*} \text{ such that } \alpha \beta \in L\}$
ie. ...
