Teoreticka informatika

[ppt]

pr. 5 (moja verzia nehovorim ze spravna) :


q0, (c,Z,Z), (c,Z,Z), q0, (R,R,R)
q0, (a,B,B), (a,B,B), qa, (R,-,-)
qa, (a,B,B), (a,B,B), q0, (R,R,-)
q0, (b,B,B), (b,B,B), q1, (R,-,R)
q1, (b,B,B), (b,B,B), q1, (R,-,R)
q1, (c,B,B), (c,B,B), q2, (-,L,L)
q2, (c,B,B), (c,B,B), q2, (R,L,L)
q2, (s,Z,Z), (s,Z,Z), qF, (-,-,-)

tak zrucnejsi ludia skuste sa na to pozriet ci moze byt a ked ne opravte.

EDIT: priklad je a^2n b^n c^n som zabudol

Preco je ta prva instrukcia q0, (c,Z,Z), (c,Z,Z), q0, (R,R,R)? Ako moze prist na vstupnu pasku "c", ked slovo ma vyzerat napr: aabc? A co tam potom znamena to Z? A potom aj nakonci, preco tam ti pride na vstupe "s"? Nemalo by tam prist "B"?
Thx.

[Pribina]

pr.4  link na obrazok http://img141.imageshack.us/i/sekvencnystrojwv8.jpg/
este v tom obrazku maju chybat prechody:
b/ab z q0 do q1
a/lamba z q3 do q3
ale nerozumiem tomu prikladu

Ten prvy prechod je tam preto keby si chcel pre vsetky bcka generovat iba acka, a mozes aj 2i aciek vygenerovat preto tam musel pribudnut ten prechod. Ten druhy preto lebo mozes pre a z L1 vygenerovat aj menej aciek ako m teda musis byt schopny nakonci aj par prazdnych znakov vediet vygenerovat

[Pribina]

pr. 5 (moja verzia nehovorim ze spravna) :


q0, (c,Z,Z), (c,Z,Z), q0, (R,R,R)
q0, (a,B,B), (a,B,B), qa, (R,-,-)
qa, (a,B,B), (a,B,B), q0, (R,R,-)
q0, (b,B,B), (b,B,B), q1, (R,-,R)
q1, (b,B,B), (b,B,B), q1, (R,-,R)
q1, (c,B,B), (c,B,B), q2, (-,L,L)
q2, (c,B,B), (c,B,B), q2, (R,L,L)
q2, (s,Z,Z), (s,Z,Z), qF, (-,-,-)

tak zrucnejsi ludia skuste sa na to pozriet ci moze byt a ked ne opravte.

EDIT: priklad je a^2n b^n c^n som zabudol

Preco je ta prva instrukcia q0, (c,Z,Z), (c,Z,Z), q0, (R,R,R)? Ako moze prist na vstupnu pasku "c", ked slovo ma vyzerat napr: aabc? A co tam potom znamena to Z? A potom aj nakonci, preco tam ti pride na vstupe "s"? Nemalo by tam prist "B"?
Thx.

lebo pocitadlo ma vstup ohraniceny symbolmi c(preskrtnute) vlavo a s(preskrtnute) vpravo a na zaciatku sa citacia hlava nachadza pod c(preskrtnute)

EDIT: Sorry moja chyba v prvej instrukcii je preskrtnute c :D

[badi]

pr. 5 (moja verzia nehovorim ze spravna) :


q0, (c,Z,Z), (c,Z,Z), q0, (R,R,R)
q0, (a,B,B), (a,B,B), qa, (R,-,-)
qa, (a,B,B), (a,B,B), q0, (R,R,-)
q0, (b,B,B), (b,B,B), q1, (R,-,R)
q1, (b,B,B), (b,B,B), q1, (R,-,R)
q1, (c,B,B), (c,B,B), q2, (-,L,L)
q2, (c,B,B), (c,B,B), q2, (R,L,L)
q2, (s,Z,Z), (s,Z,Z), qF, (-,-,-)

tak zrucnejsi ludia skuste sa na to pozriet ci moze byt a ked ne opravte.

EDIT: priklad je a^2n b^n c^n som zabudol

vysledkom toho ma byt co, ze v tych pocitadlach bude NIC ? alebo ze jedno pocitadlo bude ukazovat pocet a a druhe pocet b,c ? ci ako ? nerozumiem absolutne ...
lebo v skriptach je napisane ze hlava sa nachadza nad takym polickom pocitadla aka hodnota je v nom zapamatana

[Pribina]

V pocitadlach sa bude ukladat : v prvom pocitadle cislo n (a^2n) a v druhom tiez n kde b^n. Pri vstupe c sa presunie hlava dolava na oboch pocitadlach. Teda sa zmensuje hodnota stale o jedno na kazdom pocitadle. ked pride symbol s(preskrtnute) a v pocitadlach nie je nic slovo vyhovovalo podmienke a^2n b^n c^n. Co sa tyka tych pocitadiel badi, tak na paskach pocitadiel sa moze zapisat iba symbol B a symbol Z (iba na zaciatku) pocitadla. Preto stale Bcka sa tam zapisuju.

[badi]

OK OK .. to som chcel vediet a teraz k tomu kodovaniu
STAV, CITAM , ZAPISUJEM, NOVY STAV, POSUN
  q0  , (a,B,B) ,  (a,B,B)    ,     qa        ,  (R,-,-)
ak spravne chapem tak
potom prva zatvorka zanmena ze
a - znak z pasky
B - znak v pocitadle 1.
B - znak v pocitalde 2.
 ?


TAKTO BY TO MALO BYT ASI SPRAVNE

q0, (c,Z,Z), (c,Z,Z), q0, (R,R,R)
q0, (a,B,B), (a,B,B), q0, (R,R,-)
q0, (b,B,B), (b,B,B), q1, (R,-,R)
q1, (b,B,B), (b,B,B), q1, (R,-,R)
q1, (c,B,B), (c,B,B), q2, (-,L,L)
q2, (c,B,B), (c,B,B), q1, (R,L,-) 
q1, (s,Z,Z), (s,Z,Z), qF, (-,-,-)

[Miro]

pr. 5 (moja verzia nehovorim ze spravna) :


q0, (c(preskrtnute),Z,Z), (c(preskrtnute),Z,Z), q0, (R,R,R)
q0, (a,B,B), (a,B,B), qa, (R,-,-)
qa, (a,B,B), (a,B,B), q0, (R,R,-)
q0, (b,B,B), (b,B,B), q1, (R,-,R)
q1, (b,B,B), (b,B,B), q1, (R,-,R)
q1, (c,B,B), (c,B,B), q2, (-,L,L)
q2, (c,B,B), (c,B,B), q2, (R,L,L)
q2, (s(preskrtnute),Z,Z), (s(preskrtnute),Z,Z), qF, (-,-,-)

tak zrucnejsi ludia skuste sa na to pozriet ci moze byt a ked ne opravte.

EDIT: priklad je a^2n b^n c^n som zabudol

tam to vyzrea tak, ze moze zacat aj b-ckom .. takze spolu s pribinom sme na toto este prerobili.. asi to je uz lepsie

q0, (c(preskrtnute),Z,Z), (c(preskrtnute),Z,Z), q0, (R,R,R)
q0, (a,B,B), (a,B,B), qa, (R,-,-)
qa, (a,B,B), (a,B,B), qa2, (R,R,-)
qa2, (b,B,B), (b,B,B), q1, (R,-,R)
qa2, (a,B,B), (a,B,B), qa, (R,-,-)
q1, (b,B,B), (b,B,B), q1, (R,-,R)
q1, (c,B,B), (c,B,B), q2, (R,L,L)
q2, (c,B,B), (c,B,B), q2, (R,L,L)
q2, (s,Z,Z), (s,Z,Z), qF, (-,-,-)

[McLarenPP]

mam jednu namietku k prvemu riadku - podla mna by na konci malo byt (R,-,-), pretoze na zaciatku neinkrementujeme pocitadla pri precitani prveho c(preciarknuteho). Aspon tak mi to vychadza, lebo ked som si to odsimuloval na slove aaaabbcc, tak riesenie nevyslo, citacia hlava pocitadiel sa na konci nenechadzala na Z, ale na prvom B hned napravo od Z. Opravte ma, ked sa mylim.

[Miro]

mam jednu namietku k prvemu riadku - podla mna by na konci malo byt (R,-,-), pretoze na zaciatku neinkrementujeme pocitadla pri precitani prveho c(preciarknuteho). Aspon tak mi to vychadza, lebo ked som si to odsimuloval na slove aaaabbcc, tak riesenie nevyslo, citacia hlava pocitadiel sa na konci nenechadzala na Z, ale na prvom B hned napravo od Z. Opravte ma, ked sa mylim.

jasne .. to som prehliadol nejako .. asi mas pravdu .. opravim to tam hore aby to bolo presne napisane

EDIT .. resp. ale potom tie dalsie riadky uz nebudu sediet .. lebo tam to pozera ci tam je B znak v pocitadle .. aaa


EDIT2: toto je upravene .. na zaciatku sa to nezmeni ale zmeni sa ten riadok tak jak to mal povodne pribina len mne sa to nezdalo :-D (riadok 7) .. cize tu to je opat zmenene .. skus pozriet .. teraz sa mi zda ze ide aj toto aaaabbcc .. len ja som uz total mimo taze skontrolujte

q0, (c(preskrtnute),Z,Z), (c(preskrtnute),Z,Z), q0, (R,R,R)
q0, (a,B,B), (a,B,B), qa, (R,-,-)
qa, (a,B,B), (a,B,B), qa2, (R,R,-)
qa2, (b,B,B), (b,B,B), q1, (R,-,R)
qa2, (a,B,B), (a,B,B), qa, (R,-,-)
q1, (b,B,B), (b,B,B), q1, (R,-,R)
q1, (c,B,B), (c,B,B), q2, (-,L,L)
q2, (c,B,B), (c,B,B), q2, (R,L,L)
q2, (s,Z,Z), (s,Z,Z), qF, (-,-,-)

[TradeMark]

Ide sa vam prihlasit na terminy 29.1 a neskor?

[McLarenPP]

dalo by sa to vyriesit napr. takto (ked berieme povodny prvy riadok):

q0, (c(preskrtnute),Z,Z), (c(preskrtnute),Z,Z), q0, (R,R,R)
q0, (a,B,B), (a,B,B), qa, (R,-,-)
qa, (a,B,B), (a,B,B), qa2, (R,R,-)
qa2, (b,B,B), (b,B,B), q1, (R,-,R)
qa2, (a,B,B), (a,B,B), qa, (R,-,-)
q1, (b,B,B), (b,B,B), q1, (R,-,R)
q1, (c,B,B), (c,B,B), q2, (R,L,L)
q2, (c,B,B), (c,B,B), q2, (R,L,L)
q2, (s,B,B), (s,B,B), q3, (-,L,L)
q3, (s,Z,Z), (s,Z,Z), qF, (-,-,-)

postup rovnaky, len povodny posledny riadok sa stane predposlednym, a posunu sa pocitadla dolava(cize sa dekrementuju naspat, kedze v prvom kroku sa inkrementovali) a prejde sa do stavu q3, a az v nom ak budu pocitadla vynulovane, tak sa prejde do koncoveho stavu.

[Miro]

dalo by sa to vyriesit napr. takto (ked berieme povodny prvy riadok):

q0, (c(preskrtnute),Z,Z), (c(preskrtnute),Z,Z), q0, (R,R,R)
q0, (a,B,B), (a,B,B), qa, (R,-,-)
qa, (a,B,B), (a,B,B), qa2, (R,R,-)
qa2, (b,B,B), (b,B,B), q1, (R,-,R)
qa2, (a,B,B), (a,B,B), qa, (R,-,-)
q1, (b,B,B), (b,B,B), q1, (R,-,R)
q1, (c,B,B), (c,B,B), q2, (R,L,L)
q2, (c,B,B), (c,B,B), q2, (R,L,L)
q2, (s,B,B), (s,B,B), q3, (-,L,L)
q3, (s,Z,Z), (s,Z,Z), qF, (-,-,-)

postup rovnaky, len povodny posledny riadok sa stane predposlednym, a posunu sa pocitadla dolava(cize sa dekrementuju naspat, kedze v prvom kroku sa inkrementovali) a prejde sa do stavu q3, a az v nom ak budu pocitadla vynulovane, tak sa prejde do koncoveho stavu.

tu ked sa ale na zaciatku neposunies tak mas stale Z v pocitadlach nastavene .. a ty kontrolujes ci tam je B

[McLarenPP]

dalo by sa to vyriesit napr. takto (ked berieme povodny prvy riadok):

q0, (c(preskrtnute),Z,Z), (c(preskrtnute),Z,Z), q0, (R,R,R)
q0, (a,B,B), (a,B,B), qa, (R,-,-)
qa, (a,B,B), (a,B,B), qa2, (R,R,-)
qa2, (b,B,B), (b,B,B), q1, (R,-,R)
qa2, (a,B,B), (a,B,B), qa, (R,-,-)
q1, (b,B,B), (b,B,B), q1, (R,-,R)
q1, (c,B,B), (c,B,B), q2, (R,L,L)
q2, (c,B,B), (c,B,B), q2, (R,L,L)
q2, (s,B,B), (s,B,B), q3, (-,L,L)
q3, (s,Z,Z), (s,Z,Z), qF, (-,-,-)

postup rovnaky, len povodny posledny riadok sa stane predposlednym, a posunu sa pocitadla dolava(cize sa dekrementuju naspat, kedze v prvom kroku sa inkrementovali) a prejde sa do stavu q3, a az v nom ak budu pocitadla vynulovane, tak sa prejde do koncoveho stavu.

tu ked sa ale na zaciatku neposunies tak mas stale Z v pocitadlach nastavene .. a ty kontrolujes ci tam je B

ale ja sa na zaciatku posuniem, to je to tvoje povodne riesenie, len zmeneny koniec.

[Mao]

to ze zacne bckom netreba osetrovat, to povodne pribinove riesenie OK
ak mate naprv vstup bc,  tak pri pohybe smerom vlavo sa dostane do konfiguracie $,Z,B a pre nu nie je definovany prechod, cize to neakceptuje,

[Miro]

dalo by sa to vyriesit napr. takto (ked berieme povodny prvy riadok):

q0, (c(preskrtnute),Z,Z), (c(preskrtnute),Z,Z), q0, (R,R,R)
q0, (a,B,B), (a,B,B), qa, (R,-,-)
qa, (a,B,B), (a,B,B), qa2, (R,R,-)
qa2, (b,B,B), (b,B,B), q1, (R,-,R)
qa2, (a,B,B), (a,B,B), qa, (R,-,-)
q1, (b,B,B), (b,B,B), q1, (R,-,R)
q1, (c,B,B), (c,B,B), q2, (R,L,L)
q2, (c,B,B), (c,B,B), q2, (R,L,L)
q2, (s,B,B), (s,B,B), q3, (-,L,L)
q3, (s,Z,Z), (s,Z,Z), qF, (-,-,-)

postup rovnaky, len povodny posledny riadok sa stane predposlednym, a posunu sa pocitadla dolava(cize sa dekrementuju naspat, kedze v prvom kroku sa inkrementovali) a prejde sa do stavu q3, a az v nom ak budu pocitadla vynulovane, tak sa prejde do koncoveho stavu.

tu ked sa ale na zaciatku neposunies tak mas stale Z v pocitadlach nastavene .. a ty kontrolujes ci tam je B

ale ja sa na zaciatku posuniem, to je to tvoje povodne riesenie, len zmeneny koniec.

aha jasne uz pozeram .. som prehliadol sorry .. aj tak by sa potom dalo .. ze osetris este to ze raz sa posunie .. pribina to mal tak ze pri prvom C ak prislo tak sa neposunul stroj doprava

[johnyo13]

inac neviem ci to tu bolo spomenute, ale teraz mi napadlo, ze na prvom termine sme si mohli po rozdani zadani oficialne medzi sebou vymenit miesta a teda aj skupiny...
Tymto sa chcem zaroven podakovat cloveku, ktoremu sa nepozdavali jeho otazky (turing. vypocit. fcie a alebra logiky a problem fcionalnej uplnosti), co som samozrejme patricne vyuzil

[Pribina]

Cize nas take necaka kedze nie sme uz prvy termin

[johnyo13]

to uz neviem, nebolo povedane, ze je to kvoli tomu ze sme prvi, len ze ked sa niekomu nepacia otazky a najde niekoho co sa chce vymenit, moze...

[Pribina]

Celkom pozitivna sprava diky za info hned mam lepsiu naladu, dufam ze vsetci v stredu porobime

[Payne]

to budew skorej tym, ze sme boli ako prva skupina a mali sme priklady co ani nikto necakal a hudak bol chory a neskorej prisiel plus koreckova benevolentnost nam pomoct

pochybujem ze aj na inych terminoch sa bude dat...

[mio]

asi sa vam to bude zdat trochu blba otazka, ale mozete mi prosim niekto vysvetlit ako funguje ta metoda posunu obsahu pasky TS ? dakujem ... (viem, ze to posunie slovo na vstupnej paske o k-policok, ale ako ? ) najlepsie by bolo pre k=1 dakujem este raz

[Martin18]

asi sa vam to bude zdat trochu blba otazka, ale mozete mi prosim niekto vysvetlit ako funguje ta metoda posunu obsahu pasky TS ? dakujem ... (viem, ze to posunie slovo na vstupnej paske o k-policok, ale ako ? ) najlepsie by bolo pre k=1 dakujem este raz

tak v skratke snad si dobre pamatam: na paske mas napr ABC a chces posunut o 1 vpravo. Prides nad A zapamatas si ho a das tam prazdny znak,posunies sa nad B, B si zapamatas a A tam zapises, posunies sa nad C,C si zapamatas a B zapises,posunies sa do prava a zapises C. 

[mio]

asi sa vam to bude zdat trochu blba otazka, ale mozete mi prosim niekto vysvetlit ako funguje ta metoda posunu obsahu pasky TS ? dakujem ... (viem, ze to posunie slovo na vstupnej paske o k-policok, ale ako ? ) najlepsie by bolo pre k=1 dakujem este raz

tak v skratke snad si dobre pamatam: na paske mas napr ABC a chces posunut o 1 vpravo. Prides nad A zapamatas si ho a das tam prazdny znak,posunies sa nad B, B si zapamatas a A tam zapises, posunies sa nad C,C si zapamatas a B zapises,posunies sa do prava a zapises C. 

prosim ta a mohol by si aj formalne ? lebo Hudak pisal cosi take :

([q,B],a,B,[q,a],R)
([q,a],b,a,[q,b],R)
([q,a],B,a,[q,B],R)
([q,B],a,a,[q,B],L)
([q,B],B,B,[q,B],R)

co tym chcel povedat ? dakujem ...

[Martin18]

([q,B],a,B,[q,a],R) tym asi tolko ze si v stave q a mas zapametane B  ([q,B]) na vstupe mas a, zapises tam B,toto co si mal zapamatane, ides do stavu q a zapamatas si a (toto co si cital) a ides do prava..

presnejsie je to v tej knihe hopcroft..

[mio]

([q,B],a,B,[q,a],R) - cize pamata si "B", na vstupe je "a", zapise tam "B" a pamata si "a" a posunie sa doprava
([q,a],b,a,[q,b],R) - pamata si "a", na vstupe je "b", zapise tam "a" a pamata si "b" a posunie sa doprava
([q,a],B,a,[q,B],R) - (na konci retazca) pamata si "a", na vstupe je "B", zapise tam "a" a pamata si "B" a posunie sa doprava
([q,B],a,a,[q,B],L) - a toto je naco ?
([q,B],B,B,[p,B],R) - a teraz len skontrolujem, ze je koniec retazca a prejdem do finalneho stavu "p"

je to tak ? a potom preco ked si pamatam "b" tak uz nie je pre nho dalsia instrukcia  ? ... napriklad ([q,b],a,b,[q,a],R) ... som z toho jelen