Szukaj

narzędzia

Język formalny

Język formalny – jedno z najważniejszych pojęć w informatyce teoretycznej, logice matematycznej, metodologii nauk dedukcyjnych.

Wybierzmy pewien 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ż "myzmyz" czy słowo puste "", oznaczane też symbolem $ε$ .

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:

zbiór wszystkich słów złożonych z liter polskiego alfabetu i występujących w pewnym słowniku
zbiór takich słów złożonych z cyfr od 0 do 9, które przedstawiają liczbę pierwszą
zbiór słów złożonych z zer i jedynek, w których zer jest więcej niż jedynek
zbiór prawidłowo napisanych równań matematycznych
zbiór programów, które po skompilowaniu i uruchomieniu zawieszą dany komputer
zbiór pusty

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 naturalnych – język, słowo, alfabet, gramatyka itd. – to języki formalne są tworami matematycznymi i posiadają jedynie bardzo odległą i praktycznie ograniczoną relację do języków naturalnych jak np. polski czy bułgarski.

Spis treści

[edytuj] Alfabet

Alfabetem może być dowolny skończony zbiór. Do częściej używanych należą:

zbiór liczb całkowitych należących do jakiegoś przedziału, np. 0 i 1, albo od 0 do 9
zbiór wszystkich bądź niektórych liter alfabetu łacińskiego
zbiór symboli ASCII
zbiór złożony z dokładnie jednego symbolu

Choć równie dobrze może to być np.:

zbiór kart do gry
zbiór złożony z możliwych wartości koloru piksela (trójki liczb całkowitych, od 0 do 255 każda)
zbiór złożony z obrazka kwiatka i obrazka pingwinka

Nie mogą to być za to:

zbiór pusty - nie dało by się z niego ułożyć żadnego słowa. Jeśli jednak koniecznie chcemy móc tworzyć takie języki, można rozszerzyć definicję języka formalnego na ten przypadek – wtedy istniałoby tylko jedno słowo – słowo puste – i tylko dwa języki – język absolutnie pusty, oraz język zawierający tylko słowo puste.
zbiory nieskończone, np. zbiór wszystkich liczb naturalnych, czy rzeczywistych

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.

[edytuj] 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 zbioru tych słów – 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.

[edytuj] Gramatyki formalne

Najważniejszym sposobem opisywania języków formalnych są gramatyki formalne. Opis w postaci gramatyki składa się z:

Opisania, symbole jakiego alfabetu są używane przez język. Są to tzw. symbole terminalne.
Wyboru dowolnego skończonego zbioru symboli pomocniczych, tzw. symboli nieterminalnych
Wyboru z symboli nieterminalnych jednego symbolu startowego
Wyboru pewnego skończonego zbioru reguł przepisywania (zwanych też produkcjami). Każda z reguł składa się z jednego słowa będącego lewą stroną reguły, oraz drugiego będącego prawą stroną. Reguły zapisuje się w postaci $\alpha \rightarrow \beta$ .

Do tak opisanego języka należy każde słowo, dla którego potrafimy zbudować taki ciąg, że:

pierwszym elementem ciągu jest słowo złożone z symbolu startowego
każde następne słowo powstało przez:
- wybranie dowolnego fragmentu poprzedniego słowa, które jest równe lewej stronie dowolnej reguły
- i zamienienie go na prawą stronę tej samej reguły
ostatnim elementem ciągu jest dane słowo

[edytuj] Przykładowa gramatyka

alfabet składa się z 0 i 1
symbole pomocnicze to $A$ , $B$ i $C$
symbolem startowym jest $A$
reguły przepisywania to:
- $A \rightarrow BC$
- $A \rightarrow CB$
- $B \rightarrow 0B0$
- $C \rightarrow 1C1$
- $B \rightarrow 0$
- $C \rightarrow 1$

Przykładowe wyprowadzenie słowa $00011111$ w tej gramatyce:

$A$
$B C$ ( $A \rightarrow BC$ )
$0 B 0 C$ ( $B \rightarrow 0B0$ )
$0 B 01 C 1$ ( $C \rightarrow 1C1$ )
$0 B 011 C 11$ ( $C \rightarrow 1C1$ )
$00011 C 11$ ( $B \rightarrow 0$ )
$00011111$ ( $C \rightarrow 1$ )

[edytuj] 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 \not\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.

[edytuj] 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.

Dowolne gramatyki – do testowania przynależności można użyć np. maszyny Turinga, programów komputerowych czy rachunku lambda
Gramatyki kontekstowe – niedeterministyczne maszyny Turinga działające w przestrzeni liniowej (NLINSPACE)
Gramatyki bezkontekstowe – wystarczają niedeterministyczne automaty ze stosem
Gramatyki regularne – wystarczają deterministyczne lub niedeterministyczne automaty skończone, można też użyć wyrażeń regularnych.

[edytuj] Języki formalne a języki naturalne

Języki formalne są używane do opisu języków naturalnych, choć nie jest to łatwe. Od 1956 roku stosowane są np. tzw. gramatyki generatywne Chomskyego. Problemem jest kontekstowość języka naturalnego, tzn. zależność reguł gramatycznych, a szczególnie reguł interpretacji (semantyki) języka naturalnego od kontekstu, czyli sąsiednich zdań, a nawet wypowiedzi bezpośrednio z daną nie sąsiadujących.

Aktualnie istnieje wiele systemów komercyjnych przetwarzających język naturalny. Tłumaczenie wolnego tekstu jest bardzo niedokładne, pozwala jednak zrozumieć treść i wspomaga pracę tłumaczy (przyspieszenie nawet 4 razy). Lepsze wyniki zostały osiągnięte w tłumaczeniu tekstów specjalistycznych^[1]

Przypisy

↑ http://hermes.kie.ae.poznan.pl/~tomek/didactics/SSI/materialy/NLP.ppt

[edytuj] Linki zewnętrzne

Języki, automaty i obliczenia (materiały dydaktyczne MIMUW na studia informatyczne I stopnia)
Semantyka i weryfikacja programów (materiały dydaktyczne MIMUW na studia informatyczne II stopnia)

Źródło: "http://pl.wikipedia.org/wiki/J%C4%99zyk_formalny"