Perché $((aa)^*bb(aa)^*bb(aa)^*)^*$ di altezza stella 1

Question

Un'espressione regolare generalizzata è come un'espressione regolare ma con un'ulteriore operazione consentita:complementazione.Il (generalizzato) altezza stella di un'espressione regolare generalizzata è il numero massimo di stelle di Kleene annidate.L'altezza stella di una lingua è l'altezza stella minima di un'espressione regolare che la descrive.Non è noto se esista una lingua con altezza stella 2.

Quindi immagino il linguaggio $((aa)^*bb(aa)^*bb(aa)^*)^*(aa)^*$ di parole costituite da concatenazioni di $aa$ E $bb$, con un numero pari di $bb$, ha un'altezza stellare generalizzata $1$.Ma non ho potuto provarlo.Nel giornale Alcuni risultati sul problema generalizzato dell'altezza delle stelle (Pin, Straubing, Thérien), il lemma 6.1 (il lemma di trasferimento) non può essere applicato perché entrambi $(bb)^*$ E $(aa)^*$ sono di altezza stella 1.

Ho visto altrove alcune lingue che si ipotizza fossero di altezza stella 2 ed erano più complesse di quella che fornisco, quindi molto probabilmente è di altezza stella 1.È così?

Answer 1

(Questo è un tentativo di risposta, spero che i dettagli siano corretti.)

La tua lingua è composta da tutte le stringhe in $(aa+bb)^*$ con un numero pari di $bb$.

Possiamo usare la complementazione, quindi iniziamo guardando il complemento della lingua.Penso che possiamo dividere il complemento in due parti (sovrapposte).

• stringhe non del modulo $(aa+bb)^*$, quella lingua ha l'altezza della stella.
• stringhe del modulo $w_0\cdot bb\cdot w_1\cdot bb\cdot w_2 \dots bb\cdot w_n$, dove (1) il numero di $bb$ è strano e (2) il $w_i$ non ne contengono alcuno $bb$ (ma su questo dovrò essere più preciso)

Ora proveremo a trovare un'espressione per la lingua $W$ del $w_i$ senza usare la stella.Ciò significa che possiamo usare la stella per contare il numero dispari di $bb$, come in $(W\cdot bb\cdot W\cdot bb)^*\cdot W\cdot bb\cdot W$.

Questa è la parte difficile.Stringhe da $W$ sono o

• la stringa vuota $\varepsilon$
• solo un singolo $a$
• del modulo $axa$, Dove $a$ non contiene $bb$.Non "contenente". $bb$" è il complemento di $(a+b)^*bb(a+b)^*$, e come sai $(a+b)^*$ è di nuovo senza stelle.

Le stringhe che ora abbiamo specificato possono avere tratti più lunghi $b$'s, ma ogni volta che ciò accade il $b$Sono venuti in coppia.