Okruh 9 - Gramatiky

[nicki-krizek]

9. - Gramatiky

Autor	Reviewer	Stav
@tomaskrizek		👀

TODO

• Rozhodnout, zda napsat i syntaktickou analýzu.

[nicki-krizek]

Okruh dodělán, čeká na review.

[tomaskounovsky]

Myslím že je chyba v příkladech přepisovacích pravidel - by smazalo/přepsalo terminál , což je nepřípustné. Předpokládám, že to je překlep a má to být .

[tomaskounovsky]

"Důležité je si uvědomit, že regulární gramatika je zároveň i bezkontextová, kontextová i typu 0. Stejně tak třeba kontexová gramatika je zároveň i typu 0. Všechny gramatiky jsou tím pádem typu 0."
Tohle budu asi potřebovat v pondělí vysvětlit, protože takhle mi to zní jakože všechny gramatiky jsou typu 0, což znamená že mají neomezená přepisovací pravidla, což samozřejmě nemůže být pravda. V sešitě se řeší něco jako vlastní podtřída a že jazyk regulární je vlastní podtřídou jazyka typu 0, ale takhle mi to smysl moc nedává.

[nicki-krizek]

Prirovnam to k cislnym mnozinam.

Komplexni cisla - a + bi; analogie typu 0
Realna cisla - omezeni, ze b == 0; analogie kontextovych j.
Cela cisla - omezeni, ze a musi byt cele cislo; analogie bezkontextovych
Prirozena cisla - omezeni, ze a musi byt kladne cele cislo; analogie regularnich

Prirozena cisla maji nejvice striktni podminky a diky tomu splnuji i podminky pro cela cisla, realna cisla i komplexni cisla.

Stejne tak regularni jazyk diky tomu, ze ma nejvice striktni pravidla, tak je zaroven i jazykem bezkontextovym, kontextovym i typu 0.

To, ze gramatiky typu 0 maji nejobecnejsi pravidla neznamena, ze ta pravidla musi byt pouzita v jejich nejobecnejsi forme. Naopak diky tomu, ze jsou pravidla naprosto obecna, tak je splnuji i velice specificka pravidla jako pouzivaji treba regularni gramatiky.

[johnymachine]

Co rozpozná Kontextovou gramatiku, existuje něco takového? Je to tak že to pozná vše směrem dovnitř že jo?

Jako TS pozná regulární

[tomaskounovsky]

Chápu, že přepisovací pravidlo regulární gramatiky bude zároveň přepisovacím pravidlem typu 0 (a opačně to tak být nemusí). Pořád mi ale přijde špatné říct "všechny gramatiky dokážou rozpoznat/generovat nějakou podmnožinu jazyka typu 0, tudíž všechny gramatiky jsou typu 0" (tohle mi přijde že vyznívá z poslední části té věty, kterou jsem citoval). Všechny gramatiky přeci nemohou být typu 0, to by pak nemusela existovat celá Chomského hierarchie.

[nicki-krizek]

@johnymachine Presne tak, TS pozna vsechno. To je prave plyne z toho, ze vsechny gramatiky jsou typu 0. Funguje to "smerem dovnitr", jak rikas.

@tomaskounovsky "Vsechny gramatiky jsou typu 0." je ok. Resili jsme to tenhle semestr v prekladacich s Lenkou KT a ta tohle taky rikala. Smysl Chomskeho hierarchie je v tom, ze nektere gramatiky jsou jeste navic necim lepsim. A pak uz se zminuje jen to nejlepsi, protoze nam to umozni to implementovat co nejjednoduseji. Kdyz budu mit regularni gramatiku, staci mi pouzit na jeji rozpoznani konecny automat. Nicmene jelikoz je to zaroven i gramatika typu 0, muzu si na to klidne pouzit TS.

Je to fakt stejne jako s temi cisly. 1 je prirozene cislo. To ovsem nic nemeni na tom, ze je to zaroven i cele cislo, realne cislo i komplexni cislo. Kdyz v mnozine komplexnich cisel prohlasim, ze vsechna cisla jsou komplexni, je to pravda. I pres to, ze mnozina komplexnich cisel obsahuje treba cisla prirozena, se kterymi muzu pracovat jednoduseji. Proto pokud budu mit nejake prirozene cislo, spis o nem prohlasim, ze je prirozene, nez abych rekl, ze je komplexni (coz je ale taky pravda).

[tomaskounovsky]

Ok, už to asi chápu. Já se na to díval z pohledu "je to typ 0, tzn. rozpoznají to jenom nejsilnější stroje - TS, PS a KSZ2+". jenom je ta chyba. Platí spíš "Je to typ 0, tzn. můžu to rozpoznat TS. Ale pokud je to zároveň typ 3, tak na to můžu použít KA".

[tomaskounovsky]

Sorry že pořád prudím, ale jak to je tedy s tím přepisovacím pravidlem ?

edit: aha, podle definice hned nad tím to je platné pravidlo

[nicki-krizek]

Je to takove zvlastni pravidlo, ale podle obecne definice by melo byt mozne ho pouzit. Myslim, ze jsem zrovna tyhle pravidla odnekud prebiral (asi z wiki).