Gramatika vo formálnych jazykoch

Ako definujeme a tvoríme pravidlá pre gramatiky vo formálnych jazykoch?

Gramatika

V predošlých pojmoch sa vyskytla aj gramatika. Gramatika $G$ generuje iba slová ktoré patria do jazyka $L$ a žiadne iné (syntéza).

Gramatika je definovaná ako štvorica ($G=(N,T,P,S)$), kde:

• ˆ$N$ je konečná neprázdna množina neterminálnych symbolov,
• $T$ je konečná neprázdna množina terminálnych symbolov, pričom $N\cap T=\mathrm{\varnothing }$ (to znamená, že tieto dve množiny nemajú spoločný žiadny symbol - symbol nemôže byť zároveň aj terminálny aj neterminálny),
• ˆ$P$ je konečná neprázdna množina pravidiel v tvare $\alpha \to \beta$, kde:
  • ľavá strana pravidiel $\alpha$ je ľubovoľný reťazec obsahujúci aspoň jeden neterminálny symbol $\alpha \in (N\cup T{)}^{*}N(N\cup T{)}^{*}$, a
  • pravá strana pravidiel $\beta$ je ľubovoľný reťazec $\beta \in (N\cup T{)}^{*}$,
• ˆ$S\in N$ je začiatočný neterminálny symbol.

Definícia môže vyzerať naozaj strašne pre niekoho kto nevie čítať matematické zápisy. V takom prípade stačí, ak si zapamätá:

1. Pomocou gramatiky generujeme nejaké slovo ktoré jednoznačne patrí iba do jedného konkrétneho jazyka (napríklad: môžeme definovať gramatiku pre generovanie čísiel od 0 po 9 a naše pravidlá zabezpečia že výsledok bude vždy iba nejaké číslo, nie napríklad písmeno);
2. Gramatika funguje tak, že najskôr definujeme pravidlá pre postupné nahrádzanie dočasných (neterminálnych) symbolov konkrétnymi konečnými (terminálnymi) symbolmi;
3. Vždy definujeme neterminálny symbol, z ktorého vychádzame. Ak nezostane nič, čo by sme mohli nahradiť, máme výsledok;

Príklad

Poďme si gramatiku ukázať na príklade. Zadanie hovorí, že máme definovať gramatiku $G$, ktorá bude generovať jednocifernú číslicu od nula po desať.

Našu gramatiku definujeme ako $G=(N,T,P,S)$ (v preklade: gramatika $G$ je štvorica $N$eterminálnych a $T$erminálnych symbolov s $P$ravidlami a začiatočným neterminálnym symbolom - teda substitučným symbolom, s ktorým začíname - a tento symbol má označenie $S$. Môžeme zvoliť akékoľvek označenie, ale najčastejšie sa používa S).

Teraz definujeme jednotlivé "písmená" z našej "NTPS" štvorice:

$\begin{array}{rl}N& =\{S\}\\ T& =\{0,1,2,3,4,5,6,7,8,9\}\end{array}$

Čo zápis vyššie znamená?

• $N$ predstavuje množinu neterminálnych symbolov. Je to zoznam symbolov, ktoré môžeme nahradiť niečím iným.
• $T$ predstavuje množinu terminálnych symbolov. Sú to všetky symboly, z ktorých môže byť tvorené nejaké slovo

Ak ešte nechápeš čo sa tu deje, skúsime si to vysvetliť na pravidlách:

$$\begin{array}{r}P:\\ S& \to 0& S& \to 4& S& \to 8\\ S& \to 1& S& \to 5& S& \to 9\\ S& \to 2& S& \to 6\\ S& \to 3& S& \to 7\\ \end{array}$$

Definovali sme najdôležitejšiu časť každej gramatiky: pravidlá, pomocou ktorých sa symboly prepisujú na iné. Šípku ($\to$) čítame ako "symbol x sa prepíše na y".

Úplná definícia našej gramatiky (ktorá generuje práve jednu číslicu od nula po desať) vyzerá nasledovne:

$\begin{array}{rl}G& =(N,T,P,S)\\ N& =\{S\}\\ T& =⟨0,9⟩\\ \end{array}\begin{array}{r}\\ \end{array}$

$\begin{array}{rlrlrl}P:S& \to 0& S& \to 4& S& \to 8\\ S& \to 1& S& \to 5& S& \to 9\\ S& \to 2& S& \to 6\\ S& \to 3& S& \to 7\\ \end{array}$

Poďme skúsiť vygenerovať čislicu 4. Za začiatočný neterminálny symbol sme zvolili $S$ (je to posledný symbol zo štvorice v definícií našej gramatiky $G$, preto sme ho zvýraznili), takže týmto symbolom musíme aj začať. Čo bude nasledovať ďalej? Musíme tento symbol nahradiť niečím za šípkou v pravidlách (preto sa zápis "$S\to \dots$" číta ako "S sa prepíše na ..." - pretože sa skutočne prepíše na niečo iné... duh).

V zozname našich pravidiel vidíme pravidlo "$S\to 4$". A to je vlastne všetko a máme číslicu 4 ktorú sme chceli. Musíme to ale matematicky zapísať:

$$S\Rightarrow 4$$

Dôležité je použiť dvojitú šípku ($\Rightarrow$) namiesto jednoduchej ($\to$), pretože dvojitá šípka predstavuje takzvaný "krok odvodenia". Znamená to že sme prepísali neterminálny symbol S na 4. V jednom kroku môžeme použiť maximálne jedno pravidlo (teda, môžeme prepísať iba jeden neterminálny symbol na terminálny, nemôžme prepísať viacej symbolov naraz).

Slovo bolo vygenerované našou gramatikou správne, ak sa vo výsledku nenachádza žiadny neterminálny symbol (v našom prípade za neterminálny symbol podľa definície považujeme iba $S$). Vo výsledku sa za dvojitou šípkou nachádza iba 4, čo je symbol ktorý sme definovali v našej množine terminálnych symbolov ($T=⟨0,9⟩$). Znamená to, že naše slovo "4" patrí do našej gramatiky $G$, pretože tento výsledok obsahuje iba terminálne (konečné) symboly.

Čo dokážeme s gramatikou?

Príklad vyššie bol veľmi jednoduchý. Prepísali sme iba jeden neterminálny symbol na nejakú číslicu, a mali sme výsledné slovo z nášho jazyka číslic. Ale čo ak by sme mali za úlohu vytvoriť gramatiku ktorá bude generovať akékoľvek prirodzené číslo (celé číslo, ktoré je väčšie ako nula)?

Využijeme gramatiku z predchádzajúceho príkladu. Musíme ju avšak zmeniť tak, aby sme dokázali vygenerovať viac ako jeden symbol.

Skúsme sa pozrieť na takéto pravidlá:

$$\begin{array}{r}P:\\ S& \to 0\\ S& \to 1& S& \to 4& S& \to 7\\ S& \to 2& S& \to 5& S& \to 8\\ S& \to 3& S& \to 6& S& \to 9\\ \end{array}$$

Tieto pravidlá nám umožnia generovať číslo od 0 po 9. Avšak, ak musíme stále začať iba symbolom $S$, pravidlá nám povolia tento symbol prepísať iba na jednu z týchto číslic - nedokážeme vygenerovať viacciferné čísla.

Ak by nás hneď nenapadlo riešenie, pravdepodobne by sme skúsili čísla nejako premiestniť na ľavú stranu (pred šípkou) aby sme nejako vygenerovali viac ako jednu číslicu a táto postupnosť by vytvorila číslo. Avšak, toto nie je povolené (podľa definície gramatiky musí ľavá strana vždy obsahovať neterminálny symbol, teda v tomto prípade naše $S$).

Riešenie v skutočnosti spočíva v rekurzií. Aby bolo riešenie čitateľné, musíme naše pravidlá trochu zmeniť:

$$\begin{array}{r}P:\\ S& \to cS& S& \to ϵ\\ c& \to 1& c& \to 4& c& \to 7\\ c& \to 2& c& \to 5& c& \to 8\\ c& \to 3& c& \to 6& c& \to 9\\ \end{array}$$

Takto definované pravidlá patria gramatike, ktorá dokáže vygenerovať akékoľvek kladné celé číslo, ktoré neobsahuje nulu (zatiaľ sme tento prípad vynechali pre jednoduchosť). Pribudol nám nový neterminálny symbol $c$ (ako "číslo" - môžeme si zvoliť ľubovoľný symbol, dokonca by sme mohli pravidlá vyjadriť aj celým slovom, napríklad: $\text{číslo}\to \dots$, ale potom by bol zápis dlhý, preto to nebudeme komplikovať).

Zároveň sme pridali dve nové pravidlá pre neterminálny symbol $S$, kde využívame rekurziu:

• Symbol $S$ sa môže prepísať na číslo $c$, alebo sám na seba;
• Symbol $S$ sa môže prepísať na prázdne slovo (ktoré označujeme ako $ϵ$).

Poďme skúsiť vyjadriť číslo "123":

$$\begin{array}{lllll}\text{1.}& S& \Rightarrow & cS& \Rightarrow \\ \text{2.}& 1S& \Rightarrow & 1cS& \Rightarrow \\ \text{3.}& 12S& \Rightarrow & 12cS& \Rightarrow \\ \text{4.}& 123S& \Rightarrow & 123ϵ\\ \text{5.}& \Rightarrow 123\end{array}$$

To už vyzerá komplikovanejšie. Vysvetlíme si jednotlivé kroky:

1. V prvom kroku sme začali so symbolom $S$, ktorý sme prepísali na $cS$. Využili sme pritom prvé pravidlo ($S\to cS$). Tým sme zabezpečili to, že môžeme $c$ nahradiť číslicou, za ktorou bude nasledovať ďalšie $S$;
2. Za číslom ktoré sme nahradili nám zostalo opäť $S$, s ktorým sme aj začínali. Preto môžeme spraviť presne to isté, a $S$ prepísať opäť na $cS$;
3. $c$ sme nahradili číslicou 2. Posledný krát spravíme to isté, čo v predchádzajúcich krokoch odvodenia a opäť nahradíme $S$ za $cS$;
4. Posledný neterminálny symbol $c$ (ktorý zostal z tretieho kroku) sme prepísali na číslicu 3, čo je posledná číslica ktorú potrebujeme aby sme vytvorili číslo "123". Avšak, zostal nám tam stále symbol $S$, ktorý nasledoval za $c$. Pre to, aby bolo naše číslo platné, tak výsledok nesmie obsahovať neterminálny symbol $S$ - musíme tento symbol nejako odstrániť.
   • V tomto kroku využijeme druhé nové pravidlo, ktoré sme definovali ($S\to ϵ$) a $S$ prepíšeme na prázdne slovo $ϵ$. V tomto spočíva zmysel prázdneho slova, pretože predstavuje naozaj "nič" - už máme naše číslo 123, preto $S$ nahradíme "ničím", čím tento nadbytočný symbol v podstate odstránime;
5. Výsledné slovo je "123". Toto číslo skutočne patrí do jazyka prirodzených čísel väčších ako nula, takže naša gramatika je definovaná správne.

Avšak, ak chceme povoliť aj generovanie čísiel ktoré obsahujú nulu, pravidlá musíme opäť upraviť. Tu je hlavným problémom to, že viacciferné čísla nemôžu začínať nulou, inak to sú neplatné čísla (napr.: nemôžme vytvoriť číslo "0123", nula na začiatok nepatrí).

Aby pravidiel nebolo priveľa, používa sa symbol "alebo" (zvyslá čiara: |). Pravidlá vyššie teda môžeme zapísať aj ako:

$$\begin{array}{r}P:\\ S& \to cS|ϵ\\ c& \to 1|2|\dots |9\end{array}$$

Jedná sa o ekvivalentný zápis, ktorý je totožný s naším pôvodným zápisom. Pravidlá hovoria, že neterminálny symbol $S$ sa môže prepísať ako $cS$ alebo $ϵ$ (prázdne slovo). Ďalej sa $c$ môže prepísať na 1, alebo 2, až po 9.

Poďme ale konečne pridať pravidlo pre generovanie núl:

$$\begin{array}{r}P:\\ S& \to 1c|2c|\dots |9c\\ c& \to 0c|1c|\dots |9c|ϵ\end{array}$$Začíname zo symbolu $S$, ktorý sa môže prepísať na čísla od 1 po 9, za ktorými nasleduje $c$. Tento symbol $c$ môžeme potom ľubovoľne kombinovať, až pokým ho nenahradíme prázdnym slovom, čo ukončí generovanie nášho slova.

« Úvod do formálnych jazykov

Chomského hierarchia jazykov »