Pumping Lemma per grammatiche regolari
Teorema
Sia L una lingua normale. Allora esiste una costante‘c’ tale che per ogni stringa w in L -
|w| ≥ c
Possiamo rompere w in tre corde, w = xyz, tale che -
- | y | > 0
- | xy | ≤ c
- Per ogni k ≥ 0, la stringa xy k z è anche in L.
Applicazioni del Pumping Lemma
Il Pumping Lemma deve essere applicato per mostrare che alcune lingue non sono regolari. Non dovrebbe mai essere usato per mostrare che una lingua è regolare.
Se L è regolare, soddisfa Pumping Lemma.
Se L non soddisfa Pumping Lemma, è irregolare.
Metodo per dimostrare che una lingua L non è regolare
In un primo momento, dobbiamo assumerlo L è regolare.
Quindi, il lemma di pompaggio dovrebbe valere L.
Usa il lemma di pompaggio per ottenere una contraddizione:
Selezionare w tale che |w| ≥ c
Selezionare y tale che |y| ≥ 1
Selezionare x tale che |xy| ≤ c
Assegna la stringa rimanente a z.
Selezionare k in modo tale che la stringa risultante non sia in L.
Hence L is not regular.
Problem
Prova che L = {aibi | i ≥ 0} non è regolare.
Solution -
In un primo momento, lo assumiamo L è regolare e n è il numero di stati.
Sia w = a n b n . Quindi | w | = 2n ≥ n.
Pompando lemma, sia w = xyz, dove | xy | ≤ n.
Sia x = a p , y = a q , ez = a r b n , dove p + q + r = n, p ≠ 0, q ≠ 0, r ≠ 0. Quindi | y | ≠ 0.
Sia k = 2. Allora xy 2 z = a p a 2q a r b n .
Numero di as = (p + 2q + r) = (p + q + r) + q = n + q
Quindi, xy 2 z = a n + q b n . Poiché q ≠ 0, xy 2 z non ha la forma a n b n .
Quindi, xy 2 z non è in L. Quindi L non è regolare.