Sent: 28. júna 2000 13:52 To: 8inf Subject: foja 26.6. 1. dvojsmerny nedeterministicky konecny automat, ktory moze pouzit na oznacenie pismena jeden (dva) zeton(y) - toto tu uz bolo a celkove to nie je tazke (kedze som to mal dobre :) 2. veta o zrychleni pre TS - je treba dost dobre vediet, ako ten TS A' pracuje, moje predstavy boli v niektorych bodoch dost hmliste, a prave na tie body sa Rovan bez vahania pytal :) ale inak pohoda, mam pocit, ze uz dava znamky dost lacno David p.s.: mne sa zda vzdy ten konstrucny pripad lahsi, hmmm Sent: 26. júna 2000 13:12 Subject: foja Moje otazky zo skusky: 1- Defin ujte viacpaskovy TS, ktory ma jednu vstupnu pasku na ktoru nemoze zapisovat a k pracovnych pasok s tym, ze na i-tej paske moze pracovat len ak su vsetky i+1 az k pasky prazdne. Moze zapisovat B. Urcit silu. 2- Je rozhodnutelny problem dosiahnutelnosti stavu v zasobnikovom automate? (ano) Sent: 26. júna 2000 13:52 Subject: Foja 26.6.2000 Date: Mon, 26 Jun 2000 13:51:30 +0200 Subject: Foja 26.6.2000 Cavte, tak konecne to uz mam za sebou a mam prazdniny, kuwa len netusim preco som tak dlho sral na ucenie :) No dobre tu su tie trivialitky : 1. Pumpovacka pre linarne jazyky - k tomu ma musel trosku dotlacit - inak ide o to, ze slova sa budu pumpovat len na krajoch. 2. Uzavretost na komplment u jazykov chomskeho hierarchie. to zvladne hadam, kazdy ... Dufam, ze tento mail je este niekomu na nieco, ale asi nie lebo tieto otazky sa uz tu vyskytli, cize je dobre is pred skuskou pozriet maily naozaj tie otazky nemeni... Tak caute a prijemne prazdniny ... Sent: 24. júna 2000 20:27 Subject: foja nazdar lidi na fojacikoch som mal dvojsmerny dvojhlavovy KA co vie zistit ze ma hlavy na tej istej pozicii zadefinovat a skumat triedu jazykov a potom este pumpovaciu lemu pre bezkontextove jazyky. tot fsio. Sent: 19. júna 2000 16:01 To: 8inf Subject: foja 16.6. + novy termin je 26.6. btw: Rovan vypisal novy termin , a to pondelok 26.6., 8:30, tak ti, ktorym to vyhovuje, sa zapiste moje otazky: 1. 4 definicie det. kon. automatu, co ma na vstupe maticu, sila, atd. 2. dolne ohranicenie pre cas automatu akceptujuceho jazyk L= wcw ad1: kludne dovolte hlave hybat sa hore, dole, dolava, doprava po matici (ja som dovolil len doprava a potom na zac. dalsieho riadku, silu to ma rovnaku) mnou definovany DTMA zvladal rozlisit nulovu maticu, ale uz nie jednotkovu (to by chcelo counter, alebo zasobnik), ani regularnu blabla, nebolo mi celkom jasne, co odo mna chce, ale asi to bolo vcelku ono ad2: tak tu som si vobec nenastudoval ako sa to robi, a preto som to dokazoval dost z brucha, co sa vsak istej osobe vobec nepacilo :) to ohranicenie je tusim T(n^2) potom mi zacal vyvetlovat, ako riesit ten 2., ale moc som sa nechytal, a poslal ma na dalsi termin (ponaucenie: ucte sa aspon tak, aby ste sa chytali :))) David Sent: 16. júna 2000 22:01 Subject: FOJA 16.6.2000 Xaffa Dneska sme boli s Palom Babelom na FOJAkoch ... vytiahli sme si toto: Ja: 1) Definuj konecny teplomerovy automat - praobycajny konecny automat, ktory ma este navyse teplomer, ktory moze v kazdom kroku odvodenia zmenit o +1,0 alebo -1 . Automat pocas typoctu nevidi, aka je momentalna hodnota teplomeru. Akceptuje len ak je po docitani vstupu v akceptacnom stave a teplomer ma hodnotu 0. Kusok sa este pytal na silu tohto cuda ... nakoniec zaziaril usmevom, ze takyto automat si vymyslel sam vcera len tak z nudy :) Tak isto, ked som mu isiel ukazat dokaz, ze je trieda tymto strojcekom akcepovanych jazykov je uzavreta na zretazenie, tiez sa figliarsky usmial, ze na toto je zvedavy a rad si to pozrie ... nasiel mi tam chybu a vyjadril hypotezu, ze to nie je na zretazenie uzavrete :) Tak mi treba, nemal som byt hyperaktivny po studijnej noci ... 2) Redukcia TS k -> 1 pasku pre priestor Palo: 1) Definuj dvojsmerny zasobnikovy automat + nejake haluzky o sile ... 2) Dokaz, ze Lecs je prava podmnozina Lre Staci si vybrat dobre otazky a pohoda. _______________________ Martin Kovacik alias Georgi phone: +421 905 399 320 Pripijam na slnko, ktore vyzlieka baby do plaviek a na chalanov, ktori toho dokazu este viac ... Sent: 15. júna 2000 13:40 Subject: FOJA 15.6. Ahoj, Pripajam sa s otazkami, ktore boli na mojom papieriku: 1.) Zadefinovat viacpaskovy TS s jednou samostatnou vstupnou paskou (nemozno ju prepisovat), pricom ak automat chce pouzivat i-tu pasku, tak vsetky pasky s indexami viac ako i musia byt prazdne (max. na nich mozu byt blanky, t.j. TS moze zapisovat B). 2.) Rozhodnutelnost problemu dosiahnutelnosti stavu pre zasobnikove automaty. (t.j. pre konkretny automat a vybrany stav, ci ex. vstup ze automat prejde tymto stavom). Boris Sent: 15. júna 2000 12:53 Subject: FOJA 15.6 Cafte, toto bol jeden z papierikov: 1. Definuj zasobnikovy automat s operaciou reverz na zasobniku. Co sa stane, ak nebude moct robit epsilon prechody. Aku ma silu (ekvivalentne s turingovym strojom) 2. Polozkovy automat. Co je to za cudo, naco nam je dobre, ako to konstruujeme, ako to funguje... a ci to nekuse... ;) Laco Sent: 15. júna 2000 12:14 Subject: Foja - 15.6.2000 Ahojte, mal som tieto otazky: 1: Definovat dvojhlavy dvojsmerny konecny automat, kde jedna hlava moze citat len policko konc. znakov. Porovnat silu. 2: Ogdenova lema pre triedu bezk. jaz. Sent: 9. júna 2000 0:11 Subject: foja tusim 7.6 no rovan ma v oblube metalinearne jazyky, takze dava uzavretot, silu a tak a mne tresol ze vymysliet pumpovaciu lemu pre metalinearne jazyky cim by sa dalo dokazat, ze nejaky jazyk nie je metalinearny ci co su to nejake take, ze sigma->humus, uplne hocico a potom neterminaly idu na take cosi kde je len jeden neterminal alebo iba same terminaly je to v pohode ide tam o to , ze sa tam da najst len konecne vela miest de sa to da pumpovat, ccc a druhe som mal CYK a pouzitie v syntaktickej anallyze holt vela zdaru, aj ked myslim, ze ked trafite otazky tak pohoda Sent: 8. júna 2000 23:37 Subject: FOJA 08.06.2000 Cafte sa :) No teda dva Rovanove papieriky vyzerali takto: Z piatich papierikov ten stredny: 1. Jazyk platnych vypoctov pre TS A. 2. Konecne automaty pre nekonecne slova. Zadefinuj. Co by mohli a co by nemohli (ktore jazyky) akceptovat. Napr: slovo bude akceptovane, ak vypocet na nom prejde nekonecnekrat cez akceptacny stav. .. Zo styroch druhy zlava: 1. Rozhodnutelnost problemu =Sigma* pre R, Lcf. 2. Definuj nejaky specialny tvar bezkontextovych gramatik s navestiami. Kazde pravidlo ma navestie(cislo) atd. Aku ma silu tato trieda jazykov. Sent: 8. júna 2000 18:44 Subject: foja zdravim, moje otazky z foje 7.6.2000: 1:myhill-nerode veta 2:maticove gramatiky - vymyslat co sa da (nieco som vymyslel, ale nie to co presne chcel, potom sme sa bavili o tom co chcel) kila Sent: 8. júna 2000 13:55 Subject: Foja 8.6.2000 Takze ideme na to : 1. Definovat modifikovany zasobnikovy automat, ktory sa moze ponorit hlavou do zasobnika ale nemoze v nom nic menit. Menit moze iba ked je navrchu. Sila. Uzavretost. - pozor na pouzitie prir. cisla ako index hlavy v zasobniku ten index je spravny ale nie v delta funkcii, iba v konf. 2. Uzavretost tried (R,Lcf,Lcs,Lre) na homomorfizmus. - odpovede su v poradi Ano,Ano,Nie,Ano dokazy simulovanim > Ja som t pobabral s tym indexom, a pre Lcs som to nevedel vysledok 2-. Johny Sent: 8. júna 2000 12:54 Subject: Foja 8.6.2000 Ahoj Ludkovia Mal som tieto otazky: 1) - nejaka neznama gramatika, vymysliet jej definiciu, a nieco o nej, uzavretost, kde je asi v hierarchii a podobne. (Rovan poda vysvetlenie ze co chce). 2) - konstatne zrychlovanie DTS. Nech sa dari. Palo Sent: 8. júna 2000 11:24 Subject: FOJA 7.6 ...hmm trocha neskoro ale predsa :) ja som mal : 1.) ekviv. NKA a KA 2.) Definujte grafovu gramatiku. tu som nieco vymyslel, ale generovalo to len konecne grafy, a to je moc trivialna trieda grafov, takze sa ma skoro nemal co opytat. inak na testovanie definicie gramatiky je vraj dobre zistit, ci gramatika je schopna generovat napr. nekonecne kompletne grafy, alebo nekonecne grafy take, ze kazdy vrchol bude mat urcity stupen (take mriezky). co si spominam, on mi potom navrhoval take riesenie, ze vo vrcholoch grafu su bud terminalne alebo neterminalne symboly, a iba neterminaly sa mozu prepisovat na dalsie grafy. ok...to je vsetko PS: ti co sa este na fojaky len chystate, pozrite si tie otazky ludi, co uz boli, lebo podla mna tie karticky moc nemeni, a ak aj ano, tak je velmi pravdepodobne, ze si vytiahnete otazku co uz bola Sent: 29. mája 2000 15:55 Subject: FOJA - min. roky niekto to po me chcel, tak tu to mate vsetci .. Subj: FOJA 17.6. 2 otazky: - klasika: Redukcia k-paskoveho DTS na 2-paskovy pre cas - novinka: - Zadefinovat "dvojsmerne nedeterministicke konecnestavove prekladace" - Obraz jazyka L takymto prekladacom - Porovnat s a-prekladacmi ( je to silnejsie ako a-prekladace, lebo to dokaze prerobit regularny jazyk na neregularny, napr a^n -> a^n.b^n.c^c ) je to pohoda (Rovan bol trochu vyvedeny z miery, ked zistil, ze namiesto planovanych 20 ludi prislo iba 8... Lubeno Subj: foja 27.5. Posielam informaciu o skuske z Foja 27.5.1999 Na uvod by som chcel povedat, ze to nie je az take zle, ako sa mnohi (aj my) obavaju, doc.Rovan je vcelku prijemny clovek, aj ked niekedy do niekoho rype, vzdy to robi s usmevom. Takze priklady: Ja 1. Veta o zrychleni. (chcel aby som ju vyslovil a prerozpraval dokaz aj s odvodenim casovych vztahov, co bolo trochu neprijemne, davajte si pozor na predpoklady). 2. 2-smerny konecny automat (nedeterministicky, ale povedal, ze ak chcem moze byt aj deterministicky), ktory na rozdiel od bezneho automatu ma 1 (2) zeton(y), ktore moze na pasku davat (zapisovat), a citat (nic ine zapisovat nemoze, a moze zapisat len prave 1 (2) zetony. Chcel odo mna vsetky 4 definicie (automatu, konfiguracie (napr. s bicikmi), kroku odvodenia, jazyka akceptovaneho automatom). Treba nejako vyriesit problem prepisovania znaku, kam davam zeton (napriklad zdvojenou abecedou - povodna sigma + sigma so zetonmi). A klasicky chcel aby som vyslovil nejake zavery o sile tohoto stroja. Dosiel som k tomu, ze jeden zeton je tam aj tak na...(nic), pretoze, ak ho aj na nejake miesto zapiseme, nevieme sa vratit na inu poziciu na paske (nemame si tuto informaciu kde uchovat), takze je to tak silne ako trieda R. Situacia sa ale zmeni ak pridame dalsi zeton (ten nam prave pomoze s tym pamatanim pozicie. Takymto strojom sa daju robit slova ww, wwR, ale aj zistovat napr. polovica slova (jeden posuvam o jedno, druhy o dve policka, ked je druhy na konci, je prvy v strede slova). Ale napriklad to nedokaze robit uplne uzatvorkovane vyrazy, takze na bezkontextove jazyky to nema (neporovnatelne, lebo dokaze ww). Vysledok: 2 (nestihol som projekt) Sonka: 1. Szelepczenyi (chcel hlavne princip, preco to vlastne funguje) 2. Modifikovana pumpovacia lema - tento priklad si ale nepamatam, mozno ho Sonka posle neskor sama, vraj bol dost tazky Subj: foja 27.5. 1. Dvojsmerny nedeterministicky stavovy prekladac. Definicia a porovnanie s a-prekladacom. Dvojsmerny prekladac nezachovava regularnost ani bezkontextovost jazyka. Vie zobrazit jazyk a^n na jazyky a^n b^n, pripadne a^n b^n c^n (viac prechodov po paske a pri kazdom vypisuje ine pismeno) 2. casova zlozitost a redukcia k->2 pasky. Subj: foja 27.5 1. konecne automaty pracujuce na nekonecnych vstupnych slovach - def, jazyk akceptovany takym automatom 2. normalne tvary pre bezkontextove jazyky(redukovana gramatika) Subj: Foja 27.5. 1. uzavretost metalinearnych jazykov (to uz tu myslim bolo) 2. ekvivalencia DTS a NTS --- metalinearne jazyky su lcf jazyky, pre ktore a sigma nevyskytuje na pravej strane pravidiel, a vsetky pravidla okrem pravidiel sigma->xxxx su linearne(max 1. meterminal). uzavrete na: zjednotenie, retazenie, homomorfizmus(ak v pravidlach zobrazime terminaly cez h dostaneme patricnu gr.), prienik s R (zevraj cez konstrukciu pomocou lcf gramatiky a kon. aut.) neuzavrete: prienik(a^n.b^n.c^k je metalin.), komplement(deMorgan) Date: Fri, 21 May 1999 11:23:59 MET Ahojte Tazke moje foja: 1. PKP, teda konkretne som povedal PKP, MPKP a ich ekvivalenciu vzhladom na rozhodnutelnost. 2. Zasobnikovy automat, ale dole je z0, ktore sa nemoze vybrat a nad neho sa moze ukladat iba jediny druh symbolu (napr. palicky) Uzaverove vlastnosti tohoto cuda.. CaV Subj: FOJA 20.5. Nazdar spoluziaci! Tu su moje otazky z FOJA: 1. Def. rozsirene a-prekladace: vstupna paska je dvojsmerna. Premyslajte o uzavretosti standardnych tried na zobraz. 2. Algoritmus CYK. (uplne v pohode...) Inak Rovan bol OK, len sa stazoval, ze ludia nerobia projekty. Takze vrele doporucenie: Urobte projekt, trochu sa poucte a mate to v pohode za jedna.... Subj: foja 20051999 (20.5.1999) ahojte vsetci rovan je fasa chalan... otazky: 1) Greibachovej hormonalny stav (tvar) 2) Zasobnikove Prekladace - definicie + uzavretost tried na zobrazenie tym shitom. dnesny priemer (nechcem krivdit) jednotky - 1 kus dvojky - vela kusov (aj ja) trojky - asi 2 vyletelo - 0 kusov Caute.. Takze fojaky prebiehali v pohode, Rovan je total fasa.. Ak pisete projekt, tak ho piste formalne (mal dost pripomienky k formulaciam obsahujucim :-) alebo napr. formulacia "je zdesenemu citatelovi nejasne..." atd.. Myslim, ze viete, na co narazam, tak si dajte pozor.. Otazky: 1.) uzaverove vlastnosti pre L_{CS} s dorazom na komplement (Szelepcenyiho veta) 2.) vymyslacia otazka - zadefinovat casovu a priestorovu zlozitost nie pre TS ale pre frazove gramatiky + porovnanie tried podla vami def. zlozitosti pre gramatiky z triedami zlozitosti pre TS... no, tam sa da vymysliet kopec veci...... Subj: FOJA, 20.05.1999 Zdravicko damy a pani, takze boli dnes fojaciky a zatial (po 5 ludoch) to vyzera na nejake tie dvojky vacsinou. Inak pohoda. S Rovanom sa iste dobre porozpravate o prijemnych veciach. Takze co som mal... 1.-> Cerveno-zelene bezkontextove gramatiky. Zelene pravidla su obycajne a cervena pravidla maju tu vlastnost, ze ked uz nejake cervene pravidlo vo vypocte pouzijeme, tak toto pravidlo musi byt v tomto kroku pouzite na vsetky neterminaly (pre ktore sa toto pravidlo pouzit da) v aktualnej vetnej forme. Treba sa zamerat na uzaverove vlastnosti. (finta: skuste sa pozriet na jazyk n n n n n n a b a c a a jazyk a b c pripadne jeho komplement.) 2.-> Vypoctova zlozitost TS. Definovat zlozitost, nejaky vztah s jazykmi, redukcia k-paskoveho automatu na 1-paskovy. Zamerat sa na konstrukciu a zmenu casovej zlozitosti. nowo. Sorry za chybu v texte. Treba za pozriet na jazyky n n n n n n a b c a a b a c a nowo. Sorry... Subj: foja 13.5 1.nerozhodnutelnost cf gramatik 2.ten fifo automat (s epsilonmi aj bez) Subject: foja suska 13.5 cafte ja som mal: 1.CYK a pouvazovat preco Comskeho norm tvar, co ked nie je v chomskom,... 2. zadefinuj zasobnikovy automat, pri4om zapisovat moze iba jeden znak, navyse sa moze po zasobniku pohybovat ako chce, ale pritom moze zapisovat (a mazat iba na konci) Pozn. s NZA je neporovnatelny (bo dokaze a^i b^i c^i, ale nie w#w^R),... p.s. rovan je celkom fasa, asi mu dam do hodnotenia iba 11111 Subj: foja 13.5 Drahi priatelia, pripajam aj svoje ulohy, hinty a postrehy: 1 Zasobnikovy automat s takou zmenou, ze delta funkcia sa kdesi moze rozhodnut, ze zmeni stav a cely na zasobnik aplikuje dany homomorfizmus. Tento homomorfizmus je pre dany nas zas.automat jeden a je taky specialny, ze je z Gama do Gama, t.j. nevymazavaci a na ziadne pismeno nevracajuci slovo dlhsie jak jedna, cize funguje pismenko na pismenko. Da sa ukazat, ze sila tohto monstra neni vacsia ako sila NPDA, lebo aplikovanie homomorfizmu si mozme na zasobniku oznacit pridanim symbolu h. Homomorfizmov z Gama do Gama je konecne vela, presne ich je Gama^Gama, takze v druhej zlozke stavu si mozeme pamatat, ze ktory homomorfizmus je aktualny... 2 Ako to vyzera s redukciou k pasok na jednu pasku pre priestor a pre cas. Mal som napisane aj dokaz ze ziadny det. jednopaskovy TS nedokaze akceptovat wwR v case lepsom jak n^2, ale na to sa ani nepozrel. Subj: Skuska Foja Takze som dostal 1. Dokazat ekvivalenciu nasej definicie CS jazykov a definice podla chomskeho (taka strasne stara definicia, ktoru spominal na zaciatku ; s pravidlami uNv -> uXv kde N je neterminal a X je nejake neprazdne slovo z (N U T)* 2. Uzaverove vlastnosti Lcs s dorazom na Inverzny homomorfizmus Tak ako ZoRRo aj ja som nemal projekt, takze som dostal za dva. V podstate ma stopol este pred koncom mojho vykladu s tym, ze je vidno, ze to viem, takze staci sa nepomylit a on vam to da hned ;-))) Subj: foja 13.5 Cafte 1.NKAZ s prezeratelnym zasobnikom- form. def. +sila 2.Redukcia pasok z k na 2 pre cas. Bol kludas, v pohode, ziadne podrazy... ale nemal som projekt, tak za 2... inak by mi vraj xcel dat 1... Subj: foja 6.5 Tos dostal sem totok: 1. cerveno zelene pravidla... vid mail ktory sme raz dostali 2. CF G -> Zas. automatu inac bolo aj LBA -> CS G Subj: foja 13.5. Takze: 1. Zadefinuj dvojhlavovy jednosmerny zasobnikovy automat a porovnaj silu 2. Ogdenova lema Subj: foja - skuska 1.) Vymysliet a zadefinovat gramatiky nie na slovach (retazcoch) ale na grafoch. Pravidla maju tvar g1 -> g2, kde g1,g2 su grafy. A vsetko mozne okolo toho. Ludova tvorivost. A este taketo bezkontextove gramatiky. 2.) Greibachovej normalny tvar. Zda sa mi, ze definovat nove veci dava stale 2 ludom a potom porovnava, kto to ako robil. Ale mozno nie. Giro ---- Date: Tue, 19 May 1998 14:46:11 MET Subject: Foja 19.5. Takze zatial nikto nevyletel, 2x trojka, raz dvojka a zvysok jednotky (este su tam piati). 1.Dvojpaskovy konecny automat, porovnat silu s a-prekladacom, uvazujeme, ze na 1.paske je 1.slovo a na 2.paske je slovo, ktore by spravil a-prekladac ;)))) (sh*t) 2.Je normalovou formou L_CS gramatika, co ma najviac 2 symboly na lavej i pravej strane pravidiel? 6Kreten --- Date: Tue, 19 May 1998 13:15:06 MET Subject: foja 19.5 1. automaty ako zasobnikove, lenze s FIFO 2. Rice-ova veta a rekurzivnych mn. ind. (ta prva - vsetko je nedokazatelne) Drzte sa, Peter. ---- Date: Tue, 19 May 1998 10:50:31 MET Subject: Fojaky 19.5. Cafte ! Rovan dal tradicne jednu vec z prednasok, jednu vec vymysliet. Ja som mal: 1.) Gramatiky ako L_CF, ale pravidla su podelene do skupin a v skupinach zoradene, takze ked sa odvodzuje, pouzije sa lubovolna skupina. Ked sa pouzije lubovolna skupina, musia sa postupne (v danom poradi) pouzit vsetky jej pravidla, az potom sa ide dalej. sila, porovnat s L_CF, uzaverove vlastnosti (necaka ze stihnes vsetko). Je to silnejsie ako L_CF, vie to a^ib^ic^i, a je to aspon take silne, lebo kazde G z L_CF sa da prepisat na tuto triedu. 2.) LR(0). Tvaril sa, ze by k LR(0) este nieco dal na siet, kedze sa v tejto oblasti na skuske nepodavaju nejake moc velke vykony :-) Tomas ---- Date: Wed, 13 May 1998 09:02:38 MET Subject: foja, 12.5 Ja som mala: 1. Cocke - Young - Kassami algoritmus 2. Bezkontextova gramatika, ak mame v odvodeni vetnu formu, ktora obsahuje viackrat ten isty neterminal A, v jednom kroku odvodenia sa musia vsetky A rozpisat podla toho isteho pravidla. Zadefinovat, porovnat s L_CF (triedy su neporovnatelne, napr. ww patri do novej triedy ale nepatri do L_CF, dobre uzatvorkovane vyrazy su z L_CF, ale nepatria do novej triedy). Caute a vela stastia na fojakoch Eva. ---- Date: Tue, 12 May 1998 12:13:54 MET Subject: foja 12-MAY-98 Forma skusocky: Ziadne priklady, len dve otazky, jedna na vec z prednasok, jedna na vymyslenie nejakej novej masiny/gramatiky-sila,vlastnosti. Priblizne tristvrtehodina na pripravu, nevyzaduje ziadne kvanta popisaneho papiera, skor vedie priatelsku debatu o otazkach. Hodnoti zavaznost chyb. moje otazky: 1. Mame bezkontextovu gramatiku, kt. okrem klasickych(cervenych) ma este zelene pravidla, kt. maju tu vlastnost, ze v jednom kroku sa musi pravidlo pouzit na vsetky neterminaly ( ak N -> a,b tak uNvNw -> uavaw alebo ubvbw ale nie na uavbw ) povedzte nieco o sile a vlastnostiach takychto gramatik. 2. Casova zlozitost TS, veta o redukcii poctu pasok na 2 v case T(n) log T(n) ucast: 5 kusov priemer: doteraz 1.25 ---- Date: Tue, 12 May 1998 12:38:28 MET moje otazky z FoJa: 1. LR(0) gramatiky 2. zadefinovat gramatiky, co neobsahuju neterminaly ani terminaly, len obycajne symboly, pricom sa v odvodeni musi kazdy symbol prepisat (teda ak existuje na neho pravidlo). Do jazyka potom patri kazda vetna forma. def., silu, uzaverove vlastnosti, porovnat s Lcf. Tot vsjo. Aron ---- Subject: Foja 26.5.1998 Date: Tue, 26 May 1998 18:22:36 +0000 (GMT) Caute ludia! Ja som mal: 1. Greibachovej norm tvar 2. Automat ktory namiesto zasobnika ma FIFO. Porozmyslat o tom co to bude, ked to bude mat prechody \epsilon a ked to taketo prechody mat nebude. Ked to nebude mat prechody je to neporovnatelne s Lcf. ww - sa sa urobit pomouf FIFO s neda sa pomocou Stacku ww^r - sa da pomocou Stacku a neda sa cez FIFO. Ked sa vsak pridaju prechody na \epsilon, cuduj sa svete je to ekivvaletne s TS, z nasledovneho dovodu. Pomocou FIFa sa bude simulovat paska TS. Na \epsilon mozete v pohode tocit paskou kolko chcete a teda sa mozete dostat na lub. miesto pasky. Pojem tocit je mysleny = na esp. vyberiem z FIFA znak a dam ho na koniec FIFa a tak potupujem podla toho co chcem. Mirec ---- Date: Tue, 26 May 1998 16:26:44 MET Subject: foja 26.5. Zdravim moje priklady na skuske: 1. bezkontextove gramatiky s navestiami (G=(N,T,P,sigma,R) kde R je regularny jazyk), t.j. kazde pravidlo ma navestie (povedzme prirodzene cislo); slovo sa odvodi klasicky bezkontextovo, ale zaroven zretazenie navesti (labelov) pouzitych pravidiel musi patrit do daneho regularneho jazyka R; treba to porovnat s CFG, urcit silu, uzaverove vlastnosti 2. nerozhodnutelne problemy pre L_cf (hlavne treba vediet sposob, akym sa tieto dokazy robia) -- boro ---- Subject: Foja 26.5.1998 Date: Tue, 26 May 1998 14:35:11 +0000 (GMT) Caff Lidi. 1.Uloha Zasobnikove automaty s prezeratelnym zasobnikom -zovseobecnenie zasobnikovych automatov -sila -model -uzaverove vlastnosti 2.Uloha Majme nasledovnu podtriedu kontextovych gramatik Vsetky pravidla maju na lavo a napravo najviac dva symboly. Otazka ci je to Normalny tvar. Odpoved ... Je. Som to obisiel cez LBA, co sice nevonalo nejako ale bolo to dobre... Neviem ale dostal som otazky , ktore velmi na prednaske neboli . Nandi ---- Date: Tue, 26 May 1998 13:49:48 MET Subject: foja 26.5 1/ casova zlozitost, redukcia pasok k-->2 v T(n)logT(n) 2/ Metalinearne gramatika - linearna gramatika (napravo kazdeho pravidla max. jeden neterminal) pricom pre pociatocny neterm. S obmedzenie linearnosti neplati. S nikde nieje na pravej strane. [sila,uzavr] R < Lml < Lcf .dg. ---- Date: Tue, 26 May 1998 13:14:32 MET Subject: foja 26.5 dostal som 1) LBA do CSL 2) vymysliet gramatiky generujuce matice erce ---- Date: Tue, 26 May 1998 12:37:27 MET Subject: FOJA 26.5. Caute.... 1, Algoritmus : Coche , Younger, Kasumi 2, Bezkontextova gramatika s pravidlom odvodenia, ktore nahradzuje vsetky vyskyty,...., uvazujte o jej sile, uzavretosti.... p. --------------------------- WWW: http://www.homepage.sk/hudecof.html PGP: redbull.dcs.fmph.uniba.sk/~hudecp/hudecp.txt MOBIL : zabijem sa ??? nemam Sent: 25. mája 2000 12:58 Subject: Foja 25.5.2000 no ako obvykle su tu dve otazky .. jedna standartna a druha (vymysli si sam) 1. Definovat lave krajne odvodenie pre kontextove jazyky. Je mozne pouzivat len lave krajne odvodenia ??? 2. Ekvivalencia PDA, ktore akceptuju stavom a prazdnym zasobnikom. PS. Skor ako napisete ze je nieco zrejme, skuste sa o tom presvedcit .. Mal som dost problemov aby som ho presvedcil o niecom ze je zrejme .. --------------------------- WWW: http://www.homepage.sk/hudecof.html PGP: redbull.dcs.fmph.uniba.sk/~hudecp/hudecp.txt MOBIL : zabijem sa ??? nemam