Problem Detail:
Possible Duplicate:
How to prove that a language is not regular?
Why $L_a$ and $L_b$ are not reguluar? $L_a = { e^i f^{n-i} g^j h^{n-j} : n in N, 1 leq i, j leq n }$. $L_b= {nm^{i_1} nm^{i_2}…bn^{i_z}: z in N, (i_1,…,i_n) in N^z, 1 leq j leq z, i_j ≠ j }$.
Asked By : corium
Answered By : David Lewis
Hints… $L_a$ can be transformed into an well-known non-regular language by a very simple homomorphism that basically “loses” information. For $L_b$ you might try transforming it into its “opposite” (that is, equality in place of inequality) by operations known to preserve regular languages. The “opposite” language might then be amenable to a pumping argument. Also, try “testing” your argument on a much simpler version of $L_b$ which, although it is regular, will let you see the patterns to use for the full $L_b$. PS — these are both techniques that might be added to the reference post that Dave Clarke points to. I will do so when this question has settled down. Thinking a bit more about $L_b$, the idea I had in mind to derive the “opposite” language may not lead directly to an easy solution. So here’s a hint in a different direction. There are a lot of $m^{i_j}$ in each string of that language. If you could “isolate” those strings of $m's$ by an appropriate regularity-preserving operation, you might get a simpler language that is amenable to a proof, perhaps by pumping or perhaps by the “opposite” idea. Also, think about what each $i_j neq j$ means in terms of other symbols in the string.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/1753
