Teoreticka informatika

cepi · 29.11.2009, 03:22:45

dakujeme

kOsTi · 29.11.2009, 03:52:05

ah kua nejak som zabudol o co ide v tych zasobnikovych automatoch :/ vedel by to niekto troska vysvetlit na tom priklade?

L = {0ⁿ1ⁿ | n > 0}

thx

Casso · 29.11.2009, 04:13:30

Quote from: kOsTi on 29.11.2009, 03:52:05
ah kua nejak som zabudol o co ide v tych zasobnikovych automatoch :/ vedel by to niekto troska vysvetlit na tom priklade?

L = {0ⁿ1ⁿ | n > 0}

thx

Trocha "teorie" na uvod:
format instrukcii hadam ovladas ale pre istotu: (aktualny stav, vstup,vrchol zasobnika, nasledujuci stav, novy vrchol zasobnika)
Z - symbol oznacujuci dno zasobnika
Po kazdej instrukcii sa posunie citacia hlava o jeden krok doprava

takze program:
(q0, 0, Z, q0, 0Z), pri nacitani prvej nuly za vyberie Z zo zasobnika a nahradi dvojicou 0Z (vpodstate ako keby si dal 0 na vrch)
(q0, 0, 0, q0, 00) pri dalsich nulach sa jednoducho da navrch dalsia nula (jedna sa akokeby vyberie a daju sa tam dve)
(q0, 1, 0, q1, lambda) prva jednotka; zo zasobnika sa vyberie nula ( vyberie sa nula a do zasobnika sa vopcha "nič")
(q1, 1, 0, q1, lambda) to iste ako predchadzajuca instrukcia, ale pre ostatne jednotky
(q1, lambda, Z, qF, Z) ak boli nacitane vsetky znaky (vstup je lambda) a v zasobniku nieje ziadna nula (len dno) to znamena ze pocet nul a jednotiek bol rovnaky. v tomto pripade sa prejde do finalneho stavu

dufam ze som to napisal dobre, predsa je uz 10hodin. tazko sa to vysvetluje takto nadialku...

kOsTi · 29.11.2009, 04:58:49

diky moc... tak uz asi chapem.. cize tam sa neriesia take veci ze napr. ked citame uz tie jednotky: na vstupe bude dalsia jednotka ale zasobnik bude uz prazdny...

Casso · 29.11.2009, 05:16:29

Quote from: kOsTi on 29.11.2009, 04:58:49
diky moc... tak uz asi chapem.. cize tam sa neriesia take veci ze napr. ked citame uz tie jednotky: na vstupe bude dalsia jednotka ale zasobnik bude uz prazdny...

Po vyprazdneni zasobnika , t.j. Odstranenia dna Z, sa automat zastavi.

buhehe · 29.11.2009, 05:43:29

no pockaj v tomto pripade sa automat zastavi prechodom do koncoveho stavu qF pretoze este vzdy je v zasobniku Z, ak by posledna instrukcia bola (q1, lambda, Z, q1, lambda) potom by sa automat zastavil vyprazdnenim zasobnika nie?

Casso · 29.11.2009, 05:48:54

Quote from: buhehe on 29.11.2009, 05:43:29
no pockaj v tomto pripade sa automat zastavi prechodom do koncoveho stavu qF pretoze este vzdy je v zasobniku Z, ak by posledna instrukcia bola (q1, lambda, Z, q1, lambda) potom by sa automat zastavil vyprazdnenim zasobnika nie?

Presne. v zbierke su uvadzane tusim obe metody zastavenia. Obcas mam pocit ze to tak robia aby nas viac zmiatli...

kOsTi · 29.11.2009, 05:50:21

Quote from: Casso on 29.11.2009, 05:16:29
Quote from: kOsTi on 29.11.2009, 04:58:49
diky moc... tak uz asi chapem.. cize tam sa neriesia take veci ze napr. ked citame uz tie jednotky: na vstupe bude dalsia jednotka ale zasobnik bude uz prazdny...
Po vyprazdneni zasobnika , t.j. Odstranenia dna Z, sa automat zastavi.

takze ten posledny stav kde je na vstupe lambda riesi aj to ked tam bude jednotka a v zasobniku Z? alebo ako?

kOsTi · 29.11.2009, 06:06:21

takze automat sa zastavi proste len preto ze taky stav nie je urceny?

kOsTi · 29.11.2009, 06:30:48

aha no podla toho co som teraz cital tak lambda moze znamenat aj ignorovnaie vstupu

cepi · 29.11.2009, 16:09:33

Quote from: kOsTi on 29.11.2009, 06:06:21
takze automat sa zastavi proste len preto ze taky stav nie je urceny?

hej a ak je nieco v zasobniku tak slovo nevyhovuje

Payne · 29.11.2009, 17:15:35

Chcem sa spytat ze v tej plocicovej zbierke priklad 4.6 to je dobre ratany? dajak mi tam naviac prida ten stav q1. Dalej stat 4.2 to dakto ratal na cvikach? bo my ani nie...

Casso · 29.11.2009, 17:20:06

Quote from: Payne on 29.11.2009, 17:15:35
Chcem sa spytat ze v tej plocicovej zbierke priklad 4.6 to je dobre ratany? dajak mi tam naviac prida ten stav q1. Dalej stat 4.2 to dakto ratal na cvikach? bo my ani nie...

bez dvoch stavov by ti presiel aj prazdny retazec (hoc v zadani taka podmienka nieje....)

Payne · 29.11.2009, 17:43:57

sak tam je {a,b}*, * znamena 0 a viac krat

Casso · 29.11.2009, 17:49:23

Quote from: Payne on 29.11.2009, 17:43:57
sak tam je {a,b}*, * znamena 0 a viac krat

sak pisem ze v zadani taka podmienka nieje... niekto to prekombinoval a zabudol uviest cele znenie zadania, klasika v tych knihach...

buhehe · 29.11.2009, 21:03:08

nevie niekto co je to baza pri zobrazeniach a ako sa urcuje?

TradeMark · 29.11.2009, 21:51:04

Baza je mnozina tried, ktore ti vyjdu, pri prikladoch kde je modulo to vyjde vacsinou tak ze tych tried mas tolko ake je modulo.

buhehe · 29.11.2009, 22:02:20

a tie triedy dostanem odkial?

trek · 29.11.2009, 22:36:58

tie triedy proste musis zistit...ak mas napr (pocet 1)mod2 = 0, tak v jednej triede vypises priklady takych zobrazeni, kde po deleni dostanes zvysok 0 a v druhej triede vypises tie zobrazenia kde dostanes zvysok 1...tie triedy su potom aj nasledne stavy v konecnom automate

les paul · 29.11.2009, 23:49:20

Quote from: cepi on 29.11.2009, 02:57:48
nasiel som dobry simulator turinga http://www.isvet.sk/Download/15/Turingov-stroj--v-1-5- vie to krokovat, ukazuje priebeh postupne, este aj stavy kresli. skusal som v nom ten priklad co sme mali na cvikach ze:

x je z {0,1}* N0(x)=N1(x) ten je tu http://uloz.to/3185108/spravne.tm napodiv funguje

uzite v zdravy a kto sa bude nudit tak moze skusit spravit dalsie priklady a hodit ich niekam

caute prikladam pre ten simulator od cepiho riesenie dalsieho prikladu L={x|x ma mnozinu symbolov {a,b,c}, pocet a = pocet b = pocet c}.
Zadanie toho prikladu raz spomenul Korecko na cviku ale sme ho na hodine neriesili....Neviem ci to je idealne riesenie ale tak by som to asi robil na pisomke. Mozno pomoze

LinK: http://www.edisk.cz/stahnout-soubor/74929/x_z_mnoziny_a_b_c_s_rovnakym_poctom.tm_10.83KB.html

Pribina · 30.11.2009, 00:19:35

Okej neda mi to...4.6 v Plocicovych prikladoch mi nejak nesedi, dajake divne riesenie...prikladam svoje, ktore sa mi zda byt celkom spravne...skuste sa na to kuknut. Mozno to na pisomke dakomu pomoze. Takze moje riesenie :

(q0, a, Z, q1, Z)
(q0, b, Z, q0, bZ)
(q0, b, b, q0, bb)
(q0, a, b, q1, b)
(q0, a, a, q1, a)
(q0, b, a, q0, lambda)
(q1, a, a, q0, aa)
(q1, b, a, q1, lambda)
(q1, a, b, q0, lambda)
(q1, b, b, q1, bb)
(q1, a, Z, q0, aZ)
(q1, b, Z, q1, bZ)
(q0, lambda, Z, qF, Z)

Tak je to mozno krkolomnejsie ale skusal som to na vela kombinacii a vyslo mi to furt takze by to mohlo aj byt spravne. Logicky ten automat tiez sedi. Tak skuste sa na to kuknut.

les paul · 30.11.2009, 00:43:22

nie je to 4.5 ten priklad ? L(M) = {x ∈ {a, b}∗,Na(x) = Nb(x)}. ?

a neviem ci je to spravne....som si skusil tvoje riesenie pre aaabbb a ked prejdem celym retazcom (teda nacitam posledne b) cez instrukciu (q1, b, a, q1, lambda) tak som v stave q1 a nemam to ako ukoncit ked nacitam lambdu, teda som za koncom vstupneho retazca..to tam asi treba este osetrit s (q1, lambda, Z, qF, Z)

Pribina · 30.11.2009, 00:53:38

aaabbb ti to nerozpozna jak si to robil?

som skusal teraz

Pribina · 30.11.2009, 00:57:22

jaaaj uz viem co myslis ale netreba to osetrovat pretoze Korecko vravel ze ak nema automat instrukciu tak sa sam zastavi...to znamena ze chybovy stav a nerozpoznal slovo

trek · 30.11.2009, 01:19:21

Quote from: les paul on 30.11.2009, 00:43:22
nie je to 4.5 ten priklad ? L(M) = {x ∈ {a, b}∗,Na(x) = Nb(x)}. ?

a neviem ci je to spravne....som si skusil tvoje riesenie pre aaabbb a ked prejdem celym retazcom (teda nacitam posledne b) cez instrukciu (q1, b, a, q1, lambda) tak som v stave q1 a nemam to ako ukoncit ked nacitam lambdu, teda som za koncom vstupneho retazca..to tam asi treba este osetrit s (q1, lambda, Z, qF, Z)

ee to by mal byt priklad L(M) = {x ∈ {a, b}∗,Na(x) = 2Nb(x)}...funguje to aspon co som skusal