|
\subsection{Applicazioni} |
|
|
|
Qui passiamo alle applicazioni del \emph{Pumping Lemma}. In particolare può essere utilizzato per provare che un linguaggio \(\mathcal{L}\) non è libero. |
|
|
|
In generale, da un'implicazione logica del tipo \(A \implies B\), è possibile ottenere la negazione \(\neg A \implies \neg B\). Nel nostro caso, da \(\mathcal{L}\) libero \(\implies\) Tesi del \emph{Pumping Lemma}, abbiamo \(Not\) tesi del \emph{Pumping Lemma} \(\implies\) \(\mathcal{L}\) \(Not\) libero. |
|
La negazione della tesi del \emph{Pumping Lemma} è la seguente: |
|
|
|
\begin{itemize} |
|
\item \(\forall p \in \mathbb{N}^+\) tale che |
|
\item \(\exists z \in \mathcal{L} : |z| > p\), allora |
|
\item \(\forall u, v, w, x, y\) tale che: |
|
|
|
\begin{itemize} |
|
\item \(z = uvwxy \textrm{ } \land\) |
|
\item \(|vwx| \leq p \textrm{ } \land\) |
|
\item \(|vx| > 0 \textrm{ }\land\) |
|
\item \(\exists i \in \mathbb{N}.uv^iwx^iy \not\in \mathcal{L}\) |
|
\end{itemize} |
|
|
|
\end{itemize} |
|
|
|
Lasciamo al lettore immaginare gli altri modi in cui è possibile riscrivere la negazione della tesi del \emph{Pumping Lemma} applicando le basi di algebra booleana. |
|
Passiamo dunque ad esempi pratici. |
|
ES 1 |
|
Sia \(\mathcal{G}\) così definito |
|
\(S \rightarrow aSb \ abc\) |
|
\(cB \rightarrow Bc\) |
|
\(bB \rightarrow bb\) |
|
ci chiediamo dunque se \(\mathcal{G}\) è \emph{context dependent} o \emph{free}. Ovviamente è \emph{context dependent}. |
|
Ci chiediamo quale sia il linguaggio generato da \(\mathcal{G}\), \(\mathcal{L(G)}\) ed è \({a^n b^n b^n | n>0}\) |
|
Ci chiediamo infine se il linguaggio \(\mathcal{L(G)}\) sia o meno un linguaggio libero. Per farlo possiamo semplicemente utilizzare la negazione del \emph{Pumping Lemma} per dimostrare che \(\mathcal{L(G)}\) non è libero. |
|
|
|
Sia \( p \in N^+\) un numero intero arbitrario |
|
Possiamo prendere un numero \(z=a^pb^pc^p \in \mathcal{L}\) che soddisfa la condizione \(|z|\leq p\) |
|
Quindi possiamo prendere qualsiasi decomposizione di \(z = uvwxy, |vwx|\leq p |vx|>0\). |
|
Sappiamo che la parola \(z\) è composta in questo modo. \(\underbrace{aa...a}_\text{\emph{p}}\underbrace{bb...b}_\text{\emph{p}}\underbrace{cc...c}_\text{\emph{p}}\). |
|
La sottostringa \(vwx\) deve essere sicuramente in una di queste possibili posizioni |
|
\(a\underbrace{a...a}_\text{\emph{vwx}} |
|
a\underbrace{a...abb...b}_\text{\emph{vwx}} |
|
b\underbrace{b...b}_\text{\emph{vwx}} |
|
b\underbrace{b...bc...c}_\text{\emph{vwx}} |
|
c\underbrace{c...c}_\text{\emph{vwx}}c\) |
|
da cui abbiamo che qualsiasi sia la posizione di \(vwx\) all'interno della parola \(z\) è possibile costruire una parola con un numero non bilanciato di \(a,b,c\) semplicemente ponendo \(v^i,x^i,i=0\) |
|
Dunque troviamo una parola che non appartiene al linguaggio. Se il linguaggio fosse libero, tutte le parole costruite in questa maniera dovrebbero appartenere al linguaggio. Dunque il linguaggio non è |
|
\emph{free} |
|
Passiamo dunque ad un altro esempio riprendendo l'esercizio lasciato per casa a suo tempo |
|
ES 2 |
|
|
|
\(S \rightarrow CD \) |
|
\(C \rightarrow aCA | bCB \) |
|
\(AD \rightarrow aD \) |
|
\(BD \rightarrow bD \) |
|
\(Aa \rightarrow aA \) |
|
\(Ab \rightarrow bA \) |
|
\(Ba \rightarrow aB \) |
|
\(Bb \rightarrow bB \) |
|
\(C \rightarrow \epsilon \) |
|
\(D \rightarrow \epsilon \) |
|
|
|
Si verifica facilmente che il linguaggio generato da tale grammatica è \(\mathcal{L(G)} =\{ww | w\in\{a,b\}^*\}\) |
|
Ci chiediamo allore se tale linguaggio sia libero o meno |
|
Un lettore naive potrebbe essere portato ad applicare la proprietà di chiusura dei linguaggi liberi rispetto alla operazione di concatenazione per dimostrare che suddetto linguaggio sia libero, in quanto sappiamo che \(\mathcal{L'(G)} =\{w | w\in\{a,b\}^*\}\) è un linguaggio libero. Tuttavia l'operazione di concatenazione non rispetta la proprietà di palindromia di \(\mathcal{L}\). |
|
È infatti semplice provare che \(\mathcal{L}\) non è libero |
|
DIM |
|
Sia \(\mathcal{L}\) libero |
|
sia \(z=a^pb^pa^pb^p, z\in \mathcal{L}, z=uvwxy, |vwx|\leq p \) |
|
Per esempio supponiamo sia \(|vwx|=b^p\), allora ic è facile prendere \(uv^0wx^0y\) e verificare che questo non può avere la forma \(a^pb^pa^pb^p\) |
|
Dunque abbiamo trovato un elemento che contraddice il \emph{Pumping Lemma} e dunque l'ipotesi iniziale non è valida, ovvero \(\mathcal{L}\) non è \emph{free} |