Kondisi yang memadai untuk keteraturan bahasa bebas konteks

Akan menyenangkan untuk mengumpulkan daftar kondisi yang menyiratkan bahwa bahasa bebas konteks-L adalah reguler, yaitu syarat-syarat bentuk: "jika CFG / PDA yang diberikan memiliki properti P, maka bahasanya adalah reguler"

Properti P tidak harus mengkarakterisasi CFG yang menghasilkan bahasa reguler. Selanjutnya, P tidak harus decidable, dan P harus "entah bagaimana bergantung" pada bahasa yang bebas konteks ("monoid sintaksis L adalah terbatas", "L dapat di decidable dalam ruang o (log log n)" dan sebagainya pada, bukan apa yang saya cari).

1. Setiap bahasa bebas konteks unary teratur. (misalnya konsekuensi langsung dari teorema Parikh)

2. $$xu^nyv^nz \in L, \text{for all } n \geq 0 \implies xu^iyv^jz \in L, \text{ for all }i,j \geq 0.$$

3. Jika bahasa bebas konteks adalah komutatif dan linear, maka itu adalah reguler. (Ehrenfeucht, Haussler, Rozenberg, "Pada keteraturan bahasa bebas konteks" , 1983)