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 bude definícia regulárnej gramatiky, definovaná ako $G = (N, T, P, S)$ .

1.

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

Riešenie

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 - index predstavuje čí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).
- $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 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:

$2 d \Rightarrow 25 p \Rightarrow 256$ .

- Ak chceme vygenerovať čísla 260 až 299, zvolíme napr.: $2 d \Rightarrow 27 c_{3} \Rightarrow 275$ .
- 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é) »