# Regular languages - models of computation [duplicate]

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$?

• 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. – Dave Clarke Feb 10 '13 at 20:34
• Another hint: things don't change if in both languages $x,y \in 1^*$ (instead of $x,y \in \{0,1\}^*$) – Vor Feb 10 '13 at 21:02
• 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. – Paresh Feb 10 '13 at 21:25
• 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 ... – Vor Feb 10 '13 at 21:33
• Hint: even + even = even, odd + odd = even. – saadtaame Feb 10 '13 at 21:36