abclinuxu.cz AbcLinuxu.cz itbiz.cz ITBiz.cz HDmag.cz HDmag.cz abcprace.cz AbcPráce.cz
AbcLinuxu hledá autory!
Inzerujte na AbcPráce.cz od 950 Kč
Rozšířené hledání
×
včera 22:33 | Komunita

Byly vyhlášeny výsledky letošní volby vedoucího projektu Debian (DPL). Dnešním dnem je novým vedoucím Sam Hartman.

Ladislav Hagara | Komentářů: 0
včera 22:11 | Nová verze

Po čtyřech měsících od vydání verze 5.5 byla vydána verze 5.6 svobodného multiplatformního softwaru pro konverzi a zpracování digitálních fotografií primárně ve formátů RAW RawTherapee (Wikipedie). Nová verze RawTherapee je k dispozici také jako balíček ve formátu AppImage. Stačí jej stáhnout, nastavit právo ke spuštění a spustit.

Ladislav Hagara | Komentářů: 0
včera 00:22 | Nová verze

Byla vydána verze 1.0 svobodné multiplatformní závodní hry SuperTuxKart (STK). Přehled novinek v příspěvku na blogu. Zdůraznit lze především víceuživatelský mód umožňující hrát hru po síti. Videoprezentace nejnovější verze na YouTube.

Ladislav Hagara | Komentářů: 3
20.4. 15:55 | Komunita

Ke zhlédnutí jsou videozáznamy grafických rozhraní telefonů, zatím jenom vývojových desek, Librem 5 a PinePhone. Librem 5 za 649 dolarů by měl být aktuálně k dispozici ve třetím čtvrtletí 2019. Při spuštění kampaně se mluvilo o lednu 2019. PinePhone za 150 dolarů by měl být odesílán ve čtvrtém čtvrtletí 2019.

Ladislav Hagara | Komentářů: 0
19.4. 20:22 | Nová verze

Po dvou měsících vývoje od vydání verze 6.0.0 byla oficiálně vydána nová verze 6.1.0 správce digitálních fotografií a nově i videí digiKam (digiKam Software Collection, Wikipedie). Přehled novinek i s náhledy v oficiálním oznámení. Vývojáři zdůrazňují nové API pro rozšíření DPlugins nahrazující KIPI. Ke stažení je také balíček ve formátu AppImage. Stačí jej stáhnout, nastavit právo ke spuštění a spustit.

Ladislav Hagara | Komentářů: 0
19.4. 19:55 | Nová verze

Byla vydána verze 1.16.0, tj. první stabilní verze nové řady 1.16, multiplatformního multimediálního frameworku GStreamer (Wikipedie). Z novinek lze zdůraznit vylepšení podpory WebRTC nebo AV1. Podrobnosti v poznámkách k vydání.

Ladislav Hagara | Komentářů: 0
19.4. 11:55 | Nová verze

Po více než 3 letech od vydání verze 1.3.0 byla vydána nová stabilní verze 1.4 multimediálního přehrávače MPlayer (Wikipedie). Nejnovější verze přináší kompatibilitu s verzí 4.1 a také s aktuální vývojovou verzí multiplatformní multimediální knihovny FFmpeg (Wikipedie).

Ladislav Hagara | Komentářů: 15
18.4. 23:55 | Komunita

Mozilla oznámila, že projekt Things byl přejmenován na WebThings. Nové jméno by mělo zdůraznit, že se nejedná pouze o projekt IoT (Internet věcí), ale o WoT (Web věcí). Současně byla vydána WebThings Gateway (GitHub) ve verzi 0.8 pro Raspberry Pi.

Ladislav Hagara | Komentářů: 0
18.4. 21:11 | Nová verze

Byl vydán balík KDE Aplikace ve verzi 19.04. Shrnuje práce za poslední čtyři měsíce: opravy chyb, mj. ve správci souborů Dolphin, prohlížeči dokumentů (nejen PDF) Okular nebo prohlížeči obrázků Gwenview – tyto dostaly např. lepší podporu dotykových obrazovek. Významného přepracování se dočkal editor videa Kdenlive.

Fluttershy, yay! | Komentářů: 3
18.4. 16:22 | Nová verze

Byla vydána verze 19.04 linuxové distribuce Ubuntu a oficiálních odnoží Ubuntu Budgie, Kubuntu, Lubuntu, Ubuntu Kylin, Ubuntu MATE, Ubuntu Studio a Xubuntu. Kódový název Ubuntu 19.04 je Disco Dingo. Přehled novinek a odkazy ke stažení v poznámkách k vydání. Ubuntu 19.04 bude podporováno 9 měsíců, tj. do ledna 2020.

Ladislav Hagara | Komentářů: 10
Používáte headset pro virtuální realitu?
 (1%)
 (3%)
 (1%)
 (19%)
 (0%)
 (75%)
Celkem 218 hlasů
 Komentářů: 12, poslední 18.4. 01:19
Rozcestník

Jazyky a překladače - 1 (úvod)

13. 7. 2006 | Michal Vyskočil | Programování | 17362×

Zdrojový kód je ve světě Open Source (respektive Free Software) velice častým a důležitým pojmem. Tento server se problematikou F/OSS zabývá, a proto není od věci si vysvětlit, co to vlastně zdrojový kód je, co je to programovací jazyk, a jakým způsobem se zpracovává. Upozorňuji, že dnešní díl si užijí především ti, kteří se nebojí matematiky.

Poznámka: Máte-li problém se zobrazováním znaku ∪ (∪), vyzkoušejte fonty DeJavu, které jej obsahují.

Obsah

Co je to jazyk

Jazyk, co to vlastně je jazyk? Základem takového jazyka je abeceda, což je jistá množina znaků specifická pro daný jazyk. Ze znaků abecedy jsou tvořena slova (pochopitelně neuvažujeme pro nás exotické jazyky typu japonštiny). Ty dále spojujeme do vět a to za pomoci gramatických pravidel. A právě gramatika je problémem. Jazyky, které se nazývají přirozené, mají gramatiky velmi složité, plné vyjímek a pro zpracování na počítačích se nehodí. Pokud mi nevěříte, tak se podívejte na diplomovou práci Johanky (ps, 1.0MB) a pokud budete rozumět alespoň slovům v obsahu, můžete se pustit do čtení (já, nemaje humanitní vzdělání, jsem skončil právě na něm). Nebo můžete navštívit přímo stránky Ústavu formální a aplikované lingvistiky na Matematicko fyzikální fakultě Univerzity Karlovy.

Druhou skupinou jazyků jsou formální jazyky. To jsou ty, jejichž pravidla pro generování a pohlcování jsou víceméně jednoduchá a deterministická (jednoznačná). Takové se potom hodí pro zpracování na počítačích. A o nich bude tento článek.

Formální jazyky

Teorie kolem formálních jazyků je rozsáhlá, ale pro potřeby článku se musí poněkud zkrátit. Jak jsem již napsal výše, základem jazyka je abeceda, kterou označujeme jako Σ (velké sigma) a Σ* (iterace), respektive Σ+ (pozitivní iterace) je množina konečných posloupností znaků z abecedy. Ty nazýváme slova na abecedou Σ a označujeme znakem w. Slovo, jehož délka je nulová, značíme e a pozitivní iterace tento znak neobsahuje. Jazyk L je potom podmnožinou množiny Σ*, respektive Σ+.

Ovšem jazyk je nutné nějakým způsobem popsat a právě zde nastupuje další pojem - gramatika. To je to, co známe i z přirozené řeči, a zde nám slouží ke konečnému popisu nekonečného jazyka. Každý formální jazyk tudíž musí mít specifikovanou nějakou gramatiku a při zpracování se mimo jiné ověřuje, zda jí zadaný vstup odpovídá.

Formálně je potom gramatika G čtveřice G=(N, Σ, P, S), kde

  • N je konečná množina nonterminálních symbolů
  • Σ je konečná množina terminálních symbolů
  • P je konečná množina přepisovací pravidel
  • S∈N je výchozí startovací symbol gramatiky

Důležitým pojmem je potom množina přepisovacích pravidel. Jedná se o podmnožinu kartézského součinu (N∪Σ)* N (N∪Σ)* × (N∪Σ)*. Přepisovací pravidlo je potom prvek (α,β)∈P a zapisuje se ve tvaru α→β.

Jazyk generovaný gramatikou je potom definován takto:

Je to množina slov w, které získáme derivacemi ze startovacího symbolu gramatiky. Symbol označuje reflexivní a tranzitivní uzávěr derivace. Pro nematematiky se jedná o postupné textové náhrady symbolů podle přepisovacích pravidel gramatiky. Zároveň musí být splněna podmínka, že slovo patří do množiny Σ*, tedy, že je tvořeno pouze symboly abecedy Σ.

Chomského klasifikace gramatik

Důvody, proč jsem se tolik zabýval gramatikami a jejich formálním vyjádřením, jsou dva. Jednak je gramatika možnost, jak popsat potenciálně nekonečný jazyk konečným způsobem. A navíc tvar přepisovacích pravidel z množiny P umožňuje zařazení jazyka do některé z následujících čtyř tříd.

  • Typ 0 obecné gramatiky
  • Typ 1 kontextové gramatiky
  • Typ 2 bezkontextové gramatiky
  • Typ 3 pravé regulární gramatiky

Přičemž jazyk generovaný gramatikou typu X se nazývá jazyk typu X a množina takových jazyků se značí LX. Platí , což znamená, že množina regulárních jazyků je podmnožinou bezkontextových, ta zase podmnožinou kontextových a to celé je podmnožinou obecných jazyků. Podstatné na této klasifikaci je, že každá z výše uvedených tříd jazyků má jistou výpočetní sílu, přičemž čím vyšší třída, tím nižší síla.

Typ Gramatika Jazyk Stroj
0 obecná rekurzivně vyčíslitelný Turingův stroj
1 kontextová kontextový Lineárně ohraničený TS
2 bezkontextová bezkontextový Zásobníkový automat
3 regulární regulární Konečný automat

Tabulka udává jednotlivé typy gramatik, jazyky, které generuje a také minimální stroj, který dokáže načíst jejich věty. Rozdíl mezi pravou a levou regulární gramatikou je pouze v pozici nonterminálního symbolu B, obecně takové gramatiky nazýváme regulární.

Praktický příklad

Dost již bylo teorie. Představíme si gramatiky v praxi. Mějme gramatiku G:

Příklad tvorby věty jazyka generovaného touto gramatikou:


Na počátku byl startovací symbol gramatiky S. S využitím prvního pravidla jsme získali řetězec xS, další aplikací prvního pravidla jsme dostali xxS. Poté jsme aplikovali pravidlo číslo dvě a získali xxyS a s využitím dalších pravidel jsme nakonec vytvořili výsledné slovo xxyyy. Naše primitivní a jednoduchá gramatika ovšem umí generovat i jiná slova, například y, xy, xyy, xxyy, xxxx...xxxy a tak dále. Pokud se podíváte pozorněji, tak mají daná slova něco společného. Dají se zapsat do regulárního výrazu x*y+, což značí, že na začátku může být žádné až nekonečně mnoho znaků x, které jsou následované alespoň jedním (ale i více) znaky y.

Co jsme to vlastně definovali za gramatiku? Pohledem na výše uvedenou klasifikaci gramatik zjišťujeme následující. První tři pravidla odpovídají prvnímu vzoru pro regulární gramatiky, protože S a A patří do množiny nonterminálních symbolů a x a y do množiny terminálních symbolů. A poslední pravidlo odpovídá třetímu vzoru pro regulární gramatiky. To znamená, že je naše gramatika regulární. Vyjadřovací síla regulárních gramatik, konečných automatů a regulárních výrazů naprosto stejná, proto je možné je navzájem zaměňovat. Nicméně regulární výrazy mají daleko kompaktnější zápis než gramatiky.

Na tomto místě si dovolím poznamenat, že spousta nástrojů svoje regulární výrazy vylepšovala do té míry, že přeskočili až do vyšších jazyků.

Meze regulárních jazyků

Regulární jazyky mají nejmenší vyjadřovací sílu. Ale pro spoustu problémů naprosto stačí a unixové regulární výrazy jsou toho jenom dokladem. Na druhou stranu by bylo vhodné mít něco, co nám pomůže zjistit hranice regulárních gramatik. To něco se nazývá Pumping teorém (česky lemma o vkládání):

Daný vztah říká, že v dostatečně dlouhém slově w, které patří do jistého jazyka, můžeme nalézt tři části — x, y a z, přičemž nejdůležitější část y může zahrnovat i celé slovo. Poslední vztah potom značí, že část y můžeme z jazyka vyjmout, nebo jí libovolně zopakovat, a přitom stále zůstáváme v rámci stejného jazyka.

Díky této větě potom můžeme dokázat, že daný jazyk není regulární. Klasickým učebnicovým příkladem je například jazyk . Definice jazyka hovoří, že generuje stejný počet znaků a i b. Při hledání podřetězce y potom můžeme narazit na následující případy.

  1. {a}+ (samá a) — není hledaný podřetězec, protože jej nemůžeme vynechat, ani ziterovat, protože by se nerovnaly počty znaků
  2. {b}+ (samá b) — stejný případ
  3. {a}+.{b}+ (alespoň jedno a následované alespoň jedním b) — iterace takového podřetězce potom poruší podmínku, že všechny znaky b následují až za znaky a

Protože nedokážeme najít žádný podřetězec y, dokázali jsme, že daný jazyk není regulární. To má i praktický význam, jelikož nemusíme hledat složité regulární výrazy na detekci takových řetězců, protože to prostě nejde. Na druhou stranu dokáží regulární jazyky vyřešit i některé problémy (bez důkazu)

Závěr

Tento díl představoval lehký (velice lehký, zájemce odkazuji na přístupné materiály některých vysokých škol k této problematice) úvod do problematiky formálních jazyků. Tématem příštího dílu by měly být především regulární výrazy (ano i to je formálně podchyceno) a konečné automaty, protože k sobě spolu neodmyslitelně patří. Myslím, že na unixově založeném serveru se bude jednat o vděčné téma.

Toto je tak trochu experiment, protože se vymyká běžným tématům na ábíčku. Navíc obsahuje dost formálních náležitostí, a proto potřebuji vědět, jak se na to díváte po přečtení. Mám přidat, nebo raději ubrat? Těším se na vaše názory a na případné opravy chyb, které jsem napáchal.

       

Hodnocení: 73 %

        špatnédobré        

Nástroje: Tisk bez diskuse

Tiskni Sdílej: Linkuj Jaggni to Vybrali.sme.sk Google Del.icio.us Facebook

Komentáře

Vložit další komentář

13.7.2006 00:17 Kyosuke | skóre: 28 | blog: nalady_v_modre
Rozbalit Rozbalit vše Japonština
A proč bychom pro formální účely nemohli znaky katakany, hiragany a kanji považovat za znaky abecední? Kde je problém? ;-)
13.7.2006 00:48 xkesh | skóre: 46 | blog: eXtempore
Rozbalit Rozbalit vše Re: Japonština
Základem takového jazyka je abeceda, což je jistá množina znaků specifická pro daný jazyk. Ze znaků abecedy jsou tvořena slova

Ono i tohle je více než podivné, neboť základem jazyka rozhodně není abeceda neboli znaky označující skupiny hlásek a už vůbec není taková abeceda "specifická" pro daný jazyk, ale naopak v zásadě univerzální (jak již vyplývá přímo z podstaty "abecedy"). Slova také nejsou tvořena "ze znaků abecedy", maximálně se dají foneticky na hlásky, které se opět dají zapsat znaky abecedy.

Pro jazyk vůbec není podstatné, jakou abecedou je zaznamenán (ostatně díky tomu dnes píšeme abecedou "latinskou", která vznikla z abecedy "řecké" kterážto opět z "fénické", specifických to jazyků s de facto jednou univerzální abecedou).

Ale jelikož to má být jen takový jakoby vtipný úvod, tak myslím není třeba těm prvním větám věnovat pozornost. Raději (vzhledem k obsahu, který následuje a je na rozdíl od nich přínosný či alespoň poučný). ;)
13.7.2006 01:01 Kyosuke | skóre: 28 | blog: nalady_v_modre
Rozbalit Rozbalit vše Re: Japonština
A proč by abeceda (přirozeného jazyka) musela být univerzální? Jak může abeceda být jakkoliv univerzální? Nota bene prý z nějaké „podstaty“?

(Jinak samozřejmě chápu, že jayky a gramatiky počítačové za jeden za základů abecedu v podstatě mají, stejně jako v teorii informace je pojem „abeceda“ celkem běžně používaný s konkrétním významem.)
13.7.2006 01:23 xkesh | skóre: 46 | blog: eXtempore
Rozbalit Rozbalit vše Re: Japonština
A proč by abeceda (přirozeného jazyka) musela být univerzální? Jak může abeceda být jakkoliv univerzální? Nota bene prý z nějaké „podstaty“?
Protože něco jako "abeceda jazyka" neexistuje. Existují různé abecedy, kterými se zapisují různé jazyky. Abeceda jako způsob označování jednotlivých hlásek či skupin hlásek, na která se dají rozložit jednotlivá slova, je univerzální proto, že vůbec není podstatné, jaký jazyk nějakou abecedou zapíšete.

Ostatně většina nynějších kulturních jazyků používá více či méně upravenou tutéž abecedu (latinka, azbuka, řecké písmo, hebrejské, arabské, syrské písmo...), pouze v různém stádiu vývoje, a dá se poměrně dobře vystopovat, jak se nynější rozdílné znaky vyvíjely jeden z druhého. Japonská abeceda vznikla zase podobně zjednodušením čínských znaků, ale i tak je univerzální, protože na rozdíl od čínských logogramů se řídí výše popsaným principem abecedy, přiřazení znaků jednotlivým (nebo několika) hláskám, díky čemuž se dá japonskou abecedou psát i čeština, ostatně fonetické přepisy jmen či názvů v každém jazyce tuto univerzálnost abecedy dokazují názorně.
13.7.2006 01:50 Kyosuke | skóre: 28 | blog: nalady_v_modre
Rozbalit Rozbalit vše Re: Japonština
Myslím, že to bude nepochopení...existence grafémů je naprosto nepodstatná pro fakt, že slova jazyka (přirozeného i umělého) nejsou atomická, a to je IMO základní fakt, který se Michal snažil sdělit. A já zase to, že množiny základních stavebních slov různých jazyků (přirozených i umělých) bývají různé. Z pohledu teorie informace to je abeceda. ;-)
13.7.2006 01:51 Kyosuke | skóre: 28 | blog: nalady_v_modre
Rozbalit Rozbalit vše Re: Japonština
Jinak samozřejmě univerzální abeceda jsou dva znaky dvojkové soustavy, teď jen vymyslet vhodné mapování a bude to... :-D
13.7.2006 02:00 Kyosuke | skóre: 28 | blog: nalady_v_modre
Rozbalit Rozbalit vše Re: Japonština
To samozřejmě mělo být „množiny základních stavebních prvků slov“... ;-)
13.7.2006 02:14 xkesh | skóre: 46 | blog: eXtempore
Rozbalit Rozbalit vše Re: Japonština
Myslím, že to bude nepochopení...existence grafémů je naprosto nepodstatná pro fakt, že slova jazyka (přirozeného i umělého) nejsou atomická, a to je IMO základní fakt, který se Michal snažil sdělit.
A vidíte, já bych v tom viděl rozdíl mezi formálním a přirozeným (normálním) jazykem, že totiž přirozený jazyk můžeme zapsat abecedou teprve díky jeho (umělé) formalizaci (protipříklad viz čínština), zatímco autor od začátku aplikuje vlastnosti jazyků formálních i na přirozené (viz jeho zmínka o japonštině), s čímž si dovolím nesouhlasit (viz mou první reakci).

Základem formálních jazyků tak může být "abeceda", jak píše autor, ale k přirozenému jazyku bylo naopak nutné "abecedu" (neboli vaši atomizaci) teprve vynalézt, což pak těžko označit jako jeho základ, díky němuž tento přirozený jazyk existuje (rozhodně přirozený jazyk nevzniká tak, že bychom skládali dohromady definovanou "abecedu" a tu teprve pak spojovali ve slova a věty, cesta je spíše opačná, od vět ke slovům a pak k jednotlivým hláskám či znakům abecedy).

Proto mi tento úvod nepřijde jako vydařený a určitě by stál za upřesnění.
13.7.2006 02:22 Kyosuke | skóre: 28 | blog: nalady_v_modre
Rozbalit Rozbalit vše Re: Japonština
Znamená to tedy, že morfémy bez formalizace v jazyku jako strukturální jev neexistují? Taky bych o tom mohl tak uvažovat, ale to bych pak rovnou mohl celou lingvistiku zahodit jako snahu násilně pasovat logiku na něco „tak krásně neformálně přírodního“... ;-)
13.7.2006 08:56 Michal Kašpar | skóre: 15
Rozbalit Rozbalit vše Re: Japonština
Tak, tak. Ona je abeceda k přirozenému jazyku něco jako přírodní zákon k přírodě. Model, který nám to umožní nějak uchopit, ale dost těžko to lze zaměňovat.

Ostatně dobře je to vidět na tom, když zkusíte "českou latinkou" přečíst anglický text. Budete obtížně hledat angličana, který by Vám rozumněl.
13.7.2006 09:59 xkesh | skóre: 46 | blog: eXtempore
Rozbalit Rozbalit vše Re: Japonština
Tak, tak. Ona je abeceda k přirozenému jazyku něco jako přírodní zákon k přírodě. Model, který nám to umožní nějak uchopit, ale dost těžko to lze zaměňovat.
Tak tak co? Reagujete na otázku: "Znamená to tedy, že morfémy bez formalizace v jazyku jako strukturální jev neexistují?" Odpověď tedy zní "ano, existují" nebo "ano, neexistují"? ;)

Pokud definujete "abecedu" jako "jistou množinu znaků specifickou pro daný jazyk" (což není abeceda v běžném významu), proč používáte pojem "abeceda"? Jinými slovy, proč aplikujete na přirozený jazyk pojem jazyka formálního?

Abeceda (přirazení značek abstrahizovaným hláskám, tedy poloze a činnosti mluvidel) se k přirozenému jazyku se právě rozhodně nemá jako přírodní zákon k přírodě. Protože abeceda nám vůbec neumožňuje přirozený jazyk pochopit (nemyslel jste gramatiku?). Je úplně lhostejné, jakou abecedou nějaký jazyk zapíšete, stále to bude tentýž jazyk.
Ostatně dobře je to vidět na tom, když zkusíte "českou latinkou" přečíst anglický text. Budete obtížně hledat angličana, který by Vám rozumněl.
Maximálně bych mohl zkusit "českou latinkou" anglický text zapsat. Když ho přečtu (dekóduji znaky přiřazené určitým hláskám), bude to stále navzdory zápisu (podle vás) jinou abecedou anglický text, kterému každý Angličan bez problémů porozumí. Du jú andersténd?

A vezmete-li si abecedu očištěnou od nánosů historie, tedy nějakou abecedu používanou k fonetickým přepisům jako je třeba fonetická abeceda IPA a naučíte-li se jí, můžete její pomocí zapsat text v jakémkoliv jazyce a když ho přečtete, bude vám jakýkoliv mluvčí jazyka rozumět, aniž byste použil něco, co odvážně nazýváte "množinou znaků specifickou pro daný jazyk".

Na tom je naopak dobře vidět, co to znamená, že abeceda je univerzální.
13.7.2006 09:43 xkesh | skóre: 46 | blog: eXtempore
Rozbalit Rozbalit vše Re: Japonština
Znamená to tedy, že morfémy bez formalizace v jazyku jako strukturální jev neexistují?
Ne, znamená to, "že totiž přirozený jazyk můžeme zapsat abecedou teprve díky jeho (umělé) formalizaci". Což je obráceně než v jazyce formálním.

Pokud vím, je řeč o abecedě, což je něco jiného než morfologie jazyka (a což jsem já ve svém příspěvku na rozdíl od vás definoval). Pokud si myslíte, že abeceda a morfémy jazyka jsou jedno a totéž, máte to říct, protože to vůbec není samozřejmost.

A když je tedy řeč o morfémech jazyka, tak ty se neskládají z "abecedy" (znaků), ale naopak je lze zpátky vystopovat k původním lexémům. Znaky nejsou to, z čeho skládáme slova, naopak, slova (nebo chcete-li i vaše morfémy) díky abstrakci jednotlivých zvuků neboli hlásek (neboť jednotlivé hlásky nenesou žádný význam) můžeme na hlásky rozkládat. A ty teprve pak abecedou zaznamenat a je úplně lhostejné, jakou konkrétní podobou abecedy, neboť z abecedy se jazyk neskládá.

Tím pádem nelze souhlasit s větami autora, pokud by je chtěl aplikovat na přirozený jazyk:

Základem takového jazyka je abeceda [=jsou písmenka], což je jistá množina znaků [=písmenek] specifická pro daný jazyk. Ze znaků abecedy [=písmenek] jsou tvořena slova (pochopitelně neuvažujeme pro nás exotické jazyky typu japonštiny). Ty dále spojujeme do vět a to za pomoci gramatických pravidel.

Základem jazyka nejsou písmenka, ani nejsou písmenka specifická pro nějaký jazyk, ani nejsou z písmenek tvořena slova.

Pokud to vidíte jinak, např. že autor používá slovo "abeceda" nikoliv v běžném významu (čemuž ovšem odporuje jeho výslovná definice), např. metaforicky ve smyslu "abeceda lásky, abeceda linuxu" nebo snad dokonce "abeceda = souhrn morfémů", napište to. Klást jakoby významné otázky s podtextem, že polemizují s tím, co jsem napsal (a přitom se týkají něčeho úplně jiného), je velice jednoduchá strategie, jak diskusi zavést do slepé uličky.
Taky bych o tom mohl tak uvažovat, ale to bych pak rovnou mohl celou lingvistiku zahodit jako snahu násilně pasovat logiku na něco „tak krásně neformálně přírodního“... ;-)
Samozřejmě můžete uvažovat třeba o růžových slonech... ale jak to souvisí s tématem diskuse (viz výše), budete muset osvětlit dříve, než bude možné na vaše úvahy nějak reagovat ;)
13.7.2006 10:47 Kyosuke | skóre: 28 | blog: nalady_v_modre
Rozbalit Rozbalit vše Re: Japonština
„Pokud to vidíte jinak, např. že autor používá slovo "abeceda" nikoliv v běžném významu (čemuž ovšem odporuje jeho výslovná definice), např. metaforicky ve smyslu "abeceda lásky, abeceda linuxu" nebo snad dokonce "abeceda = souhrn morfémů", napište to.“
Que? :-D Vždyť jsem se to o kus výše snažil sdělit a ještě jsem poukázal na teorii informace, kde prostě jiný termín pro atomické symboly zprávy není. ;-) Nebo o něm aspoň nevím.
13.7.2006 12:24 Hynek (Pichi) Vychodil | skóre: 43 | blog: Pichi | Brno
Rozbalit Rozbalit vše Re: Japonština
Základem formálních jazyků tak může být "abeceda", jak píše autor, ale k přirozenému jazyku bylo naopak nutné "abecedu" (neboli vaši atomizaci) teprve vynalézt, což pak těžko označit jako jeho základ, díky němuž tento přirozený jazyk existuje (rozhodně přirozený jazyk nevzniká tak, že bychom skládali dohromady definovanou "abecedu" a tu teprve pak spojovali ve slova a věty, cesta je spíše opačná, od vět ke slovům a pak k jednotlivým hláskám či znakům abecedy).
Jenže právě tohle je to, co tvrdí Chomsky, tedy, že i přirozené jazyky jsou tvořeny stejně jako formální jazyky svou abecedou a celým tímhle aparátem kolem. Jen je potřeba si uvědomit, že on netvrdí, že tou abecedou je abeceda písemného zápisu, ale určité myšlenkové elementy v mozku rodilého mluvčího. Tedy základem přirozeného jazykou je abeceda přirozených jazykových znaků a základem formálního jazyka je formální abeceda psaná. Na druhou stranu je fakt, že Chomskému například většina psychologů nemůže přijít na jméno a podobně. Otázkou je, jestli to nepramení právě z toho nepochopení, že abecedou u přirozených jazyků není písemná abeceda.
XML je zbytečný, pomalý, nešikovný balast, znovu vynalézané kolo a ještě ke všemu šišaté, těžké a kýčovitě pomalované.
Daniel Kvasnička ml. avatar 13.7.2006 19:39 Daniel Kvasnička ml. | skóre: 52 | blog: The Joys and Sorrows of Being an IT Freak | Ostrava
Rozbalit Rozbalit vše Re: Japonština
Kdyby jen psychologove...zkus mluvit napr. pred vzdelanym a zkusenym anglistou o Chomskem a o tom, co vymyslel ohledne prirozenych jazyku. Bavil jsem se o tom s vedoucim ustavu anglistiky na SLU v Opave. Ukazal mi jednu z Chomskeho knih, ktere o tech vecech pojednavaji (pokrytou prachem :-) ), ze srdce se smal a vypravel, jak kdyz byl on mlady student, jak to strasne zrali a mysleli, ze je to vrchol vseho :-)
FSF: “screw you for not wanting the stuff we produce”, People: “screw you for not producing the stuff we want."
wake avatar 15.7.2006 11:03 wake | skóre: 30 | blog: wake | Praha
Rozbalit Rozbalit vše Re: Japonština
Unicode?
Tento příspěvek má hlavičku i patičku!
13.7.2006 08:05 Michal Vyskočil | skóre: 60 | blog: miblog | Praha
Rozbalit Rozbalit vše Re: Japonština
Budiž to pro mě ponaučení, nemluvit o něčem, čemu nerozumím :-)
Existují dvě skupiny objektových programátorů: Smalltalkeři, a ti, kteří to ještě nepochopili. :-)
Není to tak, že existuje jen jedna skupina? Smalltalkeři? :-P
When your hammer is C++, everything begins to look like a thumb.
13.7.2006 14:05 Kyosuke | skóre: 28 | blog: nalady_v_modre
Rozbalit Rozbalit vše Re: Japonština
Some believe in Smalltalk, some have enough Self-confidence to cope without it. :-D

(Já na ty slovní hříčky jednou zajdu... :-D)
13.7.2006 00:36 Martin Beránek | skóre: 33 | blog: mousehouse | Brno
Rozbalit Rozbalit vše Re: Jazyky a překladače - 1 (úvod)
za pul roku z toho snad budu delat statnice, tak je fajn ze si to pripomenu na svem oblibenem serveru ;-)
never use rm after eight
13.7.2006 04:31 zelial | skóre: 21
Rozbalit Rozbalit vše Re: Jazyky a překladače - 1 (úvod)
Mám přidat, nebo raději ubrat?
tempo je docela silene, ale aspon to neni nudne a rozvlacne. co zaradit vic prikladu?
13.7.2006 08:03 Michal Vyskočil | skóre: 60 | blog: miblog | Praha
Rozbalit Rozbalit vše Re: Jazyky a překladače - 1 (úvod)
Vím, že je šílené. Ale to zase neznamená, že mám z ábíčka dělat vysokoškolská skripta ;-). Potíž je v tom, že nedokážu přesně odhadnout, co můžu a co nemůžu vynechat, tak, aby tomu (s trochou snahy) rozumněl i člověk tímto nezasažený.
When your hammer is C++, everything begins to look like a thumb.
13.7.2006 13:12 zelial | skóre: 21
Rozbalit Rozbalit vše Re: Jazyky a překladače - 1 (úvod)
muzu mluvit jen za sebe: ja jsem clanek cetl prave proto, ze tematiku znam. ostatni diskutujici taky vypadaji zasazene.

ale treba je to jen vysokou vzdelanosti ctenaru abicka a nikdo nezasazeny tu neni ;)
13.7.2006 18:06 Pavel Janousek
Rozbalit Rozbalit vše Re: Jazyky a překladače - 1 (úvod)
Obavam se, ze teto problematice clovek nezasazeny neni schopen jen tak prijit na chut... jednak je ta teorie znacne abstraktni, ale zejmena vetsina si pod temi tridami jazyku neni schopna nic realneho predstavit... (maximalne generovani jednoduchych slov z gramatiky, jak bylo naznaceno - jenze ta gramatika byla tak primitivni, ze jakakoli realna (a to i neatributova) je proti tomu absurdistan:-)) I ja jsem s tim mel problem... naopak jako skladacka nam to zacalo zapadat v okamziku, kdy jsme zacali psal prvni prekladace a dostali se k prakticke strance veci... (a uz jsem to za ty roky stacil opet uspesne pozapominat, protoze syntakticke parsery za mne delaji existujici implementace)

Ale mozna jsou nekteri vetsi snilci a takovyto stupen abstrakce jeste mozkove zvladaji levou zadni...:-)
14.7.2006 15:45 python2 | skóre: 4
Rozbalit Rozbalit vše Re: Jazyky a překladače - 1 (úvod)
Jako nezasazeny to vubec nechapu a myslim ze jste to vzal za spatny konec. Lepsi cesta je od praxe k teorii, tedy jestli to nekomu chcete vysvetlit. Tedy vzit to, co clovek zna a ukazat mu, ze vsechno je jinak a rozpitvat to a vysvetlit, k cemu je to vlastne dobre.
vogo avatar 13.7.2006 08:51 vogo | skóre: 34 | blog: "Skládat papír"
Rozbalit Rozbalit vše Re: Jazyky a překladače - 1 (úvod)
Že já jsem letos dělal zkoušku z formálních jazyků a automatů, no asi to tak bude zdá se mi to nějaké povědomé :).
Nejsem paranoidní, ale to ještě neznamená, že po mě nejdou.
DjAARA avatar 13.7.2006 09:45 DjAARA | skóre: 32 | Praha|Náklo|Olomouc
Rozbalit Rozbalit vše Re: Jazyky a překladače - 1 (úvod)
Zas mi tu chce nekdo pripomenout jisteho tresteneho genia co ruce Romana Lukase ...
DjAARA avatar 13.7.2006 09:45 DjAARA | skóre: 32 | Praha|Náklo|Olomouc
Rozbalit Rozbalit vše Re: Jazyky a překladače - 1 (úvod)
ehm

... co ma po ruce ...
13.7.2006 14:53 nightfish | skóre: 9 | Popůvky
Rozbalit Rozbalit vše Re: Jazyky a překladače - 1 (úvod)
RL je cool
Rezza avatar 17.7.2006 17:39 Rezza | skóre: 25 | blog: rezza | Brno
Rozbalit Rozbalit vše Re: Jazyky a překladače - 1 (úvod)
Vidim, ze RL je hvezda i mimo FIT ;)
xvasek avatar 13.7.2006 10:03 xvasek | skóre: 21 | blog: | Zlín
Rozbalit Rozbalit vše Re: Jazyky a překladače - 1 (úvod)
Toto je článek o ničem. Pokud to člověk umí, tak to má nulovou informační hodnotu, a pokud ne, tak se mu nad tím nebude chtít sedět, protože nemá zatím žádnou motivaci snažit se to pochopit.
Marek Bernát avatar 13.7.2006 18:09 Marek Bernát | skóre: 17 | blog: Arcadia
Rozbalit Rozbalit vše Re: Jazyky a překladače - 1 (úvod)
Nesúhlasím. Ja túto problematiku ovládam a napriek tomu sa mi článok páčil a rozhodne nemá nulovú informačnú hodnotu. Práve naopak, je skvelým úvodom to formálnych jazykov. To že sa niekomu nechce učiť nové veci, ešte nerobí článok nekvalitným. Netuším, do ktorej kategórie patríte Vy, ale prajem Vám, aby ste mali lepšiu náladu a nemuseli písať také mrzuté komentáre ;-)
physics.stackexchange.com -- Q&A stránky o fyzike v štýle StackOverflow.
13.7.2006 23:01 dejfson | skóre: 2
Rozbalit Rozbalit vše Re: Jazyky a překladače - 1 (úvod)
take bych si dovolil nesouhlasit. V pripade ze jste schopny prelouskat teorii mnozin kterou autor v clanku pouziva, pak v podstate jste schopny pochopit teorii formalnich jazyku. Ackoliv mam rekneme nezanedbatelne matematicke znalosti, moje matematika nesaha do oblasti teorie mnozin a logiky, tudiz at ten clanek ctu z kterekoliv strany, nebyl jsem schopny vyextrahovat nejake informace. Paradoxne se tedy dostavam do situace popsane predchozim autorem. Na pochopeni toho co autor clanku napsal je potreba nastudovat asi dalsi semestr matematiky. Nicmene to nevzdavam a doufam ze v pristim dile se neco dozvim :)
Marek Bernát avatar 17.7.2006 06:52 Marek Bernát | skóre: 17 | blog: Arcadia
Rozbalit Rozbalit vše Re: Jazyky a překladače - 1 (úvod)
Tak toto som nepozoroval. Formálne jazyky mi paradoxne vždy pripadali intuitívne natoľko, že aj nie celkom formálne napísaný článok, ako bol tento, mi všetko dostatočne ozrejmil. Ale možno je to len môj prípad.

Teda, opäť z môjho pohľadu, semester matematiky (akej konkrétne?) rozhodne nepotrebujete. Skôr to chce trpezlivosť, prípadne sa opýtať na nejasnosti.
physics.stackexchange.com -- Q&A stránky o fyzike v štýle StackOverflow.
xvasek avatar 14.7.2006 10:01 xvasek | skóre: 21 | blog: | Zlín
Rozbalit Rozbalit vše Re: Jazyky a překladače - 1 (úvod)
Já si prostě myslím, že by se k promatice mělo přistupovat tady na ábíčku přesně opačně, podobným způsobem jako je psán "TeXBook naruby". Pokud se chceme bavit o Regulárních {jazycích|gramatikách|výrazech}, tak bych to udělal přesně opačně - tady jsou RE, umí tady tyto vychytávky a pak teprve popisovat, jak to pracuje. (Což bych viděl i jako "díru na trhu", skript k formálním jazykům je hafo, ale od aplikace k teorii jsem nečetl nic.)

Pak třeba pumping lemma. Celé je to nezajímavé, protože se jedná o implikaci, nikoli o ekvivalenci (přes PL nelze dokázat, že jazyk je regulární). Celé PL se vyučuje pouze kvůli svému důkazu, který demonstruje a shrnuje, jak RE fungují. Kdo pochopil důkaz PL, ten musí nutně chápat i RE. Pokud bych nutně chtěl mít v článku nějakou větu, pak je pro RE v podstatě jediná použítelná Myhill-Nerodova.

Takto k tomu přijdou jenom lidi, kteří se to učili a řeknou si "Jó, to byly časy, to jsme s Máňou na kolejích..." a ostatní to prostě jenom přejdou s výrazem "WTF"?
Marek Bernát avatar 17.7.2006 07:00 Marek Bernát | skóre: 17 | blog: Arcadia
Rozbalit Rozbalit vše Re: Jazyky a překladače - 1 (úvod)
S tým opačným prístupom máte možno pravdu, ničmenej mne sa viac páči smer gramatiky -> RE. Už preto, že článok sa volá formálne jazyky a nie RE, hoci neviem, aký má so seriálom zámer autor.

K tej PL. V článku dôkaz vôbec nebol a autor ju tam zrejme dal kvôli jej významu v odlíšení rôznych tried jazykov. Nechápem, prečo do toho pletiete znova RE.

A ťažko povedať, kto k tomu ako príde, ale ak to zaujme len jedného človeka, ktorý o tom nič nevedel, tak to má zmysel a ľudia ako Vy, ktorí majú potrebu kritizovať, sa môžu ísť vypchať. Myslené v dobrom.
physics.stackexchange.com -- Q&A stránky o fyzike v štýle StackOverflow.
xvasek avatar 20.7.2006 10:25 xvasek | skóre: 21 | blog: | Zlín
Rozbalit Rozbalit vše Re: Jazyky a překladače - 1 (úvod)
RE, konečné automaty a regulární jazyky jsou ekvivalentní (což by se mělo asi časem dokázat).

A s tou PL je problém přesně v tom, co píšeš - PL odděluje nějakou svou třídu jazyků, která ale rozhodně není shodná s třídou regulárních jazyků. Proto když chci odlišit jednotlivé třídy, tak do toho PL vnáší jenom chaos a v tomto článku je čistě kontraproduktivní - nic nevysvětluje (neodděluje), pouze bez důkazu a bez nějakého smyslu zavádí další třídu.
13.7.2006 11:21 nardew | skóre: 5
Rozbalit Rozbalit vše Re: Jazyky a překladače - 1 (úvod)
ako bolo pisane, bolo by dobre keby si napisal nejaku motivaciu, "k comu je dobre ked sa oboznamime s tymto..."

a mozno niekedy nieco vysvetlit viac laicky napriek tomu ze ti co sa rozumeju do problematiky budu frflat a nadavat ze to nie je uplne presne s odbornou definiciou ;)

inak som rad ze sa niekto pustil do takejto tematiky, takze drzim palce...
the best way of Memtest is emerge qt kde-meta
13.7.2006 14:01 petr_p | skóre: 59 | blog: pb
Rozbalit Rozbalit vše Re: Jazyky a překladače - 1 (úvod)
Motivace: Uvod je dobry na to, abyste uverili, az budete cist pokracovani :)

Skutecna motivace: Existuji problemy, ktere za pouziti danych nastroju vyresit nelze, pripadne jejich reseni trva neumerne dlouho. Budete-li tohle znat, nestravite mladi/stari hledanim reseni neresitelneho problemu. (Pratele, tak tudy ne!)
xvasek avatar 13.7.2006 15:11 xvasek | skóre: 21 | blog: | Zlín
Rozbalit Rozbalit vše Re: Jazyky a překladače - 1 (úvod)
Dobře, teď by bylo ještě potřeba dostat to do toho článku.
Marek Bernát avatar 13.7.2006 18:17 Marek Bernát | skóre: 17 | blog: Arcadia
Rozbalit Rozbalit vše Re: Jazyky a překladače - 1 (úvod)
Ten článok napríklad pekne ukazuje že taká bežná vec, ako sú regulárne výrazy, má formálny podklad, o čom mnohí používatelia zrejme ani netušia. Proste je to zaujímavé. Nestačí Vám to? Smola, skúste iný článok, motivačne zameraný.
physics.stackexchange.com -- Q&A stránky o fyzike v štýle StackOverflow.
14.7.2006 15:51 python2 | skóre: 4
Rozbalit Rozbalit vše Re: Jazyky a překladače - 1 (úvod)
Nestaci, protoze nevim k cemu mi je to dobre vedet, ze RE maji formalni podklad? Dejme tomu, ze investuji x hodin sveho vzacneho casu do toho, abych to pochopil, k cemu mi ta investice bude dobra, jaky to pro me bude mit prinos?
14.7.2006 16:13 Michal Kubeček | skóre: 71 | Luštěnice
Rozbalit Rozbalit vše Re: Jazyky a překladače - 1 (úvod)
Třeba k tomu, aby se tady pořád dokola neopakovaly dotazy typu "jako udělat regulární výraz, který mi najde XYZ", kde XYZ je věc, kterou už od pohledu regulárním výrazem popsat nelze. Jenže ony se samozřejmě budou opakovat stejně, takže je to asi jedno…
14.7.2006 17:16 python2 | skóre: 4
Rozbalit Rozbalit vše Re: Jazyky a překladače - 1 (úvod)
Ja s pouzivanim RE problemy nemam bez znalosti jejich formalniho podkladu. Imho clovek ktery nerozumi RE tento clanek ani nebude cist. Takze prinos, bude tu mene hloupych dotazu, asi nebude pozorovatelny a hlavne to neodpovda na otazku, co to prinese mne, kdyz venuji x hodin na to, abych to pochopil.
Marek Bernát avatar 17.7.2006 06:44 Marek Bernát | skóre: 17 | blog: Arcadia
Rozbalit Rozbalit vše Re: Jazyky a překladače - 1 (úvod)
Neviem, či som jediný na celom svete, koho baví učiť sa bez toho, aby vedel, že koľko mu to zaberie času, načo, prečo a kedy. Mám presne opačný prístup a totiž, že všetko sa zíde a je lepšie vedieť viac ako menej.

A ešte jedno pozorovanie. Zatiaľ, čo sem vy, Páni s nedostatkom času, píšete komentáre, tak ste sa mohli snažiť niečo naučiť. Ak by ste toho času nemali dosť a takí ľudia skutočne existujú, nezabíjate ho písaním trápnych komentárov.

Bolo mi potešením a dúfam, že sa dozviem viac o ľudskej snahe zostať v nevedomosti a teórii hľadania výhovoriek ;-)
physics.stackexchange.com -- Q&A stránky o fyzike v štýle StackOverflow.
13.7.2006 18:08 Pavel Janousek
Rozbalit Rozbalit vše Re: Jazyky a překladače - 1 (úvod)
No jo, jenze realne programatorske problemy se mi oplatilo resit bud konecnym (stavovym) automatem a nebo to nechat udelat profesionaly (jako treba XML parser)...:-) Ale simple prekladac javy jakozto seminarka nebo simulator vysoce pararelniho stroje jsme zvladli...:-)
xvasek avatar 14.7.2006 10:20 xvasek | skóre: 21 | blog: | Zlín
Rozbalit Rozbalit vše Re: Jazyky a překladače - 1 (úvod)
Ještě jsem si to promýšlel znovu a toto není správně. Spíš je to IMHO o tom, že všichni přemýšlejí a programují v jazycích typu 0, což se jim daří - všechny jazyky v Chomského hierarchii jsou i typu 0, takže jdou rozpoznat Turingovým strojem a ekvivalentními. Tady jde primárně o to říct, že některé problémy (jazyky) jsou zároveň i jednodušší a na jejich řešení (analýzu) je vhodné buď používat jiné nástroje, nebo aspoň naučit sebe a svůj TS myslet a pracovat v těchto jednodušších třídách.

Druhou motivací by mohlo být umět najít problémy z jazyků daných typů, takže odpovědět na otázky například "Proč je kontrola formátu IP adresy pomocí RE tak složitá?" - "Protože jsou to 4 čísla a RE pracují se znaky".

Co popisuješ ty je už složitost, což je _jenom_ o TS gramatikách typu 0 (všechno ostatní je lineárně složité k délce vstupu), nebo vyčíslitelnost, což je třída problémů mimo gramatiky typu 0.
13.7.2006 15:17 rastos | skóre: 61 | blog: rastos
Rozbalit Rozbalit vše Re: Jazyky a překladače - 1 (úvod)
Dúfam, že to časom dospeje k praktickému použitiu nástrojov ako je flex, yacc či bison. Držím palce.
13.7.2006 18:09 Pavel Janousek
Rozbalit Rozbalit vše Re: Jazyky a překladače - 1 (úvod)
To sice ano, ale doufam ze vite kde presne konci...:) Ja bych videl jako podstatne prinosnejsi jit za jejich moznosti (o tom se ani ve VS skriptech moc clovek nedozvi) - to by mohla byt ta pridana hodnota, po ktere tu nekteri volaji.
13.7.2006 21:29 Honza "tux" Friesse | skóre: 15 | blog: Tuxův blog | Vyškov
Rozbalit Rozbalit vše Re: Jazyky a překladače - 1 (úvod)
Hezký článek, ale stejně jsem rád, že jsem problematiku slyšel v podání Prof. Meduny (počítám, že z jeho skript velká část článku vychází). Je to zážitek na celý život.
DjAARA avatar 13.7.2006 22:45 DjAARA | skóre: 32 | Praha|Náklo|Olomouc
Rozbalit Rozbalit vše Re: Jazyky a překladače - 1 (úvod)
13.7.2006 21:43 Milan Stary | skóre: 4
Rozbalit Rozbalit vše Re: Jazyky a překladače - 1 (úvod)
Já zas rád vzpomínám na (tehdy docenta) Bořka Melichara z katedry počítačů ČVUT na Karláku. Zahulená kancelář, na zdi obraz hasičů někde ze Žďárska. Ten pán to uměl nádherně s jemným humorem podat. To je dar, který ne každý kantor má. Jinak ta teorie je sama o sobě suchá jako troud.
13.7.2006 23:37 kokosjb
Rozbalit Rozbalit vše Re: Jazyky a překladače - 1 (úvod)
Hezký den, jsem "člověk tímto nezasažený" :), ale zvídavý a rád si takovéto články přečtu. Tempo je rozumné, jen bych prosil (pro příště) o slovní popis těch formálních zápisů, ve kterých se to jen hemží řeckými písmeny a podivnými znaky. Laikovi se to dost špatně čte. Děkuji
13.7.2006 23:43 Kníže Ignor | skóre: 19 | blog: stoupa
Rozbalit Rozbalit vše Re: Jazyky a překladače - 1 (úvod)
Bohužel učebnicová ukázka toho, jak článek vypadat nemá a nesmí. Pokud by autorem nebyl Michal Vyskočil (sice má u mě vroubek :-)), vychrlil bych ze sebe, jak je ostatně mým dobrým zvykem, dlouhou řadu nadávek a vulgarismů.

Nikdy nejde snažit se psát populárně a zároveň se snažit být formální!!! V článku jsou nepřesnosti, je to samozřejmě daň populárnosti a omezeného prostoru pro článek.

Například tvrzení "A navíc tvar přepisovacích pravidel z množiny P umožňuje zařazení jazyka do některé z následujících čtyř tříd." čtenáře musí zmást (lze chápat buď tak, že neříká zhola nic - to díky slovu "umožňuje", nebo špatně). Většinový čtenář se z něho získá mylný dojem, že pravidla musí být vždy v tom "kanonickém" tvaru. Kam asi čtenář s využítím zmíněné věty zařadí gramatiku A -> aBC, B -> a, C -> a?

Dál si myslím, že by bylo třeba alespoň říct, že v té hierarchii jde vždy o vlastní podmnožiny.

Článek nesmí být nikdy pouze šikovným a smysluplným poskládáním poznatků ze skript/manuálu, musí v něm být vždy něco z autora. Nicméně toto je seriál, autor má ještě šanci se předvést. Do zvěřejnění dalšího dílu zůstanu zděšen :-)
Jestli máš zálohu mého blogu, tak mi ji pošli. Nějak jsem si ho smazal :-)
14.7.2006 00:08 Michal Ambroz | skóre: 22
Rozbalit Rozbalit vše Re: Jazyky a překladače - 1 (úvod)
kdo nic nedela nic nezkazi vid ?
14.7.2006 01:11 Semo | skóre: 44 | blog: Semo
Rozbalit Rozbalit vše Re: Jazyky a překladače - 1 (úvod)
Protože nedokážeme najít žádný podřetězec y, dokázali jsme, že daný jazyk není regulární.

A to vyplyva z coho, co je uvedne v clanku? Cela cast o Pumping leme je napisana strasne. Keby som nevedel zo skoly o AaG dost, tak z tohoto to nikdy nepochopim.

Bud tam tu lemu napisem celu aj s dosledkami a vyuzitim, alebo ju tam necpem vobec. Hmlisto povedat, ze nieco existuje a potom pouzit slovne spojenie "a teda to mame dokazane" nie je stastna kombinacia.
If you hold a Unix shell up to your ear, you can you hear the C.
xvasek avatar 14.7.2006 10:04 xvasek | skóre: 21 | blog: | Zlín
Rozbalit Rozbalit vše Re: Jazyky a překladače - 1 (úvod)
:-) Ani ne tak "s důsledky a použitím", ale spíš "s důkazem a motivací, proč vlastně PL zavádíme."
15.7.2006 21:31 MJ | Tady a teď
Rozbalit Rozbalit vše Chomského hierarchie
Dvě maličké připomínky k Chomského hierarchii:

(1) Je pravda, že jazyky třídy 0 lze rozpoznat Turingovým strojem, ale ne tím způsobem, který by člověk na první pohled čekal, tj. že by pro každou gramatiku existoval program pro TS, který dostane řetězec a odpoví, zda je řetězec gramatikou generován či nikoliv. Existuje ovšem program, který na tuto otázku "odpoví" tím, zda se zastaví nebo běží věcně. Zastavení takového programu ale nemusí být na TS rozhodnutelné.

(2) Ona ta hierarchie není tak docela hierarchií gramatik, jako spíš hierarchií jazyků -- jazyk patří do příslušné třídy, pokud existuje gramatika ve tvaru daném onou třídou, která daný jazyk generuje.
15.7.2006 21:40 MJ | Tady a teď
Rozbalit Rozbalit vše Pumping lemma
(Nechci autora v žádném případě odradit od jeho bohulibého počínání, ale přeci jen mi to nedá, abych něco maličko nedodal...)

Pumping lemma je mocná zbraň, takový kanón světa gramatik :) Zde je ovšem jazyk 0^n1^n v roli nebohého vrabce, poněvadž jeho neregulárnost se dá nahlédnout i pomocí rozumu řečeného selský (a principu řečeného holubníkový, potažmo Dirichletův):

Kdyby náš jazyk byl regulární, znamenalo by to, že ho lze rozpoznat nějakým konečným automatem. Tak si takový automat vezměme a označme K počet jeho stavů. Teď se podívejme na řetězce 0^0, 0^1, ..., 0^K. To je celkem K+1 různých řetězců, tedy po zpracování nějakých dvou z nich, řekněme 0^i a 0^j musí automat skončit v témže stavu. Proto ale musí ve stejném stavu skončit i po zpracování řetězců 0^i1^i a 0^j1^i, jenže jeden z nich jsme měli přijmout a druhý zamítnout. A jsme ve při (totiž sporu).
18.7.2006 16:47 klobouk
Rozbalit Rozbalit vše Re: Jazyky a překladače - 1 (úvod)
Zasazenost tematem: nula

Motivace pochopit: ano

Casove moznosti: bohuzel omezene

Dotaz 1: nedari se mi pochopit toto: V cem spociva rozdil mezi iteraci sigma* a mnozinou prepisovacich pravidel?

Dotaz 2: G=(N, Σ, P, S) znamena, ze N (konečná množina nonterminálních symbolů) nepatri do abecedy Σ ?

Rozhodne bych se primluvil za:

1. vice prikladu

2. mene souveti, ktera by sla nahradit vice jednoduchymi vetami

3. mozna take rozdvojeni textu. Nejdrive danou vec rici formalne spravne a pak na nejakem prikladu vysvetlit po lopate pro "laiky" (je mi jasne, ze to bude vice textu, ale take to bude pro vicero vrstev prinosne)

4. postup od prikladu k teorii, aspon tam kde to pujde.

P.S.: Podotykam, ze jsem to pred napsanim komentare cetl nekolikrat a fakt se snazil to pochopit a neco se naucit, ale fakticky na tom nemuzu travit tyden nebo dokonce semestr ;-)
18.7.2006 16:49 klobouk
Rozbalit Rozbalit vše Re: Jazyky a překladače - 1 (úvod)
P.P.S.: casti pro laiky a profiky by pak ovsem mely byti viditelne oddeleny, aby se nepletly ;-)
Marek Bernát avatar 18.7.2006 17:44 Marek Bernát | skóre: 17 | blog: Arcadia
Rozbalit Rozbalit vše Re: Jazyky a překladače - 1 (úvod)
Dotaz 1: iteráciou abecedy dostanete jazyk obashujúci všetky možné slová, ktoré sa v danej abecede dajú vytvoriť. Množina pravidiel slúži na špecifikáciu slov, ktoré dostanete. Teda iteráciou abecedy dostanete istý druh jazyka, ale pomocou pravidiel môžete dostať veľa rôznych jazykov (ale nie všetky, pretože jazykov je nespočítateľne veľa, zatiaľ čo gramatík len spočítateľne).

Dotaz 2: myslené je to tak, že neterminály sú pomôcky pri odvodzovaní slov, niečo ako premenné, kdežto v abecede sú konkrétne symboly, z ktorých sa slová skladajú. Teda áno, žiadny neterminál nepatrí do abecedy.

Vaše pripomienky sú skvelé, kebyže som autor toho článku, tak ich využijem ;-) Lebo toto je podľa mňa presne to, čo článku chýba, komentár od niekoho, kto má chuť učiť sa, ale tento predmet nepozná.
physics.stackexchange.com -- Q&A stránky o fyzike v štýle StackOverflow.
18.7.2006 20:40 klobouk
Rozbalit Rozbalit vše Re: Jazyky a překladače - 1 (úvod)
Dotaz 1: achaa (snad) chapu ... dekuji :)

Dotaz 2: jasne, takze nonterminaly jsou jen pomucky. S nimi "nastartuji" tvorbu slova (S) a slova dale prodluzuji (napr. A->xA). Muze ("hotove") slovo obsahovat nonterminalu, nebo vzdy musi byt posledni krok prepisovaci pravidlo A->e (z nonterminaly na "nulovy retezec") ?
Marek Bernát avatar 18.7.2006 21:29 Marek Bernát | skóre: 17 | blog: Arcadia
Rozbalit Rozbalit vše Re: Jazyky a překladače - 1 (úvod)
Som rád, že môžem trochu pomôcť. Ja sa už týmto veciam síce nevenujem, ale rozhodne je to zábava, ak už nič iné :-)

Dotaz 2: Hotové slová musia patriť do iterácie abecedy. Teda posledným krokom musí byť pravidlo, ktoré na pravej strane nemá neterminál. Neterminály ako také nie sú pre jazyk vôbec podstatné, lebo, ako je aj uvedené v článku, spôsob tvorby jazykov pomocou je ekvivaletný rôznym strojom, ktoré hovoria, či slovo do jazyka patrí, alebo nie. Teda, dôležitá je len abeceda a pravidlá. To je koniec koncov celkom zrejmé, lebo je jedno, či máte rovnicu s neznámymi x, y, z alebo a, b, c, výsledok závisí na jej tvare; neformálne povedané. Dúfam, že to nevysvetľujem veľmi mätúco :-)
physics.stackexchange.com -- Q&A stránky o fyzike v štýle StackOverflow.
18.7.2006 21:52 klobouk | skóre: 2
Rozbalit Rozbalit vše Re: Jazyky a překladače - 1 (úvod)
cheche, ze by prave proto se to delilo na terminaly a neterminaly ? No mohlo mi to dojit, ale dekuji vysvetleni chapu (o5 snad). Proste nonterm. nejsou v abecede (N nema prunik s Sigma) a zaroven plati, ze "hotove" slovo musi byt iteraci abecedy, tzn. obsahovat only terminaly.

Chm ono je to celkem pochopitelne, kdyz se to nerika tema klikyhakama, ale prostym slovem :-O

Jinak i pro mne je to take spise zabava :), ptze v programovani jsem nebyl nijak systematicky vzdelan a ted jsem "nucen" ho pouzivat, takze by urcite bylo fajn pochopit sem tam nejakou tu teorii, ona ta praxe potom jde obcas i lepe ... hehe :)
Buh stvoril Evu a rekl Adamovi: "Tady mas a vyber si!" ;-)
18.7.2006 22:12 Michal Kubeček | skóre: 71 | Luštěnice
Rozbalit Rozbalit vše Re: Jazyky a překladače - 1 (úvod)
Prostě dokud tam máte nějaký ne-terminál, tj. ne-koncový objekt, nemůžete skončit. :-)
18.7.2006 18:11 Kníže Ignor | skóre: 19 | blog: stoupa
Rozbalit Rozbalit vše Re: Jazyky a překladače - 1 (úvod)
Dotaz 2 je správná připomínka. Nejenže N nepatří do Σ, ale ty dvě množiny musí být disjunktní.
Jestli máš zálohu mého blogu, tak mi ji pošli. Nějak jsem si ho smazal :-)
22.7.2006 20:30 Martin
Rozbalit Rozbalit vše Re: Jazyky a překladače - 1 (úvod)
Ja si taky prosel FJA a mel jsem podobny problem, jako uz tu nekdo zminoval a sice, ze mi to vsechno zacalo davat smysl az kdyz jsem se ucil teorii prekladacu, ale v te dobe uz jsem toho zase spoustu zapomnel.

Myslim, ze smer je vporadku, jen by to chtelo podbrobnejsi motivacni uvod. A pred kazdym novym tematem dalsi. Myslim, ze poradna motivace na zacatku je to, co mi chybelo.
9.8.2006 21:01 stando
Rozbalit Rozbalit vše Re: Jazyky a překladače - 1 (úvod)
Slovo, jehož délka je nulová, značíme e a pozitivní iterace tento znak neobsahuje

myslim, ze to nie je celkom presne. Ak Σ neobsahuje \E(epsilon-prazdne slovo) potom pozitivna iteracia tento znak neobsahuje. Ak vsak Σ obsahuje \E potom ho obsahuje ak pozitivna iteracia...aspon dufam, ze je to tak :)

6.11.2008 15:55 Jake
Rozbalit Rozbalit vše Překlep v příkladu
... získali xxyS
>
... získali xxyA

Založit nové vláknoNahoru

ISSN 1214-1267   www.czech-server.cz
© 1999-2015 Nitemedia s. r. o. Všechna práva vyhrazena.