Достаточные условия регулярности языка без контекста

Было бы неплохо собрать список условий, которые подразумевают, что язык L без контекста является регулярным, то есть условия вида: «если данный CFG / PDA имеет свойство P, то его языки являются регулярными»

Свойство P не должно характеризовать CFG, генерирующие регулярные языки. Кроме того, P не должен быть разрешимым, и P должен «как-то зависеть» от языка, не зависящего от контекста («синтаксический моноид L конечен», «L разрешим в пространстве o (log log n)» и т. Д. не то, что я ищу).

reference-request fl.formal-languages regular-language context-free survey ФХ
источник

кажется очень вероятным, что общий вопрос неразрешим. аналогия в том, что существуют другие теоремы, что «на самом деле B», где A - «меньший» языковой класс, чем B, неразрешима. Я вспоминаю вопрос здесь, может быть, КЛЛ, который был похож, но не могу найти его прямо сейчас.

ВЗН

под "регулярностью" вы подразумеваете, действительно ли это обычный язык, верно?

2012 года

хорошо нашел это. этот вопрос очень похож на этот, «на самом деле это

КФГ

o (n l o g n)

$o(n log n)$

согласен, различие в силе. но также важно знать, что общая проблема неразрешима. «достаточные условия», как правило, тесно связаны с алгоритмами, например, в приведенном вами примере о (n lg n) временной сложности.

ВЗН

Каждый унарный контекстно-свободный язык является регулярным. (например, прямое следствие теоремы Париха)
$Икс U^{N} Y v^{N} Z \in L, для всех N \geq 0 ⟹ Икс U^{я} Y v^{J} Z \in L, для всех я, J \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.$
Если контекстно-свободный язык является коммутативным и линейным, то он регулярный. (Эренфойхт, Хауслер, Розенберг, "О регулярности контекстно-свободных языков" , 1983)

ФХ
источник

Достаточные условия регулярности языка без контекста

Ответы: