IB005 úkol 8, příklad 1 Odevzdání: 15. 4. 2024 12:00
Jméno: UČO:
list učo body
Oblast strojově snímaných informací. Své učo a číslo listu vyplňte
zleva dle vzoru číslic. Jinak do této oblasti nezasahujte.
1. [0,5 bodu] Mějme trpaslíčka pracujícího v dole. Trpaslíček má krumpáč, kterým těží rudu.
Přijíždí za ním vozíčky, které on plní rudou a plné je posílá pryč. Naneštěstí se mu krumpáč může
rozbít. V takovém případě si potrubní poštou požádá o nový krumpáč, který mu pak potrubní poštou
přiletí. Od chvíle, kdy se mu krumpáč rozbije, do chvíle, kdy dostane nový, ovšem nemůže odesílat
vozíčky, protože nemůže těžit. Trpaslíček je také svědomitý a na konci každé směny chce mít všechny
vozíčky, které přijely, zase odeslané, a krumpáč v pořádku.
Vaším úkolem bude definovat bezkontextovou gramatiku, která popisuje možné posloupnosti akcí
které se trpaslíčkovi stanou za jeden pracovní den.
Stát se můžou následující akce: příjezd vozíčku (p), odjezd vozíčku (o), rozbití krumpáče (b), žádost
o nový krumpáč (r) a doručení nového krumpáče (n). Popisovaný jazyk L je tedy nad abecedou
Σ = {p, o, b, r, n}.
Dále musí platit:
• V žádnou chvíli nemůže odjet víc vozíčků, než kolik jich přijelo (pro každý prefix u ∈ Σ∗
nějakého slova z L platí #p(u) ≥ #o(u)).
• Na konci všechny vozíčky, které přijely, taky odjely (pro každé w ∈ L platí #p(w) = #o(w)).
• Rozbít se může jen funkční krumpáč. Trpaslíček reportuje rozbitý krumpáč poté, co se mu rozbil.
Nový krumpáč dostane až poté, co ho zareportuje. Jiné posloupnosti těchto akcí nemůžou
nastat. Na začátku i na konci má trpaslíček k dispozici funkční krumpáč. (Pro libovolné w ∈ L
uvažme slovo wbrn, které vznikne z w vynecháním p a o. Platí wbrn ∈ {brn}∗.)
• Dokud má trpaslíček rozbitý krumpáč, vozíčky můžou přijíždět, ale ne odjíždět (mezi libovolným
výskytem b a k němu příslušejícím výskytem n nemůžou být žádné výskyty o, můžou
mezi nimi však být p).
Jazyk L popisuje všechny možné sekvence akcí, které se během trpaslíčkova pracovního dne
mohou stát. Tedy právě ty sekvence, které splňují výše popsané podmínky. V každém slově je vlevo
nejstarší a vpravo nejnovější akce.
Příklady slov patřících do jazyka L:
• ε
• ppoopo
• brn
• bprpnoo
• bprpnbrpnooo
• pbprpnoobrpnoo
Příklady slov nepatřících do jazyka L:
• ppo
• poop
• br
• ppbrono
• pbrrno
• prno
Vaším úkolem je sestrojit bezkontextovou gramatiku, která generuje jazyk L. (Gramatika může, ale
nemusí obsahovat epsilon pravidla.)
Úkol nebudete odevzdávat přes odevzdávárnu, ale skrz odpovědník.
Oblast strojově snímaných informací, nezasahujte. Druhá strana se neskenuje. Zde jsou losi.