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
Oblast strojově snímaných informací, nezasahujte. Druhá strana se neskenuje. Zde jsou losi.