Mostra $ L= $ {W $ \ in (a, b) ^ * $ |per tutte le sottostringa di W, $ -5 \ Le | u | _a- | u | _b \ le5 \} $ è regolare

Question

Provo a dimostrare che questa lingua è regolare:

$ l= $ {w $ \ in \ (a, b) ^ * $ |Per ogni uppstring di W, $ - 5 \ le | u | _a- | u | _b \ le5 \} $

Se costruisco un NFA e correre su di esso ogni sottostringa di W (salta altre lettere ogni volta) - e solo se sono tutti accettati (segue la condizione) quindi accetta w. È possibile in NFA?C'è altro modo per mostrare la regolarità della lingua?

Answer 1

Nice domanda! Questo è un problema molto non tradizionale che coinvolge lingue regolari.

Prima di tutto: No, non è possibile eseguire un automa su ogni sottostringa di una stringa che salta altre lettere, dovresti eseguire l'automazione solo una volta sulla stringa di destinazione.

In questo caso è più semplice per la ragione sul Complementary della lingua data, cioè su

$$ l ^ c={w \ in (a, b) ^ * \ mid \ text {c'è una sottostringa} u \ testo {di} w \ testo {tale che} | u | _a- | u | _b> 5 \ text {o} | u | _a- | u | _b <-5 \} $$

La lingua $ l ^ c $ è regolare, poiché è riconosciuto dalla seguente NFA:

(ogni nome di stato è la differenza $ | u | _a- | u | _B $ , la prima lettera della sottostringa $ U $ è" trovato "nonreterministicamente dall'NFA).

così, come $ l ^ c $ è regolare, anche $ l= (l ^ c) ^ c $ è.

---

.

Seguendo il suggerimento di Hendrick, ho cercato di determinare l'NFA e disegnare il suo complemento, e ottengo questa bella DFA che riconosce $ l :

Ogni nome di un nome di stato accettante è un intervallo: quando, eseguendo l'automa dell'automa, siamo in stato $ [x_1, x_2] $ e abbiamo letto il String $ Z $ significa che per tutte le $ x \ in [x_1, x_2] $ c'è un Suffisso $ U $ di $ z $ in modo tale che $ | u | _a- | u | _b= x $ . Altrimenti detto, seguendo il suggerimento di Dmitry, l'Automaton calcola il set residuo di $ z $ .

In un certo senso, come dice Hendrick, è come stiamo eseguendo l'Automaton su ogni sottostringa, ma questo non significa che possiamo usare direttamente un DFA che riconosca le stringhe in tale che la differenza tra la $ A $ S e la $ B $ s è in $ [- 5,5 ] $ (che sarebbe facile da realizzare) ed eseguire questo automa per ogni sottostringa di un dato, e in questo modo dimostrare che la lingua è regolare.

---

.

Infine, scriverò una generalizzazione banale del risultato (penso che questo sia folclore, ma non riuscivo a trovare un riferimento).

Let $ T $ Sii una lingua normale su un alfabeto $ \ sigma $ e lasciare $ l $ essere la lingua definita come segue:

$$ l={w \ in \ Sigma ^ * \ Mid \ testo {per ogni sottostringa} u \ text {} w, \ u \ in t \} $$

Allora anche $ L $ è regolare.

Infatti, come sopra, considerare $ l ^ c $ , il complemento di $ L $ , vale a dire

$$ l ^ c={w \ in \ sigma ^ * \ mid \ testo {c'è una sottostringa} u \ testo {di} w \ text {tale } u \ non \ in t \} $$

quindi $ l ^ c=sigma ^ * t ^ c \ sigma ^ * $ , e quindi $ l= (\ Sigma ^ * t ^ c \ sigma ^ *) ^ c $ è regolare, poiché la famiglia di lingue regolari è chiusa in concatenazione e complementazione.

Cleary Il risultato è ancora vero per ogni famiglia di lingue chiuse in concatenazione e complementazione, ma questa non è una condizione necessaria. Infatti, la famiglia delle lingue finite non è chiusa sotto la complementazione, ma chiaramente se $ T $ è finita, quindi anche $-contenitore "> L $ è (poiché è sempre il caso che $ l \ subeteq t $ ). D'altra parte, questo non è vero per tutte le classi di lingue. Considerare la famiglia Nr di lingue non regolari, allora $ T={1 ^ P \ MID P \ Text {è Prime}} \ in \ $ nr, Ma in questo caso abbiamo $ l=Varnothing $ , che è regolare.