# Prove irregularity of a language using closure properties

Given the language $$L=\{a^{j+1}b^kc^{j-k}|j\ge k\ge 0 \}$$ I need to prove that it is not a regular language using closure properties.

I was having a trouble handling $$a^{j+1}$$ so I tried to prove this first for $$L_1 = \{a^jb^kc^{j-k}|j\ge k\ge 0 \}$$, I assume $$L_1$$ is regular and define an homomorphism $$h: \{a,b,c\}\rightarrow \{a,b\}$$ such that $$h(a) = b,\space h(b) = a,\space h(c)=\varepsilon$$ and I get $$L_2=h(L_1)= \{b^ja^k|j\ge k\ge 0 \}$$ which is also regular by my assumption and the closure of homomorphism, and from the reverse closure I get $$L_3 = L_2^R = \{a^kb^j|j\ge k\ge 0 \}$$ is also a regular language but I already know that $$L_3$$ isn't regular, a contradiction, therefore, $$L_1$$ isn't regular.

Going back to the original language $$L$$, I think I need to find a way to reach $$L_1$$ from $$L$$ while using closure properties so the assumption of $$L$$'s regularity leads to a contradiction, but so far I couldn't find any

• An easier solution is to identify $b$ and $c$ and tack on a final $b$ (or remove an initial $a$). Apr 19 at 5:11

Suppose that $$L$$ is regular. Since regular languages are closed under intersection, then $$K = L \cap a^*c^* = \{a^{j+1}c^j \mid j \geqslant 0 \}$$ would be regular and the left quotient of $$K$$ by $$a$$ $$a^{-1}K = \{u \mid au \in K\} = \{a^jc^j \mid j \geqslant 0 \}$$ would also be regular. I suppose you already know that this latter language is not regular. Thus $$L$$ is not regular.

Assume $$L_3 = \{a^kb^j|j\ge k\ge 0 \}$$ is the only language that is known to be non-regular.

Let $$L_4=\{b\}$$, the language that contains one string, $$c$$. Then $$(h(L\circ L_4)\cup\{\epsilon\})^R=L_3$$. Since $$L_3$$ is non_regular but $$L_4$$ and $$\{\epsilon\}$$ are regular and regular languages are closed under concatenation, homomorphism, union and reversal, $$L$$ must be non-regular.

Let $$L_5=\{a\}$$. Then $$(h(L_5\backslash L))^R=L_3$$, where $$L_5\backslash L$$ is the left quotient of $$L$$ by $$L_5$$. Since $$L_5$$ is regular and regular languages are closed under left quotient, homomorphism and reversal, $$L$$ must be non-regular.

It might be more reasonable to assume that $$L_6=\{a^nb^n\mid n\ge0\}$$ is known to be non-regular, since that is the first language presented as non-regular in many textbooks.

Exercise. With the assumption above, show $$L$$ is non-regular using closure properties.