kaotada korduvad konjunktsioonid) o TDNK leidub igal kehtestataval valemil ja on üheselt määratud täielike elementaarkonjuktsioonide järjekorra täpsusega Lausearvutuse valemi F täielikuks konjuktiivseks normaalkujuks (TKNK) nimetatakse valemiga F samaväärset valemit, mis kujutab endast erinevate täielike elementaardisjunktsioonide konjuktsiooni o (X111 V ... V X n1n) & (X121 V ... V Xn2n) & ...& (X1m1 V ... V X nmn) on väär väärtustustel (¬11, ..., ¬1n), (¬21, ..., ¬2n), ..., (¬m1, ..., ¬mn) ja tõene kõigil ülejäänud väärtustustel.TKNK-le viimine: Koostame valemi põhjal tõeväärtustabeli Vaatame vaid neid ridu, mil valem on väär Koostame disjunktsioonid ridadele vastavatest elementide vastandtõeväärtustest (nt kui X=t, Y=t ja Z=v, siis saame
(a1a2a3a4,q0)(a1a2a3,q1)* (e,qf). Kui z>n, peab mõni olek (näiteks olek r esinema korduvalt, masinas olema tsükkel vastasel juhul peaks masina olekute arv olema lõpmatu). Masina tsüklilises osas tekibki sõna keskele 0..lõpmatu arv stringe v. Siit on näha, et kui keel ei võimalda sellist genereerimist, siis see kindlasti ei ole paremlineaarne, kui aga võimaldab, võib see olla paremlineaarne Kuna pumpamise lemmaga saab näidata keele L = 0 n1n mitteregulaarsuse, saame järeldada, et keelteklasside L3 on alamhulgaks L2-le sisalduvus on range. Myhill-Nerode'I teoreem (piisav ja tarvilik tingimus keelte regulaarsuseks): Olgu antu keel L stringide hulgast *. Olgu antud seos HL on alamhulgaks * x *. H kehtib stringide x ja y vahel parajasti siis, kui iga stringi z korral stringid xz ja yz kas kuuluvad korraga keelde L või ei kuulu sellesse. HL on ekvivalentsiseos, kuna xzHxz, xzHyz <=> yzHxz, xzHwz AND wzHyz => xzHyz.
annaabi.ee 
