lemma di pompaggio (lingua normale)

Question

Ho bisogno di aiuto con un problema di lemma di pompaggio.

L = { {a,b,c}* | #a(L) < #b(L) < #c(L) } 

Questo è quello che ho ottenuto finora:

y = uvw is the string from the pumping lemma. 

io sia y = abbc^n, n è la lunghezza dal lemma di pompaggio. y è in L perché il numero di a: s è inferiore al numero di b: s, e il numero di b: s è inferiore al numero di c: s.

Ho lasciato u = a, v = bb e w = c^n. | Uv | < y, come indicato nel lemma di pompaggio. Se io "pompa" (bb)^2 poi ho

y = abbbbc^n which violates the rule #b(L) < #c(L). 

è questo diritto? Sono sulla "strada giusta"?

Grazie

Answer 1

L'idea principale del pompaggio lemma è per dirvi che quando si dispone di un linguaggio regolare L con un numero infinito di termini v'è un modello nella lingua che si ripete sempre.

L'espressione regolare associata a tale lingua conterrà KLEENE-STAR (modello).

L'automa associato a tale espressione regolare (e lingua) conterrà un ciclo.

La dimostrazione viene eseguita utilizzando il principio del piccione.

Questo è molto suggestivo.

Si noti che tutti i termini devono iniziare in q0 e terminare in qn in questo caso. Quindi, gli automi che definiscono la lingua sono finiti (max N stati), quindi c'è un numero limitato di stati, ma le parole (cioè i termini) possono avere> N lettere. Il principio del piccione ci dice che deve esserci uno stato che viene raggiunto 2 volte, quindi in quello stato sarà presente un ciclo.

Nella notazione, si può fare la corrispondenza con l'immagine in modo da:

• tua u è x dall'immagine

• v è y nell'immagine

• w è z da image

Per arrivare da q0 a qn, è possibile utilizzare qualsiasi delle stringhe dal set: { uw , uvw, uvvw, uvvvw, ... }.

In questo caso particolare il modello P è y, l'insieme X è {xz xyz xyyz xyyyz ...} e S è length(x)+length(y).