Redirected
edited by
801 views
1 votes
1 votes

Let $R$ be a regular language and $L$ is a language which accepts only even length strings from $R$. Then $L$ is

  1. Always Regular
  2. Always Not Regular
  3. Sometimes Regular, but not always
  4. None
edited by

2 Answers

Best answer
5 votes
5 votes

Let $E$ be the set of all event length strings over $\sigma^*$ which is regular as we can easily get a DFA for this. Now, $L = R \cap E$ and since intersection being closed for regular set, $L$ must be a regular set.


Since $R$ is regular we can have a DFA for $R$. Now, mark all the final states of the DFA and identify the ones where a string is reachable with even length. At this point we can have states where both the strings of even/odd length can be reached and in such cases we have to replicate the state (reverse of what we do in DFA minimization). After this we get a DFA for $L$ and so $L$ is always regular.

PS: Sorry, the proof is more of an intuition and not mathematical.

edited by

Related questions

1 votes
1 votes
1 answer
2
KISHALAY DAS asked Nov 7, 2016
274 views
0 votes
0 votes
0 answers
3
KISHALAY DAS asked Nov 7, 2016
931 views
0 votes
0 votes
0 answers
4
KISHALAY DAS asked Nov 7, 2016
478 views