PSD 2014: Informatika je tudi znanost - formalni jeziki in avtomati

Genski kod

Iz genetike so nam znane štiri nukleotidne baze: A (adenin), C (citozin), G (gvanin) in T (timin). Po dve bazi se med seboj povezujeta v nukleotidne pare.

a) Zapiši množico B nukleotidnih baz?

b) Kolikšna je njena moč?

c) Kako bi matematično predstavil par baz? Zapiši nekaj parov.

d) Kako bi enostavno zapisal množico vseh možnih parov? Kolikšna je moč te množice?

e) Nekateri izmed teh parov so neveljavne kombinacije. Zapiši množico veljavnih parov.

Dvočrkovni zlogi

Zanimajo nas dvočrkovni zlogi sestavljeni iz črk slovenske abecede, kjer je prva črka soglasnik in druga samoglasnik., npr. ča, še, mi, bo, tu.

a) Zapiši množice: abeceda A, samoglasniki B in soglasniki C.

b) Kolikšna je moč A, B in C?

c) Zapiši vse relacije stroge vsebovanosti med A, B in C? Katere relacije bi še dodal, če bi šlo za (navadno) vsebovanost?

d) Naj bo A univerzalna množica. Zapiši čim več enačb med množicami A, B in C s pomočjo relacij unije, preseka, razlike in komplementa.

e) S katerim matematičnim konceptom bi predstavil dvočrkovne zloge? Zapiši jih nekaj.

f) Kako bi enostavo zapisal množico vseh dvočrkovnih zlogov? Kolikšna je moč te množice?

Abeceda

Kolikšna je moč

• slovenske abecede,
• angleške abecede,
• binarne abecede,
• oktalne abecede,
• šestnajstiške abecede,
• desetiške abecede,
• ASCII abecede,
• genske abecede?

Dolžina niza

a) Sestav nekaj nizov oz. besed iz črk slovenske abecede. Kakšna je njihova dolžina?

b) Sestavljati želimo slovenske stavke. Katere simbole še potrebujemo?

c) Kolikšna je dolžina niza:

• avtomat
• 01010101
• Juhuhuεpomladεjeεtu
• εεε

Stik nizov

Naj bodo w = 42, x = hokus, y = !, z = pokus. Zapiši nize:

• wx
• xwzy
• xεxεz
• x²zε
• w³
• ε¹⁰⁰
• (wεy)⁵

Σ*

a) Zapiši prvih 25 nizov, ki jih lahko tvorimo glede na gensko abecedo.

Namig: nize zapiši leksikografsko urejeno - po dolžini in abecedi.

b) Zapiši 85 niz v zaporedju nizov iz a).

b) Je res, da je Σ* vedno neskončna množica?

Namig: Kaj se zgodi, če je Σ prazna množica?

Jeziki

Zapiši naslednje jezike. Pri neskončnih jezikih zapiši le prvih nekaj najkrajših nizov.

a) Jezik veljavnih nukleotidnih baznih parov.

b) Jezik dvomestnih števil, ki so deljiva s 3 in 15.

c) Jezik nizov za stikalo za luč (da luč sveti).

d) Jezik nizov, ki vsebujejo enako število ničel in enic.

e) Jezik nizov, sestavljenih iz predklepajev in zaklepajev, tako da so oklepaji pravilno vgnezdeni.

Regularni izrazi

a) Zapiši regularni izraz za jezike iz prejšnje naloge. Se da za vse?

b) Zapiši regularni izraz za nize, ki so desetiška števila.

c) Zapiši regularni izraz za imena (prvi simbolj je črka, nadaljevanje pa je črka ali števka).

d) Zapiši regularni izraz za nalogo Preverjanje gesel iz razdelka Diagram prehodov.