Czytaj więcej"/> Drukuj
Język formalny to jedno z najważniejszych pojęć w informatyce teoretycznej.
Wybierzmy jakiś skończony zbiór symboli, i nazwijmy go alfabetem. Dla przykładu może być to zwyczajny polski alfabet, złożony z liter a, ą, b, c, ć itd., choć może być nim np. zbiór cyfr od 0 do 9, czy też coś bardziej egzotycznego.
Z symboli takiego alfabetu możemy budować słowa – skończone ciągi symboli. Słowem nad alfabetem polskich liter jest więc "ala", "słoneczko", ale też "xyzxyz" czy słowo puste "", oznaczane też symbolem \[\epsilon \].
Język formalny to właśnie podzbiór zbioru wszystkich słów nad pewnym alfabetem.
Tak pojmowanym językiem może być więc: Za język możemy uważać każdy zbiór, jeśli tylko każdy jego element potrafimy opisać za pomocą skończenie wielu symboli jakiegoś wybranego przez nas alfabetu. Prawie wszystkie ciekawe zbiory, z jakimi spotykamy się w informatyce, mają tą właściwość – jeśli niemożliwe byłoby napisanie czegoś w skończonej ilości znaków, komputery nie potrafiłyby nic z tą rzeczą zrobić – zbiory nie dające się przedstawić w postaci języków istnieją więc niejako poza informatyką.
Uwaga: Chociaż w opisach języków formalnych używa się określeń zapożyczonych od języków naturalnychjęzyk, słowo, alfabet, gramatyka itd. – to języki formalne są tworami czysto matematycznymi, i nie mają żadnego związku z językami naturalnymi.

Alfabet

Alfabetem może być dowolny skończony zbiór. Do częściej używanych należą: Choć równie dobrze może to być np.: Nie mogą to być za to: Warunek skończoności alfabetu nie ogranicza nas zbytnio. Jeśli problem wymaga użycia zbioru nieskończonego, ale przeliczalnego (np. zbioru liczb naturalnych), możemy zamiast symbolu z tego zbioru, napisać numer tego symbolu.
Dla przykładu, jak wyglądałby język takich skończonych ciągów liczb naturalnych, które są rosnące ? Najprościej byłoby użyć jako alfabetu zbioru liczb naturalnych, i słowem tego języka byłoby na przykład "10 200 317 852" (4 symbole). Ponieważ nie wolno nam używać jako alfabetu zbioru nieskończonego, napiszmy każdą liczbę w postaci rzędu cyfr, i oddzielmy je jakimś separatorem. Właściwie już to zrobiliśmy – "10 200 317 852" (14 symboli) można zinterpretować jako słowo nad alfabetem złożonym z cyfr arabskich oraz spacji.

Języki

Dla każdego alfabetu, choćby jednoelementowego, ilość możliwych do ułożenia słów jest nieskończona, ale przeliczalna. Język formalny to dowolny podzbiór tego alfabetu – podzbiorów nieskończonego zbioru przeliczalnego jest zaś nieprzeliczalnie wiele – tyle co liczb rzeczywistych.
Jeśli chcemy opisywać języki formalne za pomocą dowolnych skończonych opisów, niezależnie od tego jak pomysłowej postaci, jesteśmy w stanie opisać co najwyżej przeliczalnie wiele z nich – a więc niezależnie od sposobu opisu prawie wszystkie języki są niemożliwe do opisania !

Gramatyki formalne

Najważniejszym sposobem opisywania języków formalnych są gramatyki formalne. Opis w postaci gramatyki składa się z: Do tak opisanego języka należy każde słowo, dla którego potrafimy zbudować taki ciąg, że: Przykładowa gramatyka: Przykładowe wyprowadzenie słowa \[00011111 \] w tej gramatyce:

Klasy gramatyk i inne metody opisu języków

Ale czy gramatyki formalne rzeczywiście są wystarczające do opisu wszystkich języków, które chcemy opisać ? Każda gramatyka formalna jest opisem skończonym, gramatyk formalnych jest więc przeliczalnie wiele (pomijając możliwość różnego oznaczenia zbiorów symboli terminalnych oraz nieterminalnych), więc nie wszystkie języki formalne da się opisać za pomocą gramatyk formalnych. Z drugiej strony gramatyki formalne są wystarczająco silnym narzędziem, by były w stanie opisać każdy język, który można opisać za pomocą programu do maszyny Turinga. Jeśli więc znaleźlibyśmy metodę, która potrafiłaby opisać więcej języków, i istniałby dla niej algorytm sprawdzający, czy dane słowo należy do takiego języka, dokonalibyśmy przy okazji przewrotu w teorii obliczeń.
O tym, że istnieją języki nie dające się przedstawić w postaci gramatyk, wiemy nie tylko z argumentu o liczeniu tych języków. Gramatyki to skończone opisy, więc można zbudować język wszystkich gramatyk.
Weźmy więc język \[L_x \] złożony z takich gramatyk \[g \], które opisują język \[L_g \] taki, że same nie należą do tego języka (\[g \in L_g \]). \[L_x \] potrafimy zdefiniować, ale czy potrafimy napisać dla niego gramatykę ? Załóżmy że potrafimy, i jest nią słowo \[x \].
Ale czy \[x \] należy do języka \[L_x \] ? Jeśli założymy że tak, to z definicji \[L_x \] oznacza to że \[x \not\in L_x \]. Jeśli zaś założymy że nie, to z definicji \[L_x \] jest \[x \in L_x \]. A więc z istnienia takiej gramatyki wynika sprzeczność – istnieje język, który potrafimy opisać, ale nie potrafimy dla niego napisać żadnej gramatyki. Nie jest to jednak problem gramatyk formalnych – jakiegokolwiek systemu obliczeń byśmy nie wybrali, zawsze potrafimy znaleźć język niemożliwy do zapisania w tym systemie.

Efektywność

Mając jednoznaczny opis języka, chcielibyśmy mieć też możliwie efektywną procedurę, która sprawdzałaby czy dane słowo należy do danego języka. Niestety, ogólne gramatyki formalne nie dostarczają nam takiej metody – skoro są równie silne jak maszyny Turinga, niektóre opisywane przez nie języki będą tylko semirozstrzygalne – jeśli dane słowo należy do języka, w końcu znajdziemy jego wyprowadzenie, jednak nie istnieje ogólna metoda stwierdzania, czy wyprowadzenie nie istnieje, czy też po prostu jeszcze go nie znaleźliśmy – niektóre zaś z tych rozstrzygalnych będą miały zbyt dużą złożoność obliczeniową – metoda będzie istniała, ale będzie o wiele za wolna.
Dlatego istnieje wiele innych metod opisu języków, które dostarczają bardziej efektywnych metod testowania przynależności danego słowa. Metody te są jednak z natury rzeczy mniej ogólne od gramatyk formalnych, i generalnie czym lepszą mają złożoność, tym mniej języków potrafią opisać. Wśród gramatyk formalnych wydziela się pewne klasy języków, które można opisać za pomocą automatów różnego typu – klasy te tworzą tzw. hierarchię Chomsky'ego.
Materiał wydrukowany z portalu zgapa.pl dnia 2020-04-05 20:48:28