Wystarczające warunki dla prawidłowości języka bezkontekstowego

Byłoby miło zebrać listę warunków, które sugerują, że bezkontekstowy język L jest regularny, tj. Warunki postaci: „jeśli dany CFG / PDA ma właściwość P, to jego języki są regularne”

Właściwość P nie musi charakteryzować CFG generujących zwykłe języki. Ponadto P nie musi być rozstrzygalne, a P powinno „w jakiś sposób zależeć” od tego, czy język jest pozbawiony kontekstu („składowa monoida L jest skończona”, „L jest rozstrzygalna w przestrzeni o (log log n)” i tak na, nie są tym, czego szukam).

— fh
źródło

wydaje się bardzo prawdopodobne, że ogólne pytanie jest nierozstrzygalne. analogia jest taka, że istnieją inne twierdzenia, że „faktycznie B jest A”, gdzie A jest „mniejszą” klasą językową niż B jest nierozstrzygalna. Przypominam sobie pytanie, które może nie dotyczyło świetlówek kompaktowych, ale było podobne, ale nie mogę go teraz znaleźć.

— vzn

przez „regularność” masz na myśli, czy to naprawdę zwykły język, prawda?

— vzn

ok znalazłem to. to pytanie jest bardzo podobne do tego: „jest CFG w rzeczywistości RL” i wiadomo, że jest nierozstrzygalne

— vzn

o (n l o g n)

$o(n log n)$ , to musi być regularny.

— aelguindy

uzgodnione, rozróżnienie jest ważne. ale bardzo ważne jest, aby wiedzieć, że ogólny problem jest nierozstrzygalny. „warunki wystarczające” są na ogół ściśle powiązane z algorytmami, np. w podanym przez ciebie przykładzie o o (n lg n) złożoności czasu.

— vzn

Każdy jednolity język bezkontekstowy jest regularny. (np. bezpośrednia konsekwencja twierdzenia Parikha)
$x u^{n} y v^{n} z \in L., dla wszystkich n \geq 0 ⟹ x u^{ja} y v^{jot} z \in L., dla wszystkich ja, jot \geq 0.$ $xu^nyv^nz \in L, \text{for all } n \geq 0 \implies xu^iyv^jz \in L, \text{ for all }i,j \geq 0.$ Zostało to udowodnione przez Ehrenfeuchta, Rozenberga, „Silne pary iteracyjne i prawidłowość języków bezkontekstowych”, 1983. Zobacz ekspozycję „Języki bezkontekstowe” Berstela i Boassona.
Jeśli język bezkontekstowy jest przemienny i liniowy, to jest regularny. (Ehrenfeucht, Haussler, Rozenberg, „O regularności języków bezkontekstowych” , 1983)

— fh
źródło