Wersja z 13:09, 8 kwi 2015 edytuj PG (dyskusja \| edycje) Redaktorzy 159 897 edycji drobne redakcyjne ← poprzednia edycja		Wersja z 13:51, 8 kwi 2015 edytuj anuluj edycję Beno (dyskusja \| edycje) Redaktorzy, Administratorzy interfejsu, Administratorzy 133 052 edycje m drobne redakcyjne następna edycja →
Linia 1: {{Dopracować\|źródła=2013-09 }} '''Język formalny''' – [[podzbiór]] [[zbiór\|zbioru]] wszystkich słów nad skończonym alfabetem. Język formalny jest kluczowym pojęciem w [[informatyka\|informatyce]], [[logika matematyczna\|logice matematycznej]] i [[językoznawstwo\|językoznawstwie]]. Język formalny nie jest uściśleniem pojęcia [[język (mowa)\|języka naturalnego]] i nie powinien być z nim mylony. Linia 24: Alfabetami nie mogą być: * zbiór pusty -– nie dało by się z niego ułożyć żadnego słowa. Można jednak rozszerzyć definicję języka formalnego na ten przypadek – wtedy nad takim alfabetem istnieje 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ńczoność\|nieskończone]], np. zbiór wszystkich [[liczby naturalne\|liczb naturalnych]], czy [[liczby rzeczywiste\|rzeczywistych]]. === Słowo === Słowami są dowolne skończone ciągi symboli. Przykładowe słowa to: * [[słowo\|słowa]] języka naturalnego, np. "„''ala''"”, "„''słoneczko''"” (jeśli alfabet obejmuje litery), * słowo puste (nad dowolnym alfabetem), oznaczane <math>\epsilon</math>, * [[liczba]] zapisana w systemie [[dziesiętny system liczbowy\|dziesiętnym]] (jeśli alfabet obejmuje cyfry arabskie) lub [[rzymski system zapisywania liczb\|rzymskim]] (jeśli alfabet obejmuje znaki I, V, X, L, C, M, D), Linia 36: Słowami nie są: * ciągi o nieskończonej długości, np. reprezentacje [[liczby niewymierne\|liczb niewymiernych]] w systemie dziesiętnym -– choć już reprezentacje symboliczne, np. <math>\pi</math> -– są. * nieuporządkowane zbiory symboli, np. zbiór samogłosek. Linia 42: W niektórych zastosowaniach, przydatne jest operowanie na ciągach elementów z nieskończonego zbioru, np. zbioru liczb naturalnych. Zbiór takich ciągów nie jest językiem, ale to ograniczenie można obejść, jeśli tylko zbiór używanych elementów jest przeliczalny. Wtedy te elementy można przedstawić jako słowa nad skończonym alfabetem. Przykładowo, aby operować na ciągach liczb naturalnych, zapisuje się te liczby w sposób pozycyjny. Np. ciąg ~~"10~~„10 200 317 ~~852"~~852”, zawierający 14 symboli, należy do języka ciągów liczb naturalnych zapisanych w postaci pozycyjnej, za pomocą cyfr arabskich oraz spacji. == Metody definiowania języków == Dla każdego alfabetu (nawet jednoelementowego), liczba słów nad tym alfabetem jest '''nieskończona''' i [[zbiór przeliczalny\|przeliczalna]] (oznaczana <math>\aleph_0</math>). Liczba zbiorów słów (liczba języków), jest zatem [[zbiór nieprzeliczalny\|nieprzeliczalna]]. Ponieważ każda metoda opisania może objąć tylko przeliczalną liczbę elementów, nie istnieje metoda opisania wszystkich języków nad żadnym niepustym alfabetem. Dlatego opisuje się jedynie wybrane klasy języków. Przykładowo [[hierarchia ~~Chomsky'ego~~Chomsky’ego]] precyzuje cztery klasy języków, w zależności od tego jak złożona jest [[gramatyka formalna]] opisująca dany język. === Gramatyki formalne === Linia 82: === Należenie słowa do języka === Nie istnieje ogólna metoda, która dla danej gramatyki ~~formalej~~formalnej i danego słowa pozwoliłaby stwierdzić, czy dane słowo należy do języka opisywanego przez tę gramatykę. Wynika to z faktu, że gramatyki formalne mogą w szczególności definiować zachowanie [[maszyna Turinga\|maszyny Turinga]] i powyższy problem wymagałby rozwiązania [[problem stopu\|problemu stopu]]. Dlatego w praktycznych zastosowaniach używa się wybranych klas gramatyk, dla których taka weryfikacja jest możliwa do przeprowadzenia. W ogólności, im więcej języków potrafi opisać dana klasa gramatyk, tym problem tej weryfikacji ma większą złożoność. Przykładowo, [[hierarchia ~~Chomsky'ego~~Chomsky’ego]] wprowadza podział na następujące klasy, które można zdefiniować przez złożoność automatu rozpoznającego należenie do języka: * [[Gramatyka regularna\|Gramatyki regularne]] – rozpoznawalne przez [[automat skończony\|automaty skończone]], * [[Gramatyka bezkontekstowa\|Gramatyki bezkontekstowe]] – rozpoznawalne przez [[automat ze stosem\|automaty ze stosem]], Linia 92: == Języki formalne a języki naturalne == {{Osobny artykuł\|tłumaczenie automatyczne}} Języki formalne są używane do opisu języków naturalnych, choć nie jest to łatwe. Od 1956 roku stosowane są np. tzw. [[gramatyka generatywna\|gramatyki generatywne]] ~~Chomskyego~~Chomsky’ego. 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){{fakt\|data=2011-01}}. Lepsze wyniki zostały osiągnięte w tłumaczeniu tekstów specjalistycznych. == Linki zewnętrzne == * [http://wazniak.mimuw.edu.pl/index.php?title=J%C4%99zyki%2C_automaty_i_obliczenia Języki, automaty i obliczenia] (materiały dydaktyczne [[Wydział Matematyki, Informatyki i Mechaniki Uniwersytetu Warszawskiego\|MIMUW]] na studia informatyczne I stopnia) * [http://wazniak.mimuw.edu.pl/index.php?title=Semantyka_i_weryfikacja_program%C3%B3w Semantyka i weryfikacja programów] (materiały dydaktyczne [[Wydział Matematyki, Informatyki i Mechaniki Uniwersytetu Warszawskiego\|MIMUW]] na studia informatyczne II stopnia) [[Kategoria:Języki formalne\|*]]

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