Il linguaggio regolare come unione finita di insiemi periodici

Question

È vero che ogni linguaggio regolare può essere espresso come un'unione finita di insiemi periodici?In altre parole, se $L$ è regolare, allora esistono insiemi finiti $A_1,\punti,A_n,B_1,\punti,B_n$ tale che

$$L = A_1 \cdot B_1^* \cup \cdots \cup A_n \cdot B_n^*.$$

So che questo è vero per le lingue regolari su un alfabeto unario, ma non sono sicuro degli alfabeti generali.

Answer 1

Ogni lingua di questo modulo può essere rappresentata come espressione regolare senza nidificare la stella di Kleene.Cioè, il suo Height stella è $ 1 $ .The Hierarchia di altezza stella è rigorosa, e in particolare, è noto che la lingua $ (a ^ * b ^ * c) ^ * $ non può essere rappresentato in tale forma.Un esempio su un alfabeto binario sarebbe $ (AA (AA) ^ * bb (AB) ^ *) ^ * $ .

Answer 2

La risposta di @YuvalFilmus va benissimo e ti indirizza alla nozione di importazione di altezza della stella.Ma lasciatemi aggiungere qualcosa in più.Mostreremo che le lingue della tua forma forniscono un sottoinsieme appropriato delle lingue di altezza stella uno.Ma prima, alcune riflessioni su cosa potrebbe avvicinarsi alla tua forma.

Lingue regolari generali

Innanzitutto, probabilmente la forma più vicina alla tua per Regular $L \subseteq \Sigma^*$, accettato da un automa deterministico completo $A = (\Sigma, Q, \delta, q_0, F)$.Per $q \in Q$ E $E \subseteq Q$, scrivere $L_{q, E}(A)$ per la lingua accettata da $(\Sigma, Q, \delta, q, E)$, ovvero, modificando lo stato iniziale in $q$e l'insieme degli stati finali a $E$.Quindi possiamo scrivere$$ l = bigcup_ {q in f} l_ {q_0, q} (a) l_ {q, {q }} (a)^* $$Questo risultato sembra essere folcloristico e si segue facilmente.Potrebbe essere un po' rafforzato, sostituendolo$L_{q_0, \{q\}}(A)$ dalla lingua$$ {u in l_ {q_0, {q }} mid delta (q_0, v) ne q mbox {per ogni prefisso corretto $ v $ di $ u $} } $$nell'equazione di cui sopra.Ha la proprietà che nessuna parola in esso contenuta è prefisso proprio di un'altra parola.Una variante di questa scomposizione e ulteriori perfezionamenti compaiono nel libro Automi, Linguaggi e Macchine, volume A di S.Eilenberg, sotto il nome decomposizione ripetuta.

Linguaggi regolari commutativi e limitati

Altre forme, più vicine alla tua, ed essendo proprie generalizzazioni del caso linguistico unario da te citato, potrebbero essere date per i linguaggi regolari limitati e commutativi.Una lingua è commutativo, se è chiuso con permutazione di lettere.Per esempio, $\{ab,ba\}$ è commutativo, mentre $\{ab\}$ non è.Una lingua $L \subseteq \Sigma^*$ È delimitato, Se $L \subseteq w_1^* \cdots w_n^*$per le parole $w_i \in \Sigma^*$.Nel seguito indicheremo con $\diamante$ IL mescolata di due lingue, e, per $L \subseteq \Sigma^*$, di $L^{\diamond,*} = \bigcup_{n \ge 0} \underbrace{L \diamond \ldots \diamond L}_{\mbox{$n$ volte}}$ IL shuffle iterato.Inoltre, di $ omeoperatore{perm}:2^{\Sigma^*} \a 2^{\Sigma*}$ denotare il chiusura permutativa, O chiusura commutativa, cioè.aggiungendo tutte le parole che sono permutazioni.Per esempio, $ omeoperatore{perm}(\{ab\}) = \{ab,ba\}$.

Notare che $L \subseteq w^*$ è regolare se e solo se $L = w^n(w^p)^*$ per alcuni $n, p \ge 0$.Ciò è implicito osservandolo $\{n:w^n \in L \}$ è in definitiva periodico (potrebbe essere visto come un linguaggio unario regolare).

Per risultato di Ginsburg/Spanier abbiamo

Una lingua $L \subseteq w_1^* \cdots w_r^*$ è regolare se e solo se è un'unione finita di linguaggi della forma $L_1 \cdots L_r$, dove ciascuno $L_i \subseteq w_i^*$ è regolare.

Inoltre, se $\Sigma = \{a_1, \ldots, a_k\}$ E $L \subseteq \Sigma^*$ è commutativo e regolare, lo è possibile per dimostrarlo$$ l = bigcup_ {i = 1}^n operatorname {perm} (u_i) diamond operatorname {perm} (n_i)^{ diamond,*} $$per insiemi finiti $N_i \subseteq a_1^* \cup \ldots \cup a_k^*$ con $ | N_i cap a_j^*| le 1 $.

Inoltre, come detto Qui E Qui, una lingua regolare $L$ Sopra $\Sigma = \{a_1, \ldots, a_k\}$ è commutativo se e solo se$$ l = bigcup_ {i = 1}^n u_ {i, 1} diamond ldots diamond u_ {i, k} $$per i linguaggi regolari unari $U_{i,j} \subseteq a_j^*$con $i \in \{1,\ldots, n\}$ E $j \in \{1,\ldots,k\}$.

Tutti questi risultati sono strettamente correlati.Nota che per le lingue unarie, si riducono tutte alla forma che hai dichiarato.

Una condizione necessaria per le lingue del tuo modulo

La condizione che esporrò implica topologia e parole infinite.Ne risulta, ad esempio, questo $b^*a$ E $(b^*a)^*$ non può essere scritto nel tuo modulo.Quest'ultimo ha l'altezza della stella due, nota che l'altezza della stella potrebbe essere caratterizzata da rango del ciclo, Vedere Il teorema di Eggan.Tuttavia, qui voglio fornire un argomento autonomo e diverso, non basato sull’altezza delle stelle.Permettere $\Sigma^{\omega}$ essere l'insieme di infinite parole finite $\Sigma$.Definire un operatore $W:2^{\Sigma^*} \a 2^{\Sigma^{\omega}}$ da, per $L \subseteq \Sigma^*$, $$ w (l) = { xi in Sigma^{ omega} mid mbox {$ xi $ ha infinitamente molti prefissi in $ l $} }.$$Poiinizio {align*} w (b^*a) & = vuoto w ((b^*a)^*) & = { xi in Sigma^{ omega} mid mbox { $ xi $ ha infiniti $ A $ 's.} \}.\end{allineare*}Osservalo$$ W (U Cup V) = W (U) Cup V (V), $$come se $\xi \in W(U\cup V)$, quindi, secondo il principio della casella, almeno uno dei $U$ O $V$, o entrambi, devono contenere infiniti prefissi di $\xi$.Inoltre, nella tua forma potremmo assumere tutti i set $A_i$ sono singleton, poiché la concatenazione si distribuisce sull'unione.

Esaminiamo le lingue della forma $L = u(u_1 + \ldots + u_n)^*$, che sono le parti del tuo modulo.Impostato $\Gamma = \{ b_1, \ldots, b_n \}$, un alfabeto ausiliario, e consideriamo l'omomorfismo $h:\Gamma \a \Sigma^*$ dato da $h(b_i) = u_i$, cioè sostituendo ogni lettera con la parola corrispondente.Questo omomorfismo potrebbe essere applicato anche a infinite parole in $\Gamma^{\omega}$.Abbiamo$$ w (u (u_1 + ldots + u_n)^*) = {uh ( xi) mid xi in gamma^{ omega} }.$$In particolare, se tutto il set $B_i$ sono single, $W(L)$ è finito e $W(L) e \emptyset$ per ogni infinito linguaggio della tua forma.

Dall'ultima osservazione, $b^*a$ non può essere scritto nel tuo modulo.Quindi, questo è un esempio molto semplice, anche dell'altezza di una stella.Ma mostriamolo $L = (b^*a)^*$ non potrebbe nemmeno essere scritto in questo modo.Supponiamo che possa essere, quindi, l'insieme di infinite parole, che hanno tutte un numero infinito di $a$è in esso, potrebbe essere scritto in termini di omomorfismo$h:\Gamma^* \a \Sigma^*$ come descritto sopra, cioè$$ { xi in Sigma^{ omega} mid mbox {$ xi $ ha infinitamente molti $ a $ 's.} } = uh ( gamma^{ omega}) $$per alcuni $u \in \Sigma^*$.Permettere $ m = {| h (x) | :x \in \Gamma \} + |u|$.Poi $ub^maaaaa\cdots$ è in questa lingua e questo implica $h(x) \in b^+$ per alcuni $x \in \Gamma$.Ma allora $ubbbbbbb\cdots \in uh(\Gamma^{\omega})$, che è una contraddizione, poiché contiene solo un numero finito di $a$'S.Quindi, $(b^*a)^*$ non si poteva scrivere così. $\quadrato$