16
$\begingroup$

Is there an algorithm/systematic procedure to test whether a language is context-free?

In other words, given a language specified in algebraic form (think of something like $L=\{a^n b^n a^n : n \in \mathbb{N}\}$), test whether the language is context-free or not. Imagine we are writing a web service to help students with all their homeworks; you specify the language, and the web service outputs "context-free" or "not context-free". Is there any good approach to automating this?

There are of course techniques for manual proof, such as the pumping lemma, Ogden's lemma, Parikh's lemma, the Interchange lemma, and more here. However, they each require manual insight at some point, so it's not clear how to turn any of them into something algorithmic.

I see Kaveh has written elsewhere that the set of non-context-free languages is not recursively enumerable, so it seems there is no hope for any algorithm to work on all possible languages. Therefore, I suppose the web service would need to be able to output "context-free", "not context-free", or "I can't tell". Is there any algorithm that would often be able to provide an answer other than "I can't tell", on many of the languages one is likely to see in textbooks? How would you build such a web service?


To make this question well-posed, we need to decide how the user will specify the language. I'm open to suggestions, but I'm thinking something like this:

$$L = \{E : S\}$$

where $E$ is a word-expressions and $S$ is a system of linear inequalities over the length-variables, with the following definitions:

  • Each of $x,y,z,\dots$ is a word-expression. (These represent variables that can hold any word in $\Sigma^*$.)

  • Each of $a,b,c,\dots$ is a word-expression. (Implicitly, $\Sigma=\{a,b,c,\dots\}$, so $a,b,c,\dots$ represent a single symbol in the underlying alphabet.)

  • Each of $a^\eta,b^\eta,c^\eta,\dots$ is a word-expression, if $\eta$ is a length-variable.

  • The concatenation of word-expressions is a word-expression.

  • Each of $m,n,p,q,\dots$ is a length-variable. (These represent variables that can hold any natural number.)

  • Each of $|x|,|y|,|z|,\dots$ is a length-variable. (These represent the length of a corresponding word.)

This seems broad enough to handle many of the cases we see in textbook exercises. Of course, you can substitute any other textual method of specifying a language in algebraic form, if you like.

$\endgroup$
  • $\begingroup$ Wouldn't it be easier to start with regularity of languages? $\endgroup$ – Yuval Filmus Nov 11 '13 at 20:05
  • $\begingroup$ @YuvalFilmus, sure would! Now that you mention it, that's a great idea. Do you think the problem is feasible for regular languages? I'd be happy to ask a corresponding about regular languages, if you think that might be valuable. $\endgroup$ – D.W. Nov 11 '13 at 20:46
  • 2
    $\begingroup$ It would certainly be easier for regular languages. By the way, the general non-decidability doesn't necessarily apply to languages of the form you mention. $\endgroup$ – Yuval Filmus Nov 11 '13 at 23:50
  • 4
    $\begingroup$ I'm afraid this problem is probably open, at least a specific case is: cstheory.stackexchange.com/questions/17976. There might be a way to get undecidability for your more general problem, but I don't see it. $\endgroup$ – sdcvvc Nov 12 '13 at 14:55
  • $\begingroup$ it would be helpful to give some example words in the language. suggest further research/ collaboration in Computer Science Chat $\endgroup$ – vzn Sep 18 '14 at 19:10
-2
$\begingroup$

Try JFLAP software if you just want to check a CFG. You can maybe even ask JFLAP developers to give you the code or algorithm for the software. you can get JFLAP from here http://www.jflap.org/jflaptmp/ it is free however it requires JDK or JRE or something. Or maybe you can try some other similar softwares and their developers.

$\endgroup$
  • 1
    $\begingroup$ I'm not sure this answers the question. JFLAP has no feature that accepts a language in mathematical notation and tells you whether it is context-free or not. $\endgroup$ – Yuval Filmus Nov 2 '18 at 16:08
  • $\begingroup$ THEOREM 2.20 in Sipser book A language is context free if and only if some pushdown automaton recognizes it. And you can build PDA in JFLAP from a grammar $\endgroup$ – Haseeb Hassan Asif Nov 2 '18 at 16:39
  • $\begingroup$ You maybe right about mathematical notation that can't be put in JFLAP but you can still put all rules of a grammar and it can either convert it into a PDA or says it is not a CFG or some other error $\endgroup$ – Haseeb Hassan Asif Nov 2 '18 at 16:41
  • $\begingroup$ How would you represent $\{a^nb^nc^n : n \in \mathbb{N}\}$ as a grammar? Also, it is probably undecidable to tell whether an unrestricted grammar generates a context-free language, so I doubt JFLAP can do that. $\endgroup$ – Yuval Filmus Nov 2 '18 at 16:45
  • 1
    $\begingroup$ I imagine that JFLAP can convert a context-free grammar to an equivalent PDA, but this is of absolutely no help here. $\endgroup$ – Yuval Filmus Nov 2 '18 at 16:45

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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