0

If there is a regular language $M$ over $\Sigma = \{0,1\}$, then show that language $$L = \{x : x\in M \text{ and $x$ ends in 10}\}$$ is regular as well. I'm thinking of closure under Union or Difference but cannot connect the dots.

Really appreciate any suggestions.

M.G
  • 3,709
heevmo
  • 3

1 Answers1

1

HINT: The intersection of two regular languages is regular. In case you don’t already have this result available, you can prove it by starting with finite state machines accepting the two languages and combining them to get a finite state machine that accepts their intersection. The combination uses what is often called the product construction, since the state set of the new machine is the Cartesian product of the state sets of the original two machines.

Brian M. Scott
  • 616,228
  • @Arthur: No, it is unquestionably a result. It is not part of the definition of regular language; it is a derived consequence of that definition, and a not entirely trivial one at that. – Brian M. Scott Nov 05 '16 at 19:54
  • Never mind, it says union. I'm tired, apparently. – Arthur Nov 05 '16 at 19:57
  • For intersection I'm thinking of M intersect M' = L. M is regular so I'll have to find a language M' which is regular? – heevmo Nov 05 '16 at 20:07
  • @heevmo: Yes. Consider the language corresponding to the regular expression $(0+1)^*10$. – Brian M. Scott Nov 05 '16 at 20:16