IB102 úkol 8, příklad 1 Odevzdání: 19. 11. 2018
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. [2 body] Informatik má hlad a chtěl by si proto udělat sendvič. Na internetu si najde návod
na výrobu sendvičů. Sendvič se skládá ze dvou krajíců chleba, které musí být z vnitřní strany
namazané máslem, kečupem, nebo hořčicí (každý krajíc může být namazaný něčím jiným). Uvnitř
sendviče může být libovolné množství uzeniny, zeleniny a sýra. Zelenina může být rajče, okurka nebo
salát. Uzenina může být slanina nebo šunka. Sýr může být mozzarella nebo čedar. Informatik chce
však navíc žít zdravě, a tak dává přednost zdravému sendviči. Zdravý sendvič je takový sendvič, ve
kterém je každý plátek uzeniny vykompenzovaný alespoň jedním kusem zeleniny.
Aby informatik návodu na výrobu sendviče lépe rozuměl, rozhodl se přepsat si ho jako bezkontextovou
gramatiku. Mějme tedy abecedu Σ = {chleba, máslo, kečup, hořčice, rajče, okurka, salát,
slanina, šunka, mozzarella, čedar}. Zkonstruujte bezkontextovou gramatiku, která popisuje právě
všechny zdravé sendviče.
V zápisech slov nad abecedou Σ budeme pro přehlednost přidávat mezi jednotlivé znaky mezeru.
Tato mezera je pouze pomůckou k čitelnosti, není součástí slov. Příklady zdravých, správně
vytvořených sendvičů:
• chleba máslo hořčice chleba
• chleba kečup rajče rajče kečup chleba
• chleba máslo mozzarella čedar hořčice chleba
• chleba hořčice čedar salát máslo chleba
• chleba máslo slanina rajče salát šunka kečup chleba
• chleba máslo rajče salát okurka slanina kečup chleba
Nezdravé, nebo špatně utvořené sendviče jsou například:
• slanina
• rajče
• ε
• chleba máslo chleba
• chleba máslo slanina šunka máslo chleba
• máslo chleba máslo
• chleba máslo slanina rajče salát šunka chleba
• chleba hořčice čedar salát kečup máslo chleba
Možným řešením je gramatika G = ({S, Mazání, Náplň, Uzenina, Zelenina, Sýr}, Σ, P, S), kde
P = {S → chleba Mazání Náplň Mazání chleba,
Mazání → máslo | kečup | hořčice,
Náplň → ε | Uzenina Náplň Zelenina Náplň
| Zelenina Náplň Uzenina Náplň
| Sýr Náplň
| Zelenina Náplň,
Uzenina → šunka | slanina,
Zelenina → rajče | okurka | salát,
Sýr → mozzarella | čedar }.
Oblast strojově snímaných informací, nezasahujte. Druhá strana se neskenuje. Zde jsou losi.
IB102 úkol 8, příklad 1 Odevzdání: 19. 11. 2018
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.
U iniciálního neterminálu S se zajistí, že se sendvič skládá ze dvou krajíců chleba z vnitřní strany
namazaných. Neterminál Náplň potom popisuje část sendviče mezi dvěma namazanými chleby, kde
je potřeba dodržet pravidla pro vytvoření zdravého sendviče. Tato část tedy může být prázdná
(pravidlo Náplň → ε), nebo může obsahovat libovolné množství uzeniny, každý plátek však musí
být vykompenzovaný jedním kusem zeleniny (pravidla Náplň → Uzenina Náplň Zelenina Náplň |
Zelenina Náplň Uzenina Náplň). Dále může obsahovat libovolné množství sýra (pravidlo Náplň →
Sýr Náplň) a libovolné množství zeleniny navíc (pravidlo Náplň → Zelenina Náplň).
Oblast strojově snímaných informací, nezasahujte. Druhá strana se neskenuje. Zde jsou losi.