Regolarità di una lingua costruita da una lingua normale conosciuta

Question

Sto lavorando attraverso tali domande di manuale sulle lingue regolari e si sono imbattuti in un problema che ammonta a mostrare la lingua seguente è regolare, dato che $ A $ è Una lingua normale: $$ \ {x | \ esiste n \ ge 0 \; \ esiste y \ in a \; y= x ^ n \} $$

Ho tentato di dimostrare che questo è regolare da una contraddizione che utilizza MyHill-Nerode, assumendo che ha un indice infinito e che mostra questo significa che $ A $ deve avere un indice infinito. Tuttavia, non riesco a far funzionare questa prova, perché assumere rappresentanti di ogni classe mi consente di mostrare un numero infinito di coppie di elementi in $ a $ che non sono in La stessa classe, ma questi elementi non corrispondono in modo univoco ai miei rappresentanti, quindi non posso dimostrare che un elemento non è nella stessa classe di infinitamente molti altri.

Tuttavia, il libro sembra indicare che la soluzione dovrebbe essere la costruzione. Posso anche vedere facilmente la costruzione per un NFA se $ N $ è stato risolto, ma questo non sembra offrire alcun aiuto, poiché ciò rende gli stati dipendono da < Span Class="Math-Container"> $ N $ (utilizzando Tuples of States e simultaneamente spostanti stati una volta).

Se qualcuno potesse suggerire come andare a costruire gli automi richiesti, sarebbe molto utile.

Answer 1

Come citini, se $ N $ è stato risolto, allora questo non è troppo difficile da dimostrare. Quindi, l'idea sarebbe quella di dimostrare che in effetti, $ N $ può essere limitato a-priori, a seconda di $ A $ , e non su $ x $ .

A tal fine, considera qualche parola $ x \ in \ sigma ^ * $ , e supponiamo $ x ^ m \ in un $ per qualche $ m $ . Let $ k $ Sii il numero di stati in alcuni DFA $ d $ per $ A $ (ad esempio, DFA minimal). Supponiamo $ m> k $ , quindi esistono $ 0 \ le i tale La corsa di $ d $ su $ x ^ I $ raggiunge lo stesso stato del $ X ^ J $ . Ma ciò implica che $ x ^ {m- {ji}} $ è anche accettato da $ d $ .

Quindi, è sufficiente considerare $ n \ le k $ . Quindi puoi riscrivere la tua lingua come $$ \ {x | \ esiste n \ le k, \ x ^ n \ in a \} $$ E questo è regolare.