Gramatyki Formalne cz II 1

TEORIA JĘZYKÓW I GRAMATYK FORMALNYCH CZĘŚĆ II

Rozważmy kilka przykładów gramatyk:

Przykład 1:

Gramatyka generuje słowa złożone tylko z jednego symbolu ą, który ma w słowie wystąpić zawsze parzysta ilość razy czyli a²ⁿ.

Niech G = { {S}. {a}, P. S}. gdzie P ={S - aaS, S ♦ aa}

Wygenerujemy słowo aaaaaa S =?• aaS =?■ aaaaS =*• aaaaaa

Użyliśmy 2 razy pierwszej produkcji i 1 raz drugiej. Otrzymaliśmy słowo spełniające wymaganie, czyli należące do języka.

Przykład 2:

Gramatyka generuje słowa złożone z dwóch symboli ą i b, które mają w nich wystąpić tę samą ilość razy czyli w postaci aⁿ bⁿ.

Niech G = {{S}. {a, !>}, P. S}. gdzie P = {S ♦ aSb, S -* ab}

Wygenerujemy słowo aaa bbb S =*• aSb =*• aaSbb =?• aaabbb

Użyliśmy 2 razy pierwszej produkcji i 1 raz drugą. Otrzymaliśmy słowo należące do języka.

Każde słov-/o zbudowane z symboli terminalnych i otrzymane przez wielokrotne zastosowanie produkcji począwszy od symbolu startu — to słowo generowane przez gramatykę. Zbiór wszystkich słów generowany przez dana gramatykę nazywamy jeżykiem geneiownnym pizez te cnamatvke.

Zgodnie z powyższym, język polski to ogół zdań generowanych zgodnie z regułami gramatyki. Zaś język programowania PASCAL, to zbiór wszystkich tekstów wygenerowanych według reguł budowy tego języka (czyli przez gramatykę tego języka).

Woźne! Interesuje nas tu tylko składnia, a nie znaczenie wypowiedzi - bardziej przecież istotne.

Podział gramatyk formalnych:

Dotąd rozważaliśmy produkcje, gdzie po levyej stronie występował pojedynczy symbol nieterminalny. Zatem odpowiedniego podstawiania można było dokonać bez względu na kontekst, w jakim ów symbol nieterminalny wystąpił. Takie gramatyki noszą nazwę hezkontekstowych. Istnieje znacznie szersza klasa tzw. giamatyk kontekstowych, gdzie o możliwości użycia danej produkcji decyduje kontekst, w jakim podstawiany symbol występuje.

Czasem można uprościć gramatykę bezkontekstoyyą. Polega to na takim uproszczeniu produkcji, że po prawej stronie występuje tylko pojedynczy symbol terminalny albo paia: symbol terminalny — symbol nieteimin.ilny Taką gramatykę nazywamy liniowa hemilamal