Resent-Date: Tue, 27 Apr 1999 16:45:18 MET
Warnings-To: <>
Date: Tue, 27 Apr 1999 16:34:43 MET
Subject: foja - skuska
Lines: 211
Status: RO

Date: Tue, 19 May 1998 15:09:57 MET
Subject: foja 19.5.


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.