"keelteklasside" - 1 õppematerjal

Teoreetilibe informaatika kordamisküsimused

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.