14
$\begingroup$

It would be nice to collect a list of conditions that imply that a context-free language L is regular, i.e. conditions of the form: "if a given CFG/PDA has property P, then its languages is regular"

The property P does not have to characterize the CFGs generating regular languages. Furthermore, P does not have to be decidable, and P should "somehow depend" on the language being context-free ("the syntactic monoid of L is finite", "L is decidable in space o(log log n)" and so on, are not what I am looking for).

Improve this question
$\endgroup$
5
  • $\begingroup$ seems very likely the general question is undecidable. the analogy is that there are other theorems that "is B actually A" where A is a "smaller" language class than B is undecidable. I recall a question on here wrt maybe CFLs that was similar but cant find it right now. $\endgroup$
    – vzn
    Jun 1, 2012 at 0:49
  • $\begingroup$ by "regularity" you mean, is it really a regular language right? $\endgroup$
    – vzn
    Jun 1, 2012 at 1:16
  • 3
    $\begingroup$ ok found it. this question is very similar to this one, "is a CFG actually a RL" & is known to be undecidable $\endgroup$
    – vzn
    Jun 1, 2012 at 1:21
  • 4
    $\begingroup$ @vzn I think OP is not looking for an algorithm to decide regularity of CFLs but rather for some sufficient conditions. For example, the regularity of a language of a TM is undecidable, but one sufficient condition is that if a language is decidable in $o(n log n)$, then it must be regular. $\endgroup$
    – aelguindy
    Jun 1, 2012 at 8:30
  • $\begingroup$ agreed, distinction is valid. but its also critical to know at same time the general problem is undecidable. "sufficient conditions" are generally closely connected with algorithms eg in the example you gave of o(n lg n) time complexity. $\endgroup$
    – vzn
    Jun 1, 2012 at 15:19

1 Answer 1

Reset to default
15
$\begingroup$

  1. Every unary context-free language is regular. (e.g. a direct consequence of Parikh's theorem)

  2. If every iterative/pumping pair of a context-free language L is degenerated, then L is regular, i.e. L is regular if, for all words x,u,y,v,z it satisfies: $$xu^nyv^nz \in L, \text{for all } n \geq 0 \implies xu^iyv^jz \in L, \text{ for all }i,j \geq 0.$$This was proved by Ehrenfeucht, Rozenberg, "Strong iterative pairs and the regularity of context-free languages", 1983. See "Context-free languages" by Berstel and Boasson for an exposition.

  3. If a context-free language is commutative and linear, then it is regular. (Ehrenfeucht, Haussler, Rozenberg, "On regularity of Context-free Languages", 1983)

Improve this answer
$\endgroup$

Your Answer

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

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