Pokročilé úlohy pre tvorbu gramatík

Táto stránka bude venovaná iba riešeným úlohám pre tvorbu gramatík z hľadiska formálnych jazykov. Najskôr sa ich pokús vyriešiť sám, potom si riešenie skontroluj. Alebo iba sleduj...

Regulárne gramatiky

Predpokladá sa, že výsledné riešenie nasledovných úloh bude regulárna gramatika, definovaná ako $G = (N, T, P, S)$ .

1. úloha

Zadanie: Zostrojte gramatiku, ktorá generuje 2-ciferné alebo 5-ciferné prirodzené čísla deliteľné 5.

Riešenie 1. úlohy

Pri riešení zložitejších úloh je dobrý nápad vymenovať si niektoré slová, ktoré patria do jazyka ktorý by mala naša gramatika generovať - to zabezpečí, že nezabudneme náhodou pridať nejaké pravidlo. Pre zadanie vyššie to môže byť napríklad 10, 55, 12 345, ale nie 5, 13, 125 a podobne.

Vypadá to, že budeme potrebovať pravidlá, pri ktorých budeme môcť zastaviť generovanie pri druhej a piatej cifre, s tým že táto cifra bude buď nula alebo päťka. Riešenie by teda mohlo byť takéto:

$\begin{aligned} G & = (N, T, P, S) \\ N & = {S, c_{1}, c_{2}, c_{3}, c_{4}, c_{5}} \\ T & = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} \\ P : \\ S & \to 1 c_{2} | 2 c_{2} | \dots | 9 c_{2} \\ c_{2} & \to 0 | 5 | 0 c_{3} | 1 c_{3} | \dots | 9 c_{3} \\ c_{3} & \to 0 c_{4} | 1 c_{4} | \dots | 9 c_{4} \\ c_{4} & \to 0 c_{5} | 1 c_{5} | \dots | 9 c_{5} \\ c_{5} & \to 0 | 5 \end{aligned}$

Trik spočíva v tom, že indexy pri neterminálnom symbole $c$ predstavujú aktuálny počet cifier v našom čísle. Pri pravidle $c_{2}$ (teda, dvojcifernom čísle) si teda môžeme vybrať či chceme skončiť nulou alebo päťkou alebo pokračovať ďalšími ciframi až po $c_{5}$ , kde už musí byť číslo jasne deliteľné päťkou (teda, musí sa končiť nulou alebo päťkou).

Toto zabezpečí, že dokážeme odvodiť iba slová ktoré patria do nášho jazyka dvojciferných alebo päťciferných čísiel ktoré sú deliteľné päťkou.

2. úloha

Zadanie: Navrhnite regulárnu gramatiku, ktorá generuje jazyk $L = {x \in N; n \geq 255}$ .

Riešenie 2. úlohy

Odporúčané je skamarátiť sa s matematickými zápismi. Zadanie chce všetky prirodzené čísla (to znamená, čísla väčšie ako nula) ktoré sú zároveň väčšie alebo rovné ako 255. To znamená, že hľadáme čísla: 255, 256, 257, 258, 259, 260 a tak ďalej, až donekonečna... V zadaní je zároveň požiadavka, že sa má jednať o regulárnu gramatiku - teda, pravidlá musia byť zapísané vo forme, kde na ľavej strane je práve jeden neterminálny symbol a na pravej strane jeden terminálny symbol za ktorým nasleduje práve jeden neterminálny symbol.

Jedno z mnohých riešení by mohlo vyzerať napríklad takto:

$\begin{aligned} G & = (N, T, P, S) \\ N & = {S, c_{1}, c_{2}, c_{3}, d, p} \\ T & = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} \\ P : \\ S & \to 1 c_{1} | 2 d | 3 c_{2} | 4 c_{2} | \dots | 9 c_{2} \\ c_{1} & \to 0 c_{2} | 1 c_{2} | \dots | 9 c_{2} \\ c_{2} & \to 0 c_{3} | 1 c_{3} | 2 c_{3} | \dots | 9 c_{3} \\ c_{3} & \to 0 c_{3} | 1 c_{3} | \dots | 9 c_{3} | 0 | 1 | 2 | \dots | 9 \\ d & \to 0 c_{2} | 1 c_{2} | 2 c_{2} | 3 c_{2} | 4 c_{2} | 5 c_{2} | 6 c_{3} | \dots | 9 c_{3} | 5 p \\ p & \to 5 | 6 | 7 | 8 | 9 \end{aligned}$

Poďme si vysvetliť, ako to funguje:

Máme neterminálne symboly c1, c2, c3 ("c" ako "číslo" - aby sme sa vedeli v pravidlách lepšie orientovať). Podobne ako v predchádzajúcich úlohách, index predstavuje v tomto prípade číslo kroku (do čísla ktoré je väčšie ako 255). Inými slovami, povedzme že začíname číslom 1. Aké najmenšie číslo sa začína na 1 a je väčšie ako 255? Jediná možnosť je číslo 1 000 (keďže 1, 10 a 100 sú menšie ako 255, nemôžme našej gramatike povoliť odvodenie takýchto čísel):
- $1 c_{1}$ hovorí, že sme na prvom kroku od vytvorenia čísla ktoré je väčšie ako 255 (aktuálne číslo kroku vieme zistiť z indexu, teda: $c \color_{1}$ ). Celkový počet krokov je 3 ( $c_{3}$ ), preto ešte musíme spraviť ďalšie dva kroky aby sme vytvorili najmenšie číslo ktoré má na začiatku 1 a je väčšie ako 255 (inými slovami, musíme pridať ešte ďalšie dve cifry aby bolo číslo v poriadku a aby sme vytvorili napr. 1 000).
- $2 d$ hovorí, že číslo začína dvojkou a pokračuje niečím ďalším. V tomto prípade sa môžme rozhodnúť, že či chceme vygenerovať trojciferné číslo (255 až po 299) alebo viacciferné (napr.: 2 500, 29 857, a podobne). Túto vetvu pravidiel si vysvetlíme neskôr.
- Pokračujeme číslami 3 až 9 ( $3 c_{2} | 4 c_{2} | \dots | 9 c_{2}$ ). Tu sme využili už $c_{2}$ - povieme, že sme hneď na druhom kroku, a teda už nám stačí pridať iba 2 cifry aby to bolo číslo väčšie ako 255. Napríklad, ak začneme číslom 4, tak stačí pridať minimálne 2 čísla a máme trojciferné číslo väčšie ako 255, napr. 432. Ak by sme namiesto $c_{2}$ zvolili $c_{1}$ , naša logika ktorú sme definovali v $c_{1}$ by nás prinútila doplniť ešte 3 čísla, a nemohli by sme vygenerovať napr. číslo 432.
Pravidlá pre $c_{1}$ , $c_{2}$ a $c_{3}$ iba hovoria o tom, že môžeme generovať čísla od 0 po 9 až po pravidlo $c_{3}$ . V pravidle $c_{3}$ nám už je jedno, koľko čísel bude nasledovať, potom už môžme využiť rekurziu a generovať čísla až pokým nezvolíme posledné číslo bez neterminálneho symbolu na konci (táto časť pravidla: $0 | 1 | 2 | \dots | 9$ ). Tam sa generovanie slova ukončuje, pretože už nemáme ako pokračovať.
Pravidlo d (ako "dva", čiže to znamená že začíname dvojkou) je špecifické iba pre prípad, ak začíname s dvojkou. Môžu nastať 3 prípady:
- Pokiaľ chceme vygenerovať viac cifier ako trojciferné čísla (2 000 a vyššie), vybrali by sme si napríklad túto cestu: $2 d \Rightarrow 20 c_{2} \Rightarrow 200 c_{3} \Rightarrow 2000$ , alebo: $2 d \Rightarrow 26 c_{3} \Rightarrow 260 c_{3} \Rightarrow 2600$ , a podobne.
- Pokiaľ chceme vygenerovať dvojciferné číslo od 255 po 259, zvolili by sme napríklad: 2d⇒25p⇒256.
  - Poznámka: "p" ako "(dvesto)päťdesiat".
- Ak chceme vygenerovať čísla 260 až 299, zvolíme napr.: $2 d \Rightarrow 27 c_{3} \Rightarrow 275$ .
- Toto pravidlo $d$ obsahuje všetky tri cesty, ktorými by sme sa mohli vybrať aby sme vygenerovali číslo väčšie ako 255.
Pri tvorbe pravidiel musíme dávať pozor aj na to, že sa dajú odvodiť čísla ako napríklad 2 555. Toto má za dôsledok malú repetíciu pravidiel a podobné vzory, ale je to z dôvodu aby bola naša gramatika definovaná správne a neumožnila generovať napr. iba číslo 25 (ktoré nepatrí do zadaného jazyka). Inými slovami, pri riešení úloh nevadí že je tam niekedy repetícia. V prvom rade je dôležité nájsť funkčné riešenie, ktoré sa môže optimalizovať neskôr.

« Chomského hierarchia jazykov

Formálne automaty (konečné) »