[Teoria] pumping lemma linguaggi regolari
Ciao a tutti!
Sono uno studente lavoratore e in quanto tale non riesco a frequentare i corsi
Quest'anno abbiamo un corso di "linguaggi formali e automi" e ho degli esercizi che mi stanno causando qualche problemino. Uno di questi esercizi riguarda il pumping lemma per riconoscere se un linguaggio non è regolare.
L'esercizio riporta:
\(\displaystyle L = \{ a^{i^2} | i \geq 1 \} \)
La definizione che la prof riporta nelle dispense è:
Se L è un linguaggio regolare allora\(\displaystyle \exists k > 0 \) tale che \(\displaystyle \forall z \in L \) con
\(\displaystyle |x| \geq k \),\(\displaystyle \exists u,v,w \) tali che:
\(\displaystyle x = uvw \)
\(\displaystyle |uv| \leq k \)
\(\displaystyle |v| \geq 1 \)
\(\displaystyle uv^{i}w \in L \forall i \in N \)
Io ho pensato di procedere così:
\(\displaystyle x = a^{k-l}*a^{l} \)
dove:
\(\displaystyle u = a^{k-l} \)
\(\displaystyle v = a^{l} \)
\(\displaystyle w = \epsilon \) (stringa vuota)
quindi la condizione \(\displaystyle uv^{i}w \in L \) è violata in quanto, per esempio, se \(\displaystyle i = 2 \) avremo \(\displaystyle x = a^{k-l} * a^{li} = a^{k-l} * a^{2l} = a^{k+l}\) e quindi non appartiene al linguaggio\(\displaystyle L \) perchè dovrebbe essere nella forma \(\displaystyle a^{i^2} \) e invece risulta \(\displaystyle a^{i^2+l} \)
È giusto come ragionamento oppure non c'ho azzeccato niente?
Sono uno studente lavoratore e in quanto tale non riesco a frequentare i corsi
Quest'anno abbiamo un corso di "linguaggi formali e automi" e ho degli esercizi che mi stanno causando qualche problemino. Uno di questi esercizi riguarda il pumping lemma per riconoscere se un linguaggio non è regolare.
L'esercizio riporta:
\(\displaystyle L = \{ a^{i^2} | i \geq 1 \} \)
La definizione che la prof riporta nelle dispense è:
Se L è un linguaggio regolare allora\(\displaystyle \exists k > 0 \) tale che \(\displaystyle \forall z \in L \) con
\(\displaystyle |x| \geq k \),\(\displaystyle \exists u,v,w \) tali che:
\(\displaystyle x = uvw \)
\(\displaystyle |uv| \leq k \)
\(\displaystyle |v| \geq 1 \)
\(\displaystyle uv^{i}w \in L \forall i \in N \)
Io ho pensato di procedere così:
\(\displaystyle x = a^{k-l}*a^{l} \)
dove:
\(\displaystyle u = a^{k-l} \)
\(\displaystyle v = a^{l} \)
\(\displaystyle w = \epsilon \) (stringa vuota)
quindi la condizione \(\displaystyle uv^{i}w \in L \) è violata in quanto, per esempio, se \(\displaystyle i = 2 \) avremo \(\displaystyle x = a^{k-l} * a^{li} = a^{k-l} * a^{2l} = a^{k+l}\) e quindi non appartiene al linguaggio\(\displaystyle L \) perchè dovrebbe essere nella forma \(\displaystyle a^{i^2} \) e invece risulta \(\displaystyle a^{i^2+l} \)
È giusto come ragionamento oppure non c'ho azzeccato niente?
Risposte
Ciao pol20 
Nell'esercizio da te descritto puoi verificare pressoché immediatamente come il linguaggio fornito non sia regolare. Intuitivamente infatti si ha che risulta impossibile costruire un automa a stati finiti che riconosce il linguaggio dato (ti servirebbe idealmente un numero infinito di stati). Pertanto sappiamo che il linguaggio dato non è regolare (ovvio, il discorso appena fatto esula da quanto richiesto dall'esercizio ma l'ho scritto solo per darti un'idea).
Ora vogliamo però cercare di provarlo più formalmente utilizzando il pumping lemma, operazione sicuramente molto meno onerosa rispetto al provare mediante lo stesso che è linguaggio è regolare.
Immagino innanzitutto che nella definizione della prof che hai scritto tu intendessi $\forall x \in L$ e non $\forall z \in L$.
Possiamo quindi cercare di trovare un semplice controesempio per cui le condizioni richieste dal pumping lemma non valgono. Se prendi ad esempio $x = a$ hai che:
\[
|x| = 1, k = 1, u = \epsilon, w = \epsilon, v = a, uv = a, |uv| = 1 \le k, |v| = 1 \ge 1
\]
Ora fatte salve queste premesse risulta pertanto che con questa stringa non ho nessun $k$ possibile affinché l'ultima condizione del pumping lemma sia soddisfatta ($k = 1$ infatti se ci pensi era l'unico "papabile" che intuitivamente sarebbe stato "candidato a questo scopo", vedi infatti condizione $|uv| \le k$) in quanto ottengo che ad esempio:
\[
\text{se } i = 2 \text{ allora } aa \notin L
\]
Questo ovviamente è un solo $i$ con cui ho scelto di "pompare" la mia stringa ma ve ne sono teoricamente infiniti. Per i nostri scopi però lo stesso è sufficiente.
Spero di esserti stato d'aiuto, in caso chiedi pure altre delucidazioni.
Nell'esercizio da te descritto puoi verificare pressoché immediatamente come il linguaggio fornito non sia regolare. Intuitivamente infatti si ha che risulta impossibile costruire un automa a stati finiti che riconosce il linguaggio dato (ti servirebbe idealmente un numero infinito di stati). Pertanto sappiamo che il linguaggio dato non è regolare (ovvio, il discorso appena fatto esula da quanto richiesto dall'esercizio ma l'ho scritto solo per darti un'idea).
Ora vogliamo però cercare di provarlo più formalmente utilizzando il pumping lemma, operazione sicuramente molto meno onerosa rispetto al provare mediante lo stesso che è linguaggio è regolare.
Immagino innanzitutto che nella definizione della prof che hai scritto tu intendessi $\forall x \in L$ e non $\forall z \in L$.
Possiamo quindi cercare di trovare un semplice controesempio per cui le condizioni richieste dal pumping lemma non valgono. Se prendi ad esempio $x = a$ hai che:
\[
|x| = 1, k = 1, u = \epsilon, w = \epsilon, v = a, uv = a, |uv| = 1 \le k, |v| = 1 \ge 1
\]
Ora fatte salve queste premesse risulta pertanto che con questa stringa non ho nessun $k$ possibile affinché l'ultima condizione del pumping lemma sia soddisfatta ($k = 1$ infatti se ci pensi era l'unico "papabile" che intuitivamente sarebbe stato "candidato a questo scopo", vedi infatti condizione $|uv| \le k$) in quanto ottengo che ad esempio:
\[
\text{se } i = 2 \text{ allora } aa \notin L
\]
Questo ovviamente è un solo $i$ con cui ho scelto di "pompare" la mia stringa ma ve ne sono teoricamente infiniti. Per i nostri scopi però lo stesso è sufficiente.
Spero di esserti stato d'aiuto, in caso chiedi pure altre delucidazioni.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo