regulaarse avaldisega. T: Olgu M = (Q,Σ,δ,Q1,F) lõplik automaat olekute hulgaga Q = {q0,q1,…,qn}. Defineerime Rk ij kui sõnede hulga, mis viivad automaadi olekust qi olekusse qj vahepeal olekuid qk,...,qn läbimata. Hulk R0 ij = {a∈Σ | qj ∈ δ(qi ,a)} on lõplik ja seega esitatav regulaarse avaldisega. Oletame, et Rk ij on esitatav regulaarse avaldisega, siis on seda ka hulk Rk+1 ij = Rk ij ∪ Rk ik (Rk kk)* Rk kj Induktsioonireegli kohaselt on siis regulaarse avaldisega esitatav ka hulk Rij = Rn+1 ij, samuti ka L(M) = U {Rij | qi on algolek, qj on lõppolek}. 5 Keele regulaarsuse tarvilik tingimus (pumpamise lemma). Kui L on regulaarne keel, siis leidub konstant p, nii et iga sõne z ∈ L, |z| > p (sõnes on rohkem kui p tähte) on jaotatav kolmeks alamsõneks z = uvw, nii et |v| > 0 (keskmine osa pole tühi) ja uvjw ∈ L iga j = 0,1,2,... korral.
konstrueerida definitsiooni abil lõpmatu hulk objekte: {0, 0+1, 0+1+1, 0+1+1+1, ...} Aritmeetika jaoks tuleb meil defineerida täisarvude hulga järgmine fundamentaalne omadus (matemaatilise induktsiooni reegel): ``kui arvul 0 on omadus P ja kui väitest, et arvul x on omadus P, järeldub alati, et ka arvul x+1 on omadus P, siis on kõigil arvudel omadus P''. Induktsioonireeglit ei saa tuletada loogika baasväidetest: me võtame induktsioonireegli enda uueks täisarvude kohta kehtivaks baasväiteks. Tähendab, me usume, et induktsioonireegel on matemaatiliselt õige. Miks me sellise reegli tõesust uskuma peaks? Sellepärast, et kui tema üle mõnda aega mõelda, siis saame aru, et see reegel on paratamatult õige, samamoodi, nagu me saame aru, et väide ``kui A, siis A'' on paratamatult õige. Erinevalt viimasest on induktsioonireegel aga keerulisem ning tema paratamatu õigsus ei tundugi enam elementaarne. Mis juhtub,
annaabi.ee 
