Tagged Questions
0
votes
1answer
80 views
Proof that the regular languages are closed under string homomorphism
Where can I find a proof of this? Thanks!
-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
122 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 ...
6
votes
2answers
70 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 ...
4
votes
4answers
128 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
64 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.
3
votes
1answer
92 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
118 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
243 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 ...
2
votes
1answer
88 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?
1
vote
1answer
82 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 ...
2
votes
2answers
174 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
130 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 ...
8
votes
1answer
265 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 ...
4
votes
1answer
371 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 ...
8
votes
2answers
322 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
378 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 ...
