This question already has an answer here:

As far as a I understand, a regular language is a set of words that can be run in a DFA.

$L_1 = \{ x\#y \mid x,y \in \{0,1\}^* \ \text{and} \ |x| = |y| \}$

$L_2 = \{ xy \mid x,y \in \{0,1\}^* \ \text{and} \ |x| = |y| \}$

$L_1$ is not regular but $L_2$ is, why is that? Is it possible to create a DFA that accepts $L_2$ (it needs to remember the length of $x$) if so, why is it impossible to do it with $L_1$?


marked as duplicate by Yuval Filmus, Pål GD, Ran G., Raphael Feb 11 '13 at 6:03

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

migrated from cstheory.stackexchange.com Feb 10 '13 at 20:32

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

  • 4
    $\begingroup$ Hint: read very carefully what L2 says, or perhaps, what it doesn't say compared to L1. Think about what kind of strings are in each language. $\endgroup$ – Dave Clarke Feb 10 '13 at 20:34
  • $\begingroup$ Another hint: things don't change if in both languages $x,y \in 1^*$ (instead of $x,y \in \{0,1\}^*$) $\endgroup$ – Vor Feb 10 '13 at 21:02
  • $\begingroup$ I'm not sure if I should give this hint, but here goes. You are right in thinking that remembering length should be impossible for a DFA. $\endgroup$ – Paresh Feb 10 '13 at 21:25
  • $\begingroup$ Yet another hint :-); if you pick $x=1001$,$y=11$, then you may think that $xy$ doesn't belong to $L_2$ ... but if you pick $x'=100$,$y'=111$ you'll certainly say "Yeah $x'y'$ belongs to $L_2$!" ... but now compare $x'y'$ to ... $\endgroup$ – Vor Feb 10 '13 at 21:33
  • $\begingroup$ Hint: even + even = even, odd + odd = even. $\endgroup$ – saadtaame Feb 10 '13 at 21:36