Boonus, 10 p. Olgu deterministlik lõplik automaat, mis tunneb ära keelt . On teada, et automaadil on olekut ja et keel sisaldab sõnet pikkusega . Märgista kõik õiged vastused.

Vali kõik automaatide paarid, mis tunnevad ära sama keelt. Selliseid paare võib olla rohkem kui üks – valida tuleb neist kõik.

(a)

(b)

(c)

(d)

(e)

Kui palju leidub ingliskeelseid sõnu, mille pikkus on 8 ja mis sisaldavad iga tähte A, B ja C vähemalt üks kord?

Õpetaja andis järgmise avaldise

,

kus ja , ning palus õpilastel leida sellega samaväärne avaldis. Kolm õpilast esitasid järgmised lahendused.

Oletame, et ettevõttes on programmeerijat ja juhti. Soovime uuele projektile määrata töötajat. Ühelt poolt saame valida töötajat töötaja hulgast viisil. Teiselt poolt valime esmalt programmeerijat viisil ja seejärel valime ülejäänud töötajat viisil. Siin väärtus muutub -st -ni. Konkreetse korral on meil korrutamisreegli põhjal valikut. Kokkuvõttes saame

Oletame, et meil on õpilaste rühm, mis koosneb poisist ja tüdrukust. Soovime valida õpilasest koosneva võistkonna. Ühelt poolt saame valida õpilasest koosneva võistkonna õpilase hulgast viisil. Teiselt poolt valime poissi viisil ja tüdrukut viisil. Siin väärtus muutub -st -ni. Konkreetse korral on meil korrutamisreegli põhjal valikut. Kokkuvõttes saame

Oletame, et meil on valget palli numbritega 1, 2, . . . , ja musta palli numbritega 1, 2, . . . , . Soovime valida palli ilma järjekorda ja kordusi arvestamata. Ühelt poolt saame seda teha viisil. Teiselt poolt valime suvalist palli viisil. Siis peame valima ülejäänud palli allesoleva palli hulgast. Seda saab teha viisil. Siin väärtus muutub -st -ni. Konkreetse korral on meil korrutamisreegli põhjal valikut. Kokkuvõttes saame

Kes õpilastest esitas(id) õige lahenduse?

(b) Boonusküsimus (10 punkti). Milline avaldis on võrdne avaldisega , kus ?