# Show that the Language is irregular

I was solving some problem from past test, there was this question:

Use the closure property of regular language to show the language $$L$$ is not regular

$$L =\{ a^3 b^n c^{n-3} \mid n>3\}$$

I know how to solve it using Pumping Lemma, but how to solve it with closure property?

Also, I know that to prove that a language L is not regular using closure properties, the technique is to combine L with regular languages by operations that preserve regularity in order to obtain a language known to be not regular, but I can't figure out with whom to combine.

I saw some similar questions but didn't get ideas about how to do this one.

Any hints?

Thanks.

Suppose that $$L$$ is regular. Then so is $$L' = L \circ \{ccc\} = \{a^3 b^n c^n \mid n \ge 3\}$$. This implies that $$L'' = (aaa)^{-1}L' = \{b^n c^n \mid n \ge 3\}$$ is also regular and, in turn, that $$L''' = L'' \cup \{\varepsilon, bc, bbcc\} = \{b^n c^n \mid n \in \mathbb{N}\}$$ is regular. This is a contradiction since $$L'''$$ is known not to be regular.

• Thanks! I haven't done inverse operations by now, can you please give an intuitive explanation of what $(aaa)^{-1}$ means? – Dhruv Joshi Mar 7 at 18:18
• $(aaa)^{-1} L'$ denotes the left quotient of $L'$ by $aaa$ and is defined as the language containing all words $x \in \Sigma^*$ such that $aaax \in L'$. To see that regular languages are closed under this operation, pick a DFA $D$ for $L'$ and feed the word $aaa$ to it. You end up in some state $q$ of $D$. Construct a new DFA $D'$ that is a copy of $D$ except that the initial state is now changed to $q$. The words accepted by $D'$ are exactly those in $(aaa)^{-1} L'$ (this strategy works in general: for $\alpha \in \Sigma^*$ and some language $L$ you can show that $\alpha^{-1}L$ is regular). – Steven Mar 7 at 18:23
• Intuitively: you are taking all words of $L'$ that start with $aaa$ and dropping the $aaa$ prefix. What you are left with is $(aaa)^{-1}L'$. – Steven Mar 7 at 18:28
• Alternatively, if you do not want to use left quotient to remove the symbols $a$ at the start of the string, you can use the operation of homomorphism which is able to replace letters by new strings. In this case, replace every $a$ by the empty string $\varepsilon$, effectively deleting all $a$'s. – Hendrik Jan Mar 7 at 20:00