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

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

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
• Formální jazyky
• Chomského klasifikace gramatik
• Praktický příklad
• Meze regulárních jazyků
• Závěr

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.

       

Komentáře

[Kyosuke]

A proč bychom pro formální účely nemohli znaky katakany, hiragany a kanji považovat za znaky abecední? Kde je problém?

[xkesh]

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ý). ;)

[Kyosuke]

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.)

[xkesh]

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ě.

[Kyosuke]

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.

[Kyosuke]

Jinak samozřejmě univerzální abeceda jsou dva znaky dvojkové soustavy, teď jen vymyslet vhodné mapování a bude to...

[Kyosuke]

To samozřejmě mělo být „množiny základních stavebních prvků slov“...

[xkesh]

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í.

[Kyosuke]

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“...

[Michal Kašpar]

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.

[xkesh]

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í.

[xkesh]

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 ;)

[Kyosuke]

„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? 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.

[Hynek (Pichi) Vychodil]

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.

[Daniel Kvasnička ml.]

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

[wake]

Unicode?

[Michal Vyskočil]

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

[Kyosuke]

Some believe in Smalltalk, some have enough Self-confidence to cope without it.

(Já na ty slovní hříčky jednou zajdu... )

[Martin Beránek]

za pul roku z toho snad budu delat statnice, tak je fajn ze si to pripomenu na svem oblibenem serveru

[zelial]

Mám přidat, nebo raději ubrat?

tempo je docela silene, ale aspon to neni nudne a rozvlacne. co zaradit vic prikladu?

[Michal Vyskočil]

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ý.

[zelial]

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 ;)

[Pavel Janousek]

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...

[python2]

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]

Ž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é :).

[DjAARA]

Zas mi tu chce nekdo pripomenout jisteho tresteneho genia co ruce Romana Lukase ...

[DjAARA]

ehm

... co ma po ruce ...

[nightfish]

RL je cool

[Rezza]

Vidim, ze RL je hvezda i mimo FIT ;)

[xvasek]

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]

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

[dejfson]

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]

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.

[xvasek]

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]

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.

[xvasek]

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.

[nardew]

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...

[petr_p]

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]

Dobře, teď by bylo ještě potřeba dostat to do toho článku.

[Marek Bernát]

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ý.

[python2]

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?

[Michal Kubeček]

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…

[python2]

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]

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

[Pavel Janousek]

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]

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.

[rastos]

Dúfam, že to časom dospeje k praktickému použitiu nástrojov ako je flex, yacc či bison. Držím palce.

[Pavel Janousek]

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.

[Honza "tux" Friesse]

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]

viz http://www.abclinuxu.cz/clanky/programovani/jazyky-a-prekladace-1-uvod/diskuse#17

[Milan Stary]

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.

[kokosjb]

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

[Kníže Ignor]

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

[Michal Ambroz]

kdo nic nedela nic nezkazi vid ?

[Semo]

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.

[xvasek]

Ani ne tak "s důsledky a použitím", ale spíš "s důkazem a motivací, proč vlastně PL zavádíme."

[MJ]

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.

[MJ]

(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).

[klobouk]

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

[klobouk]

P.P.S.: casti pro laiky a profiky by pak ovsem mely byti viditelne oddeleny, aby se nepletly

[Marek Bernát]

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á.

[klobouk]

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]

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

[klobouk]

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 :)

[Michal Kubeček]

Prostě dokud tam máte nějaký ne-terminál, tj. ne-koncový objekt, nemůžete skončit. :-)

[Kníže Ignor]

Dotaz 2 je správná připomínka. Nejenže N nepatří do Σ, ale ty dvě množiny musí být disjunktní.

[Martin]

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.

[stando]

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 :)

[Jake]

... získali xxyS
>
... získali xxyA