Decidi se una lingua ha una parola di una determinata dimensione

Question

Supponiamo che $ l $ è un po 'di linguaggio sopra l'alfabeto $ \ sigma $ . Mi è stato chiesto di dimostrare che le seguenti lingue sono decidabili:

$$ l '={w \ in \ Sigma ^ * | \ testo {esiste una parola} w '\ in l \ testo {tale che} | w' | \ leq | w | \} $$

cioè, $ w \ in l $ se $ l $ ha una certa parola con lunghezza più piccola di $ | w | $ .

Il modo in cui stavo pensando di dimostrare che sta osservando che $ l \ cap \ sigma ^ {| w |} $ è finita e $ (L \ Cap \ Sigma) \ Coppa (L \ Cap \ Sigma ^ 2) \ Cup \ Ldots \ Cup (l \ Cap \ Sigma ^ {| w |}) $ è finita Anche, quindi decidabile. Ma la cosa principale con cui sto lottando è come può qualsiasi algoritmo per $ l '$ sapere se una classe $ u \ in l $ ? Questo non è chiaro, quindi non è chiaro come qualsiasi algoritmo per $ l '$ può verificare che in effetti alcune parole è in L $

Answer 1

Ci sono due casi:

.
1. $ l $ è vuoto. In questo caso, $ l '=vuoto $ è banale decidabile.
2. $ l $ non è vuoto. Let $ m $ Sii la lunghezza minima di una parola in $ l $ . Quindi $ l '$ consiste di tutte le parole di lunghezza almeno $ m $ , ed è di nuovo banale decidabile (in tempo costante!).

Come puoi vedere, non hai mai bisogno di un algoritmo per $ l $ .

---

.

Allo stesso modo, la lingua seguente è sempre decidabile:

$$ l ''={w \ in \ sigma ^ * \ Mid \ testo {esiste una parola $ w '\ in l $ tale che $ | w' | \ geq | w | $}}. $$

Ci sono ora tre casi:

.
1. $ l $ è vuoto. In questo caso, $ L '' '=vuoto $ è banale decidabile.
2. $ l $ è infinito. In questo caso, $ l ''=sigma ^ * $ è ancora triviall decidabile.
3. $ l $ è finito. Let $ M $ Sii la lunghezza massima di una parola in $ l $ . Quindi $ l '' $ consiste di tutte le parole di lunghezza al massimo $ m $ , ed è di nuovo banale decidabile (in costante tempo).

---

.

Questi sono esempi di prove non costruttive, che potresti non piacere. Invece di iniziare una discussione qui, ti riferisco a Questa domanda .