Notes 1

Question 1

Stafróf er ?

Answer 1

Mengi tákna (stafa) t.d. {0,1,2,…,9}

Question 2

Strengur er ?

Answer 2

Runa af táknum

Question 3

Löggeng endanleg stöðuvel

Answer 3

Einföld tölva sem hefur ekkert minni utan að þekkja í hvaða stöðu hún er

Question 4

Hvað gerir löggeng endanleg stöðuvel í hverju skrefi?

Answer 4

Les eitt tákn úr inntaki og uppfærir stöðuna

Question 5

Hvernig er inntakið lesið?

Answer 5

Frá vinstri til hægra, og ekki hægt að fara til baka

Question 6

Hvernig lýsum við stöðuvél myndrænt?

Answer 6

Með stefndu neti

Question 7

Ómerkta örin í byrjun á stefna neti stöðuvélarinnar ?

Answer 7

Bendir á upphafsástand

Question 8

Hvernig táknum við loka/samþykktar ástand?

Answer 8

Með tvöföldum hring

Question 9

Hversu mörg samþykktarástand geta verið í stöðuvélum?

Answer 9

ekkert, eitt eða fleiri

Question 10

Vélin er sögð löggeng því?

Answer 10

Fjöldi örva úr sérhverju ástandi er alltaf jafn fjölda tákna í stafrófinu

Question 11

Hvernig lýsum við stöðuvél myndrænt?

Answer 11

Með stefndu neti

Question 12

Ómerkta örin í byrjun á stefna neti stöðuvélarinnar ?

Answer 12

Bendir á upphafsástand

Question 13

Hvernig táknum við loka/samþykktar ástand?

Answer 13

Með tvöföldum hring

Question 14

Hversu mörg samþykktarástand geta verið í stöðuvélum?

Answer 14

ekkert, eitt eða fleiri

Question 15

Vélin er sögð löggeng því?

Answer 15

Fjöldi örva úr sérhverju ástandi er alltaf jafn fjölda tákna í stafrófinu

Question 16

Hvað er þetta : (Q, Σ, δ, q0, F) ?

Answer 16

Formleg skilgreining á löggengri endanlegri stöðuvél, 5-eind.

Question 17

Hvað stendur Q fyrir?

Answer 17

Ástönd

Question 18

Hvað stendur Σ fyrir?

Answer 18

Stafróf

Question 19

Hvað stendur δ fyrir?

Answer 19

δ : Q × Σ−→ Q er yfirfærslufall

Question 20

Hvað stendur q0 fyrir?

Answer 20

q0 ∈ Q er upphafsástand

Question 21

Hvað stendur F fyrir?

Answer 21

F ⊆ Q er mengi samþykktarástanda

Question 22

Mál er sagt vera reglulegt ef ?

Answer 22

Stöðuvél þekkir það

Question 23

Reglulegar aðgerðir á málum eru :

Answer 23

Sammál, Samkeyting og Stjörnu-lokun

Question 24

Aðgerð á stökum í mengi S er lokuð ef?

Answer 24

útkoman úr aðgerðinni er í S

Question 25

Brigðgeng stöðuvél er skilgreind ?

Answer 25

Úr sérhverju ástandi geta verið engin, ein eða fleiri færslur

Question 26

Tvær stöðuvélar eru jafngildar ef ?

Answer 26

Þær þekkja sama málið