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 nezáporné desatinné čísla s aspoň jedným desatinným miestom.

Riešenie 1. úlohy

Musíme zahrnúť aj prípad, keď máme na ľavej strane iba nulu, napr.: 0.0123 a zároveň nesmieme povoliť odvodenie napr. 00.123 alebo 0.12300, pretože nuly na ľavej a pravej strane slova sú nadbytočné.

Potenciálne riešenie (jedno z mnohých):

$\begin{array}{rl}G& =(N,T,P,S)\\ \\ N& =\{S,c_0,c_1,c_d,d,o\}\\ T& =\{.,0,1,2,3,4,5,6,7,8,9\}\\ P:\\ S& \to 0d|c_0\\ c_0& \to 1c_1|2c_1|\dots |9c_1\\ c_1& \to 0c_1|1c_1|2c_1|\dots |9c_1|d\\ d& \to .c_d\\ c_d& \to 0c_d|1c_d|2c_d|\dots |9c_d|1|2|\dots |9\\ \end{array}$

V množine terminálnych symbolov ($T$) nesmieme zabudnúť pridať okrem čísiel aj desatinnú čiarku (.), inak bude definícia neplatná!

Ako fungujú pravidlá?

• V neterminálnom symbole $S$ (kde začíname), si môžme zvoliť či chceme generovať desatinné číslo, kde celá časť je nula ($0d$) alebo chceme generovať nejaké iné číslo, ktoré môže mať ľubovoľný počet cifier ($c_0$).
• Ak si zvolíme cestu čísla väčšieho ako nula ($c_0$), potom si musíme ako prvú cifru zvoliť nenulové číslo (pretože nemôžme generovať napr. 0123.1).
  • Ďalej pokračujeme do $c_1$, kde už môžeme rekurzívne generovať akúkoľvek cifru potrebujeme, vrátane nuly (aby sme mohli generovať veľké čísla, napr. 12804007330700.123). Pre prechod na desatinnú časť prejdeme do $d$.
  • Pravidlo $c_0$ by sa dalo aj "zjednodušiť" a zlúčiť s pravidlom $S$ (teda by sme ho definovali ako $S\to 0d|1c_1|2c_1|\dots |9c_1$ a odstránili pravidlo $c_0$, ktoré by sa tým pádom stalo nadbytočným). Ale keďže sa učíme, je lepšie mať v pravidlách prehľad ako snažiť sa ich čo najviac stlačiť a zredukovať.
• $d$ predstavuje prechod do desatinnej časti. Teda, musíme dopísať desatinnú čiarku (.) a pokračovať samotnými číslami v desatinnej časti, do pravidla $c_d$.
• V pravidle $c_d$ už môžeme obmieňať ľubovoľne všetky čísla v rekurzii, pričom desatinné číslo musí mať na konci 1 až 9 (nie nulu).

2. úloha

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

Riešenie 2. ú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{array}{rl}G& =(N,T,P,S)\\ \\ N& =\{S,c_2,c_3,c_4,c_5\}\\ T& =\{0,1,2,3,4,5,6,7,8,9\}\\ P:\\ S& \to 1c_2|2c_2|\dots |9c_2\\ c_2& \to 0|5|0c_3|1c_3|\dots |9c_3\\ c_3& \to 0c_4|1c_4|\dots |9c_4\\ c_4& \to 0c_5|1c_5|\dots |9c_5\\ c_5& \to 0|5\\ \end{array}$

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.

3. úloha

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

Riešenie 3. ú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{array}{rl}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 1c_1|2d|3c_2|4c_2|\dots |9c_2\\ c_1& \to 0c_2|1c_2|\dots |9c_2\\ c_2& \to 0c_3|1c_3|2c_3|\dots |9c_3\\ c_3& \to 0c_3|1c_3|\dots |9c_3|0|1|2|\dots |9\\ d& \to 0c_2|1c_2|2c_2|3c_2|4c_2|5c_2|6c_3|\dots |9c_3|5p\\ p& \to 5|6|7|8|9\\ \end{array}$

Poďme si vysvetliť, ako to funguje:

• Máme neterminálne symboly $c_1$, $c_2$, $c_3$ ("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):
  • $1c_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{\mathrm{\backslash 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).
  • $2d$ 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 ($3c_2|4c_2|\dots |9c_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:$2d\Rightarrow 20c_2\Rightarrow 200c_3\Rightarrow 2000$, alebo: $2d\Rightarrow 26c_3\Rightarrow 260c_3\Rightarrow 2600$, a podobne.
  • Pokiaľ chceme vygenerovať dvojciferné číslo od 255 po 259, zvolili by sme napríklad: $2d\Rightarrow 25p\Rightarrow 256$.
    • Poznámka: "p" ako "(dvesto)päťdesiat".
  • Ak chceme vygenerovať čísla 260 až 299, zvolíme napr.: $2d\Rightarrow 27c_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é) »