2
$\begingroup$

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

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

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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