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\ge 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{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ť). 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).
  • $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).
  • $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é) »