Teoreticka informatika

[Killian]

Tak uvidime co to bude  .

Pre pobavenie, Turingov stroj postaveny z Lega 
http://www.youtube.com/watch?v=cYw2ewoO6c4&feature=fvst

[trek]

cooooooooooooooooool :D:D:D:D:D:D:D:D:D:D

[Casso]

Tak uvidime co to bude  .

Pre pobavenie, Turingov stroj postaveny z Lega 

Priznaj sa ze si googlil pri uceni a tak si sa k tomu dostal  ale peckove to je

[ApokalypS]

No len opravak nebude, Hudak povedal  .

to kedy povedal? ja som nic take nepostrehol..

[Killian]

Lalova citovala Hudaka na cvikach, povedal ze sme mali moznost ziskat dost bodov na zapocet aj bez zapoctovky (prednasky + aktivita = 18 a staci 16 tusim), kvoli tomu netreba opravnu.

Ludia mam otazku ku prikladu 4.4 z Plocicovych prikladov.

Code [Select] Expand


Navrhnite zásobníkový automat pre jazyk 1 = {x ∈ {a, b}∗,Na(x) = Nb(x)}


Spravne vyriesene to ma byt podla toho takto:

Code [Select] Expand


(q0, a,Z, q0, aZ)
(q0, a, a, q0, aa)
(q0, b, a, q0, ¸)
(q0, b,Z, q0, bZ)
(q0, b, b, q0, bb)
(q0, a, b, q0,lamb)
(q0, lamb, Z, q0, lamb)


Nechapem ako si vystacil iba  s jednym stavom q0. Pozrite si ten posledny krok "ak najdem lambda a zasobnik je prazdny, tak ostanem v stave q0 a dam lambda znak na zasobnik"? Kedy to skonci? Ako viem, ci uz bolo slovo skontrolovane... Nepojde to nejak donekonecna?

[Casso]

Nechapem ako si vystacil iba  s jednym stavom q0. Pozrite si ten posledny krok "ak najdem lambda a zasobnik je prazdny, tak ostanem v stave q0 a dam lambda znak na zasobnik"? Kedy to skonci? Ako viem, ci uz bolo slovo skontrolovane... Nepojde to nejak donekonecna?

Mnohe PDA, ktore sme mali v na cviku, si vystacili s jedinym stavom. tiez mi nieje jasna ta posledna instrukcia ale pda urcuje neakceptovanie retazca tym ze sa zastavi (nedefinovana trojica stav-paska-zasobnik)

[milaninho]

Uvidime, ja uz mam v pondelok  . Teraz pozeram do zasobnikovych automatov, tie deterministicke chapem ale nedeterministicke v niektorych pripadoch su nejake zaujimave (ako pri tom pripade s palindromom x.x^R, kde automat len tipne ze ci je v strede slova - takze realne ak zle odhadne stred slova tak skonci a nerozpozna to, alebo to nejako viackrat robi??  ).

co sa tyka toho nedeterminizmu je to tak ako spominal hore kolega.. prosste nedeterminizmus je o tom ze nevies presne ako zareagovat a preto si len tipnes.. potom bud krachnes, alebo ak je nejako implementovany navrat tak sa vies na to vetvenie vratit a skusit inu cestu(teda vsetky rozne moznosti a podla toho napokon prijmes alebo neprijmes slovo). ak som trepol nejaku somarinu tak ma kludne opravte:)

[cepi]

Nechapem ako si vystacil iba  s jednym stavom q0. Pozrite si ten posledny krok "ak najdem lambda a zasobnik je prazdny, tak ostanem v stave q0 a dam lambda znak na zasobnik"? Kedy to skonci? Ako viem, ci uz bolo slovo skontrolovane... Nepojde to nejak donekonecna?

Mnohe PDA, ktore sme mali v na cviku, si vystacili s jedinym stavom. tiez mi nieje jasna ta posledna instrukcia ale pda urcuje neakceptovanie retazca tym ze sa zastavi (nedefinovana trojica stav-paska-zasobnik)

takze ked sa zastavi a je daco v zasobniku tak slovo neakceptval, a ak sa zasobnik vyprazdni tak jo ?

[Casso]

Nechapem ako si vystacil iba  s jednym stavom q0. Pozrite si ten posledny krok "ak najdem lambda a zasobnik je prazdny, tak ostanem v stave q0 a dam lambda znak na zasobnik"? Kedy to skonci? Ako viem, ci uz bolo slovo skontrolovane... Nepojde to nejak donekonecna?

Mnohe PDA, ktore sme mali v na cviku, si vystacili s jedinym stavom. tiez mi nieje jasna ta posledna instrukcia ale pda urcuje neakceptovanie retazca tym ze sa zastavi (nedefinovana trojica stav-paska-zasobnik)

takze ked sa zastavi a je daco v zasobniku tak slovo neakceptval, a ak sa zasobnik vyprazdni tak jo ?

Jop presne tak, a nepozerajte sa na tie stroje tak realne. Su to abstraktne modely. Nedeterministicke varianty by ste hadam obcas ani na pc nenasimulovali

[Killian]

Podla mna by tam ale mal byt aspon jeden prechod stavu, pretoze instrukcia:
(q0, lamb, Z, q0, lamb)
- podla mna to zoberie aj prazdny znak na zaciatku, teda dam mu pasku a bude tam jeden prazdny znak. Tak zasobnik je prazdny, som v q0 a dostanem sa na prazdny znak = automat skonci uspesne. Nie?

[ApokalypS]

aj prazdne slovo je riesenie..

väcsinou sme davali, ze (q0, lamb, Z, qf, lamb); kde qf je finalovy stav

[Casso]

aj prazdne slovo je riesenie..

väcsinou sme davali, ze (q0, lamb, Z, qf, lamb); kde qf je finalovy stav

Uz som si to dostudoval, Akceptovanie moze byt realizovane dvojako:
1. vyprazdnenim zasobnika (nahradenim symbolu Z symbolom "lambda")
2. Prechodom do finalneho stavu (Zvycajne q_f)

[Snow]

Na zapocte by nemali byt ulohy z 10.cvika, pretoze v pondelok jedno cviko nebolo, kedze im nebol nikto zastupovat. Takze by to nebolo voci nim fer, takze 10.cviko na zapocte nebude. Tak to tvrdil Korecko na prednaske vcera, ze? A tiez nieco spominal, ze tie prve cvika nebudu, no neviem presne, coho sa to tyka, co nebude na zapocte. Je to tak?

[buhehe]

nemali by byt 1.cviko (gramatiky) a 10.cviko.
1 priklad ma byt z lahsich cvik (konecne automaty, Mealy->Moore a naopak, redukcia, ekvivalencia automatov, determinizacia, ksa a reg.vyrazy...) a dalsie 2 priklady by mali byt zo zasobnikovych automotov, sekvencnych zobrazeni alebo TS. Tak nejak som to pochopil na prednaske...

[buhehe]

aj prazdne slovo je riesenie..

väcsinou sme davali, ze (q0, lamb, Z, qf, lamb); kde qf je finalovy stav

Uz som si to dostudoval, Akceptovanie moze byt realizovane dvojako:
1. vyprazdnenim zasobnika (nahradenim symbolu Z symbolom "lambda")
2. Prechodom do finalneho stavu (Zvycajne q_f)

potom pre priklad 4.1 nestaci takto?

Code [Select] Expand

(q0, 0,Z, q0, 0Z)
(q0, 0, 0, q0, 00)
(q0, 1, 0, q0, lambda)
nebude slovo akceptovane vyprazdnenim zasobnika?

[Casso]

potom pre priklad 4.1 nestaci takto?

Code [Select] Expand

(q0, 0,Z, q0, 0Z)
(q0, 0, 0, q0, 00)
(q0, 1, 0, q0, lambda)
nebude slovo akceptovane vyprazdnenim zasobnika?

podlamna je to jedna z variant. Myslim ze by ti to cviciaci uznal, a ak nie tak by si sa dohadal k pravde

[ApokalypS]

imho, zaklad bude, ze tomu chapeme..
Ľaľová spominala, ze sa nemusime presne dopracovat k vysledku, hlavne, ze sme to dobre zacali.. aj na ukor bodov..
aspon ja to tak chapem..

[kOsTi]

btw, neviete co su to za priklady na FTP v adresari zapich?

[DeViLvs]

btw, neviete co su to za priklady na FTP v adresari zapich?

Vyzera to, ze to su priklady zo ZI (FJaA). Tam sa neberu TS a tie veci z poslednych cvik. Preto sa chcem spytat, kde by sa dali zohnat priklady na tieto veci. Aj tie priklady Plocicu su original z FJaA, cize iba po Zasob.Automaty.

[cepi]

nemali by byt 1.cviko (gramatiky) a 10.cviko.
1 priklad ma byt z lahsich cvik (konecne automaty, Mealy->Moore a naopak, redukcia, ekvivalencia automatov, determinizacia, ksa a reg.vyrazy...) a dalsie 2 priklady by mali byt zo zasobnikovych automotov, sekvencnych zobrazeni alebo TS. Tak nejak som to pochopil na prednaske...

viem tak ze budu TS a ZA nabeton a zrejme nieco z mealy/moore... redukcia, ekvivalencia... co su to tie sekvencne zobrazenia nejak si nepamatam ze by sme to brali

[Payne]

Hej a take tie regularne vyrazy a take cudne obrazky hned po tom, to nikto nespominal ze by mohlo byt, co? lebo su to celkom dost bludy

[cepi]

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

a este tu je simulator na zasobnikovy automat ale ten kresli len tie stavy a nerobi s instrukciami ak ma niekto lepsi sem snim

http://ozark.hendrix.edu/~burch/proj/autosim/

[cepi]

ze sa pytas

[Casso]

Hej a take tie regularne vyrazy a take cudne obrazky hned po tom, to nikto nespominal ze by mohlo byt, co? lebo su to celkom dost bludy

my sme to mali na cviku a je to pomerne jednoduche, teda ak myslis to ze ako sa riesi sekvencia, rekurzia, vetvenie a pod v regularnych vyrazoch. Ku kazdemu prvku r.v. tam je nejaky k.s.a, ktoreho pospajanim ti vznikne k.s.a. rozoznavajuci cely regularny vyraz.  ten sa da este zvycajne zredukovat

[cepi]

a tie sekvnecne to bude ? a chape to niekto ?