# Proving that languages are not regular

The Nerode Lemma can be used to show whether a language is regular or not. This can be done in several ways but I need to do it by providing a set of separable items.

Example:

The language of well-formed brackets ($\Sigma = \{(,)\}, L = \{(),()(),(()), ...\}$ is not regular. That can be shown by providing the separable, infinite set $\{\epsilon,(,((,(((,...\}$ because

• $)$ separates $\epsilon$ and $($ because $\epsilon) \not\in L$ but $() \in L$
• $))$ separates $\epsilon$ and $(($ because $\epsilon)) \not\in L$ but $(()) \in L$
• ...
• $)^n$ separates $(^n$ and $(^k$ for $n \neq k$ because $(^n)^n \in L$ but $(^k)^n \not\in L$

a finite state machine for that language whould therefore require an infinite number of states $\Leftrightarrow$ the language is not regular.

Now I need to repeat that for two languages:

1) $L_1 = \{u \in \Sigma^* \; | \; \exists i \leq k \leq j : u = 1^i 2^j 1^k\}, \Sigma_{L_1} = \{1,2\}$

$\hspace{1cm}$

2) The language that represents a simplified "programming language" that allows only declaring and using of variables. There is no length-restriction for variable names and a variable may be of one of the fictitious types X, Y or Z. Commands (usage of variables or declarations) are separated by spaces. A variable name may contain any lowercase letter (a-z). Therefore $\Sigma_{L_2} = > \{X,Y,Z,\text{' '},a,\cdots,z\}$ and a valid word may be "X a Y ab a ab a" (declare a as X, ab as Y and use both, a and ab). An invalid world would be "X a c" or just "c" because c is not declared first.

Unfortunately I still don't know how to construct these sets apart from "trial and error" (and I'm not quite good at that).

1)

I thought about the set $\{ 2^x 1^{x+1} \; | \; x \in N\}$. If I am right this separates the words $v = 12^x1^{x+1} \not\in L$ and $w = 22^x1^{x+1} \in L$. Is this correct?

2)

I really don't know how to start creating prefixes or suffixes for that language. Can you please help me to get on with it?