Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.


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\}$


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).


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?


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?

Thanks in advance!

share|cite|improve this question
See this related question on cs.SE. – Raphael May 24 '12 at 10:41
up vote 1 down vote accepted

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.

share|cite|improve this answer
great, thank you! – muffel May 24 '12 at 14:31

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.