Czy zwykłe języki są zamknięte pod sortowaniem (obraz Parikh)?

Załóżmy, że to zwykły język nad uporządkowanym alfabetem. Czy język jest zbudowany przez wzięcie każdego słowa w i posortowanie go zawsze jako zwykłego języka? $L$ $L$

formal-languages regular-languages

— Andrzej
źródło

Odpowiedzi:

Nie. Przeciwprzykład: zakładając, , mamy , którego nie można wyrazić wyrażeniem regularnym, lematem pompującym dla zwykłych języków . $a < b$ $(ab)^\ast \xrightarrow{\;\;\text{sorted}\;\;} \{ a^n b^n \;|\; n \geqslant 0 \}$

— Niel de Beaudrap
źródło

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.

Licensed under cc by-sa 3.0 with attribution required.