I have no idea how to approach this question... How would I go about proving or disproving this? any explanation is appreciated.

  • $\begingroup$ cs.stackexchange.com/q/18524/755 $\endgroup$
    – D.W.
    Dec 18, 2022 at 8:53
  • $\begingroup$ We're not looking for posts that are just the statement of an exercise-style task and a request for us to solve it. We're looking to build an archive of knowledge that will be useful to others in the future. What did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. If you don't know where to start, it's probably premature to ask a question here. $\endgroup$
    – D.W.
    Dec 18, 2022 at 8:54
  • $\begingroup$ Hi, I just want to clarify no statement was made for anyone to solve it. I was hoping for some guidance and help to get a start in the right direction... It just turns out that someone went the extra mile for me which was greatly appreciated. Happy Holidays. $\endgroup$
    – emrb99
    Dec 18, 2022 at 11:29
  • $\begingroup$ If you want to know how to prove that a language is context-free, you can search this site and you will already find explanations of methods. Same for disproving. We expect you to search the site before asking, and try to apply what you've found. $\endgroup$
    – D.W.
    Dec 18, 2022 at 18:08

1 Answer 1


As nothing is mentioned about $j,k$ I can think of 2 possible cases,

Case 1: when $j,k \in N$

$L = $ {$a^{n}$ | $n=3j+4k>=0$}

We have to find possible solutions of $3j+4k>=0$, for $j,k >=0$ this equation holds true, we can rewrite $a^{n}$ as follow

$a^{n} = a^{3j+4k}$ $=a^{3j}.a^{4k}$ $=(a^{3})^{j}.(a^{4})^{k}$

from here the language can be written as $L=(a^{3})^{*}(a^{4})^{*}$, as we have obtained a regular expression our language $L$ is regular as well as context-free

Case 2: when $j,k\in R$

Any whole number $n$ can be written as $3j+4k$ where $j=n/6, k=n/8$ hence our language $L$ becomes $a^{*}$ which is regular and content-free also.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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