I have a language and I am trying to see if it's context-free or not, by trying to use a pumping-lemma but I can't figure it out, been reading a lot of other posts but still struggling to apply it to my example

this is the language (sorry for using an image, i know how to write number exponents but i don't know how to write letters as exponents): language in question whether it's context-free or not


  • $\begingroup$ The pumping lemma for CFLs is a statement that is true voor all CFLs, so you can only use it to prove that a language is not CF by showing the lemma doesn't hold. At first glance this language looks CF to me because I can imagine a pushdown automaton accepting it. Try that approach. $\endgroup$ – Jens Renders Dec 6 '15 at 1:25
  • $\begingroup$ Hi, thanks for the reply, if it looks CF for you could you help me write a CFG for this , because i am still learning them and I wanna see if i can come up with the same CFG you would come up with $\endgroup$ – john3901 Dec 6 '15 at 1:31
  • $\begingroup$ What have you tried? Where did you get stuck? We do not want to just do your exercise for you; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. Your question is a very basic one. Since you did not include much of an attempt to solve it on your own, we have little to work with. Let me direct you towards our reference questions which cover your problem in detail. $\endgroup$ – D.W. Dec 6 '15 at 5:11
  • $\begingroup$ Note that you can use LaTeX here to typeset mathematics in a more readable way, instead of using images. See here for a short introduction. $\endgroup$ – D.W. Dec 6 '15 at 5:11
  • $\begingroup$ The html tag <sup>w</sup> will also create superscript. $\endgroup$ – m69 ''snarky and unwelcoming'' Dec 6 '15 at 22:26

One can proof that a language is CF by constructing a CFG or a PDA for it. I will give an example CFG for this language.

Let the start symbol be $S$.

In the definition we see that we can add arbitrarily many $m$'s, and for each $m$ there have to be two $t$'s. $$M \rightarrow mMtt|\epsilon$$

The same for the $e$'s, but now with one $t$ fot each $e$. $$E \rightarrow tEe|\epsilon$$

Then finally, there has to be an extra $t$. This gives following CFG:

$$S \rightarrow MtE$$ $$M \rightarrow mMtt|\epsilon$$ $$E \rightarrow tEe|\epsilon$$

| cite | improve this answer | |
  • $\begingroup$ Thanks a lot, comparing it with another language items in brackets should be read as powers, i can't type them in here: L1 = {d(2r)p(z)f(r)p(z)d(r) | r, z >= 0} this language looks pretty similar to me could you please show me a CFG for it too in by editing your post? again Thank a lot again starting to become clearer $\endgroup$ – john3901 Dec 6 '15 at 2:10

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.