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

-
See this related question on cs.SE. –  Raphael May 24 '12 at 10:41

You should reformulate your first answer to call the infinite set the separated one (unless you have proved the equivalence of the notions before).

As for your second example, you can take any suffix that necessitates a declaration first and then either provide the declaration or not.

-
great, thank you! –  muffel May 24 '12 at 14:31