5
$\begingroup$

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 = \{0, 1\}$. Show that the language

$\qquad L' = \{w \in L \mid |w| \in 2\mathbb{N}\}$

is also regular.

What I find surprising is that the booklet mentions that the language $\{w \in L \mid |w| = 2^k, k \in \mathbb{N}\}$ is not necessarily a regular language.

$\endgroup$

migrated from cstheory.stackexchange.com Mar 31 '13 at 5:11

This question came from our site for theoretical computer scientists and researchers in related fields.

  • 3
    $\begingroup$ by closure properties, do intersection of $L$ with $E=\{w \mid |w|$ is even $\}$. $\endgroup$ – Ran G. Mar 31 '13 at 7:00
  • 2
    $\begingroup$ Which closure properties have you tried? As the answers illustrate, there is a very basic answer using closure properties. For the second part of the question, see our reference question; I imagine that Parikh's theorem is interesting for you. $\endgroup$ – Raphael Apr 2 '13 at 8:18
5
$\begingroup$

The language $Even = \{w\in\Sigma^{\ast}\mid \text{length of }w\text{ is even}\}$ is regular. user5507's answer demonstrates this with an NFA, and it's a basic exercise in most texts.

Then given that $L$ is regular, if we know that regular languages are closed under intersection for the purposes of the question, then the language $L'=L\cap Even$ is also regular.

If we're not allowed to use these closure properties, we can recapitulate the construction that gives the closure property (I'll just sketch it). Given a DFA $M_{L}$ for $L$ and a DFA $M_{Even}$ for $Even$, we can construct a DFA for $L' = L\cap Even$ that has a state space that is the product of the state spaces of $M_{L}$ and $M_{Even}$, with the follow transition rule: if $\delta_{L}(\sigma, q_{i}) = q_{j}$ and $\delta_{Even}(\sigma, p_{m})=p_{n}$ where $\sigma \in \Sigma$ and the $p$s and $q$s are states of the appropriate machines, then the product machine has a transition $\delta_{prod}(\sigma,(q_{i}, p_{m})) = (q_{j}, p_{n})$. Our accepting states are those states $(q_{i},p_{j})$ where $q_{i}$ and $p_{j}$ are accepting states in their respective machines.

That's the long an fiddly way around.

The second question depends on $L$, that is, if $L$ is not regular, then the intersection of $L$ and $Even$ may is not necessarily regular - the $w\in L$ in the definition is key.

EDIT: actually, reading vonbrand's answer, I misunderstood the second part. He is quite correct - the second language is the intersection of $L$ and $X=\{w\in\Sigma^{\ast}\mid \exists i \in \mathbb{N} \text{ such that } |w| = 2^{i}\}$ - not $Even$. So while what I said about $L \cap Even$ with $L$ not regular holds, $X$ isn't regular to begin with, so we get the same situation, but $L$ is regular and $X$ isn't.

$\endgroup$
3
$\begingroup$

For the language with lengths an integer power of two, they can be regular only if they are finite. It is easy to prove by the pumping lemma that an infinite language of such kind can't be regular (just look at the lengths of the strings).

$\endgroup$
0
$\begingroup$

If the number of even-length strings in $L$ is finite (say $w_i,i \in \{1,\dots,n\}$, then $L^\prime$ is regular and the regex $(w_1\mid \dots \mid w_n)$ accepts it. If it's infinite, then by the pumping lemma we know that for strings $w \in L$, there are strings $x,y,z$ such that $w=xy^iz\in L$ for $i=0,1,2,\dots$. A case-analysis is required:

  1. $x,y,z$ are odd-length, $i$ is even: the regex $x(yy)^*z$ accepts case-1 even-length strings.

You should be able to fill in the missing cases. Now a regex accepting strings in $L^\prime$ can be formed by taking the union of the regex's of each case. The resulting regex accepts even-length strings in $L$.

$\endgroup$
-2
$\begingroup$

We need to show that

$\{w ∈ L |$ length of w is even$\}$ is regular.

In order to show that, it is enough to construct an NFA/DFA for that. You can construct an NFA for this like

enter image description here

$\endgroup$
  • 1
    $\begingroup$ Not exactly. This is a DFA for $L=\{w \mid |w|$ is even $\}, and not the language the OP asked for.. $\endgroup$ – Ran G. Mar 31 '13 at 6:59
  • $\begingroup$ @RanG. OP asked for the same thing. I have given an NFA, not a DFA. $\endgroup$ – user5507 Mar 31 '13 at 7:55
  • $\begingroup$ @user5507 The OP's question is: given a regular language $L$, show that all even sized words of $L$ also form a regular language. What you show is that a language with only even sized words is regular. $\endgroup$ – Paresh Mar 31 '13 at 9:11
  • $\begingroup$ @Paresh $L$ is defined over $\Sigma=\{0,1\}$. Then his $L$ means all even sized words. That is what I represented using NFA!. Can you please elaborate on where I went wrong? $\endgroup$ – user5507 Mar 31 '13 at 14:16
  • 2
    $\begingroup$ $L$ is a regular language. $L^\prime$ is a language that only contains even sized words which are also in $L$. So, as an example, if $L = \{0,1,00\}$, then $L^\prime = \{00\}$. If $L=\{0,1\}$, then $L^\prime$ is empty. And so on. $\endgroup$ – Paresh Apr 2 '13 at 5:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy