Mostrare$L = ${w$\in (a,b) ^* $| per ogni u sottostringa di w,$-5\le|u|_a−|u|_b\le5\}$è regolare
Cerco di mostrare che questa lingua è regolare:
$L = ${w$\in \ (a,b) ^ * $| per ogni u sottostringa di w,$-5\le|u|_a−|u|_b\le5\}$
Se creo un NFA ed eseguo su di esso ogni sottostringa di w (salta altre lettere ogni volta) - e solo se sono tutte accettate (segue la condizione), allora accetto w. È possibile in NFA? C'è un altro modo per mostrare la regolarità della lingua?
Risposte
Bella domanda! Questo è un problema molto non banale che coinvolge linguaggi regolari.
Prima di tutto: no, non puoi eseguire un automa su ogni sottostringa di una stringa saltando altre lettere, dovresti eseguire l'automa solo una volta sulla stringa di destinazione.
In questo caso è più semplice ragionare sul complementare della lingua data, cioè su
$$L^C = \{ w \in (a,b) ^ * \mid \text{ there is a substring } u \text{ of } w \text{ such that } |u|_a−|u|_b>5 \text{ or } |u|_a−|u|_b<-5\}$$
La lingua$L^C$è regolare, in quanto riconosciuto dalla seguente NFA:
(ogni nome di stato è la differenza$|u|_a−|u|_b$, la prima lettera della sottostringa$u$è "trovato" in modo non deterministico dall'NFA).
Così come$L^C$è regolare, anche$L=(L^C)^C$è.
Seguendo il suggerimento di Hendrick, ho cercato di determinare l'NFA e di disegnare il suo complemento, e ottengo questo bel DFA che riconosce$L$:
Ogni nome di un nome di stato accettante è un intervallo: quando, eseguendo l'automa, siamo nello stato$[x_1,x_2]$e abbiamo letto la stringa$z$questo significa che per tutti$x\in [x_1,x_2]$c'è un suffisso$u$di$z$tale che$|u|_a−|u|_b=x$. Altrimenti detto, seguendo il suggerimento di Dmitry, l'automa calcola l'insieme residuo di$z$.
In un certo senso, come dice Hendrick, è come se stessimo eseguendo l'automa su ogni sottostringa, ma questo non significa che possiamo usare direttamente un DFA che riconosca stringhe tali che la differenza tra le$a$se il$b$c'è$[-5,5]$(che sarebbe facile da realizzare) ed eseguire questo automa su ogni sottostringa di una data, e in questo modo dimostrare che il linguaggio è regolare.
Infine, scriverei una banale generalizzazione del risultato (penso che si tratti di folklore, ma non sono riuscito a trovare un riferimento).
Permettere$T$essere una lingua normale su un alfabeto$\Sigma$e lascia$L$essere la lingua definita come segue:
$$L= \{ w \in \Sigma^* \mid \text{ for every substring } u \text{ of } w,\ u\in T\}$$
poi anche$L$è regolare.
In effetti, come sopra, considera$L^C$, il complemento di$L$, vale a dire
$$L^C = \{ w \in \Sigma^* \mid \text{ there is a substring } u \text{ of } w \text{ such that } u\not\in T\}$$
Quindi$L^C=\Sigma^*T^C\Sigma^*$, e quindi$L=(\Sigma^*T^C\Sigma^*)^C$è regolare, poiché la famiglia dei linguaggi regolari è chiusa rispetto alla concatenazione e alla complementazione.
Chiaramente il risultato è ancora vero per ogni famiglia di lingue chiusa sotto concatenazione e complementazione, ma questa non è una condizione necessaria. Infatti, la famiglia dei linguaggi finiti non è chiusa rispetto alla complementazione, ma chiaramente se$T$è finito, allora anche$L$è (come è sempre il caso che$L\subseteq T$). D'altra parte, questo non è vero per tutte le classi di lingue. Consideriamo quindi la famiglia NR delle lingue non regolari$T=\{1^p\mid p\text{ is prime}\}\in\ $NR, ma in questo caso abbiamo$L=\varnothing$, che è regolare.