# Regular languages - models of computation [duplicate]

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

• 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
• 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