Wersja z 03:50, 3 lis 2009 edytuj Loveless (dyskusja \| edycje) 69 231 edycji m robot dodaje: sv:Formella språk ← poprzednia edycja		Wersja z 11:37, 4 lis 2009 edytuj anuluj edycję Xqbot (dyskusja \| edycje) Boty 327 507 edycji m robot poprawia: bg:Формален език (математика); zmiany kosmetyczne następna edycja →
Linia 17: 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 [[alfabet]]u. 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, [[komputer]]y 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. == Alfabet == Linia 32: '''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 pusty, oraz język zawierający tylko słowo puste. * zbiory nieskończone, np. zbiór wszystkich [[Liczby naturalne\|liczb naturalnych]], czy [[Liczby rzeczywiste\|rzeczywistych]] Linia 95: == 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. [[hierarchia Chomsky'ego\|hierarchię Chomsky'ego]]. Linia 120: [[ar:لغة شكلية]] [[bs:Formalni jezik]] [[bg:Формален език (математика)]] [[cs:Formální jazyk]] [[da:Formelt sprog]]

Język formalny: Różnice pomiędzy wersjami