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).

reference-request fl.formal-languages regular-language context-free survey 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

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

Odpowiedzi: