IB102 - úkol 2, příklad 2 - řešení
Odevzdání: 1.10. 2012
Vypracoval: James Bond UČO: 007
Skupina: MI6
2. [2 body] Navrhněte regulární gramatiku, která generuje všechna čísla v trojkové soustavě dělitelná pěti. Pro jednoduchost předpokládejme, že korektně zapsané číslo je i to, které začíná nulou či nulami. Například čísla 12 nebo 101 mají být generována gramatikou, stejně jako čísla 012, 0012, 0101, atd. Naopak čísla 20,21,22 ani 100 gramatikou být generována nemají. Nezapomeňte, že 0 je dělitelná pěti. Naopak prázdné slovo e není číslem v trojkové soustavě.
TIP: Neterminály gramatiky si označte Sq, S±, S2, s3, S4.
Řešení: Pro řešení je potřeba si uvědomit, že pokud k zápisu čísla x v trojkové soustavě přiřetězíme symbol 0, znamená to vlastně vynásobit hodnotu čísla x třemi. Například pokud x = 102, tj. 11 v soustavě desítkové, pak 1020 odpovídá 3-11 = 33. To ale znamená, že třemi násobíme i zbytek po dělení pěti. Například, zbytek po dělení čísla x = 102 (tj. 11 v desítkové soustavě) je 1 a zbytek po dělení x = 1020 (tj. 33 v desítkové soustavě) je 3 -1 = 3. Analogické úvahy vedou k tomuto řešení. Index neterminálu i vždy označuje zbytek po dělení 3 pro již vygenerovaný prefix terminálů a aktuální větné formy aSi. Tedy například lze vygenerovat větnou formu 1025*1 a v dalším kroce IO2OS3, ale naopak nelze vygenerovat 1025*0, ani IO2S2.
G = ({S0, Si, S2, S3, S4}, {0,1, 2}, P, S0), kde
P = {S0	0S0		2S2 1	0
Si			2^0 1	2
S2	OSi	1S2		
S3	0S4	ISo	2Si 1	1
S4.	^os2	IS3	2S4}