0

Let $R$ be a regular language and $R_e := \{w\ |\ w \in R \text{ and the length of } w \text{ is even}\}$

Question: Is $R_e$ regular? Prove your answer.

I am having trouble with these type of questions. Can anyone help?

Lord_Farin
  • 17,743
a b
  • 21

1 Answers1

1

Yes: Intuitively, you can modify any automaton accepting $R$ to additionally keep track of the parity of the length of the string processed so far.

A little bit more formally, pick a finite automaton accepting $R$ and construct a new one accepting $R_e$ by doubling the set of states and having all transition maps go between the two copies of the states. The initial and terminal states of the original automaton are put in precisely one of the two copies.

Addendum with requested details: Suppose ${\mathcal R}$ is defined over the alphabet $\Sigma$ and that it is accepted by the finite automaton $({\mathcal S},s_0,{\mathcal T},\delta)$, where ${\mathcal S}$ are the states of the automaton, ${\mathcal T}$ are the terminal states, $\delta: {\mathcal S}\times\Sigma\to{\mathcal S}$ defines the state transitions and $s_0\in{\mathcal S}$ is the initial state. Then consider the automaton with state set ${\mathcal S}\times\{\text{even},\text{odd}\}$, initial state $(s_0,\text{even})$, terminal states ${\mathcal T}\times\{\text{even}\}$ and transition map $((s,\text{even}),x)\mapsto (\delta(s,x),\text{odd})$ and $(s,\text{odd}),x)\mapsto (\delta(s,x),\text{even})$. Then this automaton accepts precisely ${\mathcal R}_e$.

Note that this is a special case of the fact - proved very similarly way - that the intersection of two regular languages is again regular.

Hanno
  • 19,510
  • i would prefer more details – a b Jan 21 '15 at 07:45
  • But this does help, thanks – a b Jan 21 '15 at 07:51
  • @ab: btw, I don't know why your questions got downvoted twice, I'm sorry for that (I gave it an upvote). Apart from the formatting for which you can use LaTeX everything's fine. – Hanno Jan 21 '15 at 08:25
  • thank you, i am still a little confused but i believe i am getting there. Can you explain the second automation you described and why it accepts R_e – a b Jan 21 '15 at 08:28
  • @ab: If you can locate what causes the confusion, just ask :) – Hanno Jan 21 '15 at 08:29
  • Can you explain the second automation you described again and why it accepts R_e? – a b Jan 21 '15 at 08:30
  • The second automaton has two states for every state of the first automaton for keeping track whether so far an even or an odd number of symbols has been read. Apart from that, the automaton behaves exactly the same. The initial state is the initial state of the old automaton colored even (in the beginning, no signs have been read), while the terminal states are those of the old automaton, again colored even (you want to accept those words which where accepted by the old automaton and which are of even length). – Hanno Jan 21 '15 at 08:32
  • since the automation accepts R_e, then we can state that it is regular based of the theorem that "a language is regular if and only if some nondeterministic finite automation recognizes it". Is this correct? – a b Jan 21 '15 at 08:38
  • Yes, here it's even an determinstic finite automaton. If you refer to this as a theorem: what is your definition of regular language? – Hanno Jan 21 '15 at 08:42
  • i just looked, the theorem and definition are similar. – a b Jan 21 '15 at 08:43
  • Your explanation helped me a lot, I was wondering if you could help me think through another question related to languages. I will post it now – a b Jan 21 '15 at 08:44