share: true
author: Jan Černý
date: 2022-10-01

Jan Černý

06. 10. 2022

Zadání

Navrhněte bezkontextovou gramatiku pro následující bezkontextové jazyky:

Poznámka

Pomocí zápisu značíme počet symbolů v řetězci .

generuje takové věty, které jsou palindrom a zároveň počet symbolů '' je beze zbytku dělitelný třemi.

Vysvětlení

Jako neterminály jsem si určil zbytky po dělení 3, tedy .
Pomocí přechodu na nebo vytvářím palindromy, a to přidáním dvou -ček nebo dvou -ček,
Přidáním dvou -ček se změnil zbytek po dělení, nahradím tedy tímto zbytkem. Přidáním -ček se zbytek nemění, tedy zůstává stejné.
Neterminál lze nahradit i pouze -čkem, protože tím dosáhneme zbytku po dělení 0 a lze tak vytvořit platnou větu.
Neterminál lze nahradit libovolným počtem -ček nebo , protože tím se zbytek po dělení nemění, zůstává 0, a lze tak vytvořit platnou větu.

Místo lze jako startovní neterminál určit , a mít tak o pravidlo méně, ale pro přehlednost jsem si nechal S, snad nevadí 😉

generuje takové věty, ve kterých je 2x více symbolů '' oproti symbolům '', včetně prázdného řetězce.
např. tedy

Vysvětlení

Nejdříve potřebuji vytvořit nejkratší možné řetězce splňující , tedy vznikne mi .
Ty lze pro tvorbu delších řetězců libovolně vkládat do sebe, tedy na všechny možné pozice jsem přidal .