Linguagem regular como união finita de conjuntos periódicos

Question

É verdade que toda linguagem regular pode ser expressa como uma união finita de conjuntos periódicos?Em outras palavras, se $ l $ é regular, então haja definições finitas $ a_1, \ Dots, A_N, B_1, \ DOTS, B_N $ tal que

$$ l= a_1 \ cdot b_1 ^ * \ cope \ cdoz \ cope a_n \ cdot b_n ^ *. $$

Eu sei que isso é verdade para idiomas regulares sobre um alfabeto unário, mas não tenho certeza sobre alfabetos gerais.

Answer 1

Cada idioma deste formulário pode ser representado como uma expressão regular sem a estrela de Kleene aninhada.Isto é, é o seu estelar a altura é $ 1 $ .O hierarquia de altura da estrela é rigorosa e, em particular, sabe-se que a linguagem $ (a ^ * b ^ * c) ^ * $ não pode ser representado nesse formulário.Um exemplo sobre um alfabeto binário seria $ (AA (ab) ^ * bb (ab) ^ *) ^ * $ .

Answer 2

A resposta por @yuvalfilmus está perfeitamente bem, e aponta para a noção de importação de Estrela de altura . Mas deixe-me adicionar um pouco mais. Vamos mostrar que idiomas do seu formulário dão um subconjunto adequado das línguas da estrela altura uma. Mas primeiro, algumas reflexões o que pode chegar perto do seu formulário.

idiomas regulares gerais

Primeiro, provavelmente a forma mais próxima do seu para a sua para regular $ l \ subseteq \ sigma ^ * $ , aceito por um automatismo determinístico completo $ a= (\ sigma, q, \ delta, q_0, f) $ . Para $ \ \ em q $ e $ e \ subseteq q $ , escreva $ l_ {q, e} (a) $ para o idioma aceito por $ (\ sigma, q, \ delta, q, e) $ , ou seja, alterando o estado de início para $ Q $ e o conjunto de estados finais para $ e $ . Então, podemos escrever $$ L=bigcup_ {\ in f} l_ {q_0, q} (a) l_ {q \ {\ \}} (a) ^ * $$ Este resultado parece ser folclore e segue facilmente. Pode ser um pouco fortalecido, substituindo $ l_ {q_0, \ {\ \}} (a) $ pelo idioma $$ \ {U \ in l_ {q_0, \ {\ \}} \ mid \ delta (q_0, v) \ ne \ mbox {para cada prefixo adequado $ v $ de $ u $}} $$ na equação acima. Tem a propriedade que nenhuma palavra é um prefixo adequado de outra palavra. Uma variante desta decomposição, e mais refinamentos, aparecem no livro Automatá, idiomas e máquinas, volume a por S. Eilenberg, sob o nome UP-decomposição iterada . / p >.

idiomas regulares comutativos e limitados

Outros formam, mais perto da sua, e sendo generalizações adequadas do caso de linguagem unírico que você mencionou, poderia ser dado para os idiomas regulares limitados e comutativos. Uma linguagem é comutativa , se for encerrada sob permutação de letras. Por exemplo, $ {AB, BA \} $ é comutativo, enquanto $ \ {AB} $ não é. Uma linguagem $ l \ subseteq \ sigma ^ * $ é delimitado , se $ l \ subseteq w_1 ^ * \ cdots w_n ^ * $ Para palavras $ w_i \ in \ sigma ^ * $ . No que se segue, deixe-nos denotar por $ \ diamond $ o shuffle de dois idiomas, e, para $ l \ subseteq \ sigma ^ * $ , por $ L ^ {\ diamond, *}=bigcock_ {n \ GE 0} \ underbrace {l \ diamond \ ldots \ diamond l} _ {\ mbox {$ n $ times}} $ o shuffle iterado . Além disso, por $ \ operatorName {perm}: 2 ^ {\ sigma ^ *} \ para 2 ^ {\ sigma *} $ denotam o fechamento permutacional / em>, ou fechamento comutativo , ou seja, adicionar todas as palavras que são permutações. Por exemplo, $ \ operatorName {perm} (\ {AB \})= {AB, BA \} $ .

Observe que $ l \ subseteq w ^ * $ é regular IFF $ l= w ^ n (w ^ p ) ^ * $ para alguma $ n, p \ G 0 $ . Isto está implícito observando que $ \ {n: w ^ n \ in l} $ é finalmente periódica (pode ser visto como um idioma unário regular). / p >.

por um resultado de Ginsburg / spanier temos

.

Uma linguagem $ l \ subseteq w_1 ^ * \ cdots w_r ^ * $ é regular IFF É uma união finita de idiomas da forma $ l_1 \ cdoz l_r $ , onde cada $ l_i \ subseteq w_i ^ * $ é regular.

Além disso, se $ \ sigma= {a_1, \ ldots, a_k \} $ e $ l \ subseteq \ Sigma ^ * $ é comutativo e regular, é possível para mostrar que $$ L=bigcup_ {i= 1} ^ n \ operatorName {perm} (u_i) \ diamond \ operatorName {perm} (n_i) ^ {\ diamond, *} $$ Para conjuntos finitos $ n_i \ subseteq a_1 ^ * \ copo \ ldots \ cope a_k ^ * $ com $ | n_i \ bon A_J ^ * | \ le 1 $ .

Além disso, como indicado aqui e < um href="https://arxiv.org/abs/2005.04042" rel="nofollow noreferro"> aqui , uma linguagem regular $ l $ mais $ \ sigma= {a_1, \ ldots, a_k \} $ é comutativo IFF $$ L=bigcup_ {i= 1} ^ n u_ {i, 1} \

diamante \ ldots \ diamond u_ {i, k} $$ Para idiomas regulares regulares $ u_ {I, J} \ subseteq A_J ^ * $ com $ i \ in \ \ \ {1, \ lDOTS, n \} $ e $ j \ in \ {1, \ ldots, k \} $ .

Todos esses resultados estão intimamente relacionados. Observe que para idiomas unários, todos eles reduzem para o formulário que você declarou.

uma condição necessária para idiomas do seu formulário

A condição que vou declarar envolve topologia e palavras infinitas. Ele produz, por exemplo, que $ b ^ * a $ e $ (B ^ * a) ^ * $ não pôde ser escrito em seu formulário. Este último tem estrelas duas estrelas, observe que a altura da estrela pode ser caracterizada por classificação de ciclo , ver Teorema de Eggan . No entanto, quero dar um argumento independente e diferente, não baseado na altura da estrela. Deixe $ \ sigma ^ {\ Ômega} $ Seja o conjunto de palavras infinitas sobre $ \ sigma $ . Definir um operador $ W: 2 ^ ^ {\ sigma ^ *} \ a 2 ^ {\ sigma ^ {\ ÔMGA}} $ por, para $ l \ subseteq \ sigma ^ * $ , $$ W (l)={\ xi \ in \ sigma ^ {\ Ômega} \ mid \ mbox {$ \ xi $ tem infinitamente muitos prefixos em $ l $}}. $$ Então \ begin {alinhar *} W (B ^ * a) &=FORTSET \\ W ((b ^ * a) ^ *) e={\ xi \ in \ sigma ^ {\ Ômega} \ mid \ mbox {$ \ xi $ tem infinitamente muitos $ a $ s. }}. \ end {alinhar *} Observe aquilo $$ W (u \ cope v)= w (u) \ cope v (v), $$ como, se $ \ xi \ em w (u \ cope v) $ , então, pelo princípio do pigenolo, pelo menos um dos recipientes de matemática $ U $ ou $ v $ , ou ambos, deve conter infinitamente muitos prefixos de $ \ xi $ . Além disso, na sua forma, poderíamos assumir todos os conjuntos $ a_i $ são singletons, pois a concatenação distribui sobre a União.

Deixe-nos inspecionar idiomas do formulário $ l= u (u_1 + \ ldots + u_n) ^ * $ , que são as partes do seu formulário. Definir $ \ gamma= {B_1, \ LDOTS, B_N \} $ , um alfabeto auxiliar e considere o homomorfismo $ h: \ gamma \ to \ sigma ^ * $ dado por $ h (b_i)= u_i $ , ou seja, substituindo cada letra pela palavra correspondente. Este homomorfismo também pode ser aplicado a palavras infinitas em $ \ gamma ^ {\ ômega} $ . Nós temos $$ W (u (u_1 + \ ldots + u_n) ^ *)={uh (\ xi) \ mid \ xi \ in \ gamma ^ {\ ÔMGA}}. $$ Em particular, se todo o conjunto $ b_i $ são singletons, $ w (l) $ é finito, e $ W (L) \ ne \ FORTSET $ para cada linguagem infinita do seu formulário.

Na última observação, $ b ^ * A $ não pôde ser escrito em seu formulário. Então, este é um exemplo muito simples, mesmo da estância de altura. Mas vamos mostrar que $ l= (b ^ * a) ^ * $ também não poderia ser escrito dessa maneira. Assumir que poderia ser, então o conjunto de palavras infinitas, que todos têm um número infinito de $ a $ nele, poderia ser escrito em termos de um homomorfismo $ h: \ gamma ^ * \ to \ sigma ^ * $ como descrito acima, isto é, $$ \ {\ xi \ in \ sigma ^ {\ Ômega} \ mid \ mbox {$ \ xi $ tem infinitamente muitos $ a $ s. } \}= u h (\ gamma ^ {\ Ômega}) $$ Para alguns $ u \ in \ sigma ^ * $ . Deixe $ m= {| h (x) | : x \ in \ gamma} + | u | $ . Então $ ub ^ maaaaa \ cdoz $ está nesta linguagem, e isso implica $ h (x) \ em b ^ + $ para alguma $ x \ in \ gamma $ . Mas então $ ubbbbbb \ cdots \ in uh (\ gamma ^ {\ Ômega}) $ , que é uma contradição, pois contém apenas um número finito de $ a $ 's. Portanto, $ (B ^ * a) ^ * $ não pôde ser escrito dessa maneira. $ \ quadrado $