Język formalny - Polski Serwis Naukowy

Język formalny – jest to podzbiór zbioru wszystkich słów nad skończonym alfabetem. Język formalny jest kluczowym pojęciem w informatyce, logice matematycznej i językoznawstwie. Język formalny nie jest uściśleniem pojęcia języka naturalnego i nie powinien być z nim mylony.

Formalna definicja

Aby zdefiniować język formalny, najpierw definiuje się alfabet, wybierając jakiś niepusty zbiór skończony. Elementy tego zbioru nazywane są symbolami. Ciągi symboli, o skończonej długości, nazywane są słowami. Dowolny zbiór takich ciągów nazywany jest językiem formalnym.

Podzbiór – pewna „część” danego zbioru, czyli dla danego zbioru, nazywanego nadzbiorem, zbiór składający się z pewnej liczby jego elementów, np. żadnego, jednego, wszystkich. Pierwszy przypadek nazywa się podzbiorem pustym, drugi – podzbiorem jednoelementowym lub singletonem, trzeci – podzbiorem niewłaściwym.
Język – ukształtowany społecznie system budowania wypowiedzi, używany w procesie komunikacji interpersonalnej. Na język składają się dwa elementy:

Przykłady języków formalnych:

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.

Alfabet

Alfabetem może być dowolny skończony zbiór. Przykładowe alfabety to:

Słownik – zbiór słów lub wyrażeń ułożonych i opracowanych według jakiejś zasady. Dzieli się na artykuły hasłowe ułożone w porządku alfabetycznym, rzadko tematycznym.
Ciąg – w matematyce pojęcie oddające intuicję ponumerowania, czy też uporządkowania elementów zbioru. W zależności od rodzaju elementów zbioru stosuje się różne nazwy: w przypadku liczb mówi się o ciągach liczbowych, bądź bardziej precyzyjnie, np. w przypadku zbioru liczb całkowitych, rzeczywistych czy zespolonych, ciąg nazywa się wtedy odpowiednio ciągiem całkowitoliczbowym, rzeczywistym i zespolonym. Jeśli elementami zbioru są funkcje, to ciąg nazywa się ciągiem funkcyjnym. Ciąg powstały poprzez wybranie elementów innego ciągu nazywa się podciągiem.

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.

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 wszystkich obrazów możliwych do wyświetlenia przy ustalonej rozdzielczości ekranu i liczbie kolorów.

Alfabetami nie mogą być:

Definicja intuicyjna: Maszyna Turinga stanowi najprostszy, wyidealizowany matematyczny model komputera, zbudowany z taśmy, na której zapisuje się dane i poruszającej się wzdłuż niej "głowicy", wykonującej proste operacje na zapisanych na taśmie wartościach.
Definicja intuicyjna: Język rekurencyjny to rodzaj języka formalnego, dla którego mając podane reguły jego składni, da się opracować automatyczny sposób sprawdzania, czy dane słowo jest zbudowane zgodnie z tymi regułami (tzn. należy do języka) czy nie.

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ńczone, np. zbiór wszystkich liczb naturalnych, czy rzeczywistych.

Słowo

Słowami są dowolne skończone ciągi symboli. Przykładowe słowa to:

Automat skończony (ang. finite state machine, FSM) to abstrakcyjny, matematyczny, iteracyjny model zachowania systemu dynamicznego oparty o tablicę dyskretnych przejść między jego kolejnymi stanami (diagram stanów).
Liczby naturalne – liczby służące podawaniu liczności (trzy osoby, zob. liczebnik główny/kardynalny) i ustalania kolejności (trzecia osoba, zob. liczebnik porządkowy), poddane w matematyce dalszym uogólnieniom (odpowiednio: liczby kardynalne, liczby porządkowe). Badaniem własności liczb naturalnych zajmują się arytmetyka i teoria liczb.

słowa języka naturalnego, np. "ala", "słoneczko" (jeśli alfabet obejmuje litery),

słowo puste (nad dowolnym alfabetem), oznaczane $\epsilon$ ,

liczba zapisana w systemie dziesiętnym (jeśli alfabet obejmuje cyfry arabskie) lub rzymskim (jeśli alfabet obejmuje znaki I, V, X, L, C, M, D),

wyrażenie algebraiczne,

film o dowolnej skończonej długości, wyświetlany na ekranie o ustalonej rozdzielczości i liczbie kolorów (jeśli alfabetem jest zbiór obrazów możliwych do wyświetlenia na tym ekranie).

Słowami nie są:

Logika matematyczna – dział matematyki, który wyodrębnił się jako samodzielna dziedzina na przełomie XIX i XX wieku, wraz z dążeniem do dogłębnego zbadania podstaw matematyki. Koncentruje się ona na analizowaniu zasad rozumowania oraz pojęć z nim związanych z wykorzystaniem sformalizowanych oraz uściślonych metod i narzędzi matematyki.
Informatyka (łac. informatio - "wyobrażenie", "wizerunek", "pomysł", ang. computer science, computing science, information technology, informatics) – dziedzina nauki i techniki zajmująca się przetwarzaniem informacji – w tym technologiami przetwarzania informacji oraz technologiami wytwarzania systemów przetwarzających informacje. Pierwotnie część matematyki, została rozwinięta do osobnej dyscypliny nauki, pozostaje jednak nadal w ścisłym związku z matematyką, która dostarcza jej podstaw teoretycznych.

ciągi o nieskończonej długości, np. reprezentacje liczb niewymiernych w systemie dziesiętnym - choć już reprezentacje symboliczne, np. $\pi$ - są.

nieuporządkowane zbiory symboli, np. zbiór samogłosek.

czytaj dalej: [2], [3]

w oparciu o Wikipedię (licencja GFDL, CC-BY-SA 3.0, autorzy, historia, edycja)