My first post here, so glad I found this great place. Hoping I could improve and learn a lot from you and contribute in the future if I can.

I have a problem with the following scenario:

Given $\Sigma= \{a,b,c,d\}$, prove that $L$ is not regular, where $$L = \{a^ib^jcd^k \mid i \geq 0; k > j > 0\}$$ using: 1) pumping lemma 2) closure properties.

Regarding 1)

Assuming that $L$ is regular, using the pumping lemma there should exist some integer $n$ (pumping length). Choosing a word $w \in L$ (not sure if I chose the right word). If $w=a^ib^jcd^k$ ($|w|>n$), but I cannot find a way to obtain $xy^i z \notin L$, would very appreciate an explanation or example of how you found the term so it can be concluded that $L$ is not regular using the pumping lemma.

Regarding 2)

Assuming that $L$ is regular, it means that $a^ib^jcd^k$ is also regular. So it should be closed under intersection, however, the form of $\{a^ib^jcd^k \mid i\geq 0;k>j>0\}$ is not regular, and it can be achieved using completion, so contradiction and because of that $L$ is not regular.

Hoping to learn from my mistakes and improve.

Thank you very much for your aid.


For (1): You assume the language satisfies the pumping lemma for some $n$. You want to choose a word that would have at least one of its letters related to $n$. A good start would be taking one of your letters $l\in w$ to be $l^n$, and using that to show that for some $i$, $xy^iz\notin L$

For (2): You want to show that if $L$ is regular, then some other language $L_{not}$ which you know is not regular, is the intersection of another regular language $L_{reg}\cap L=L_{not}$.


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.