IB005 úkol 10, příklad 2 Odevzdání: 6. 5. 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.
2. [0,5 bodu] Mějme opět trpaslíčka pracujícího v dole z úlohy 0801. 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.
Tentokrát se rozbilo i celé krumpáčové potrubí. Trpaslíček tedy musí rozbitý krumpáč posílat
ve vozíčku do skladu krumpáčů. Když trpaslíčkům ve skladu s krumpáči přijede rozbitý krumpáč,
pošlou další vozíček s novým krumpáčem. Od chvíle, kdy se trpaslíčkovi krumpáč rozbije, do chvíle,
kdy dostane nový, nemůže odesílat vozíčky kromě vozíčku s krumpáčem. 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.
Zkonstruujte zásobníkový automat (PDA) pro jazyk, 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), odjezd
vozíčku s rozbitým krumpáčem (or) a příjezd vozíčku s novým krumpáčem (pn). Pozor, akce or a
pn se skládají se dvou symbolů. 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 odešle rozbitý krumpáč poté, co se mu rozbil.
Nový krumpáč dostane až poté, co odešle rozbitý. 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 může odjet pouze vozíček
s rozbitým krumpáčem (mezi libovolným výskytem b a k němu příslušejícím výskytem n může
být pouze jeden výskyt o, konkrétně or, můžou mezi nimi však být p).
• Rozbitý krumpáč může trpaslíček reportovat pouze odeslaním vozíčku s rozbitým krumpáčem.
Nový krumpáč může dostat pouze v přicházejícím vozíčku. (Těsně před každým r je znak o a
těsně před každým n je znak 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
• pborpno
• bporppnoo
• bporpnpborpnoo
• pbporpnoobporpno
Příklady slov nepatřících do jazyka L:
• ppo
• poop
• brn
• ppboropno
• pobororpnpnoo
• porpno
Uveďte zásobníkový automat, který rozpoznává jazyk L. Výsledný zásobníkový automat nesmí být
rozšířený.
Úkol budete odevzdávat skrz AutomataTutor. Odkazy a informace k přihlášení jste dostali emailem.
Potřebné údaje najdete i v interaktivní osnově v kapitole Softwarové nástroje.
Oblast strojově snímaných informací, nezasahujte. Druhá strana se neskenuje. Zde jsou losi.
IB005 úkol 10, příklad 2 Odevzdání: 6. 5. 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.
Pokyny ke konstrukci PDA najdete v stránce úkolu na webu AutomataTutor.
Odevzdávaný zásobníkový automat si uložte. Pokud dojde k problémům se systémem AutomataTutor,
požádáme vás o odevzdání výsledného zásobníkového automatu přes odevzdávárnu.
Oblast strojově snímaných informací, nezasahujte. Druhá strana se neskenuje. Zde jsou losi.