1
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks! I haven't done inverse operations by now, can you please give an intuitive explanation of what $(aaa)^{-1}$ means? $\endgroup$
    – Dhruv Joshi
    Mar 7, 2021 at 18:18
  • $\begingroup$ $(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). $\endgroup$
    – Steven
    Mar 7, 2021 at 18:23
  • $\begingroup$ 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'$. $\endgroup$
    – Steven
    Mar 7, 2021 at 18:28
  • 1
    $\begingroup$ 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. $\endgroup$
    – Hendrik Jan
    Mar 7, 2021 at 20:00

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.