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.