patternMinor
Proof that regular languages are closed against taking the even-length subset
Viewed 0 times
thelanguagesarelengthregularclosedagainstthatevensubset
Problem
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.
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.
Solution
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.
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.
Context
StackExchange Computer Science Q#10927, answer score: 5
Revisions (0)
No revisions yet.