Język formalny

Wprowadzenie do języków formalnych

Język formalny to zbiór łańcuchów zbudowanych z symboli określonego alfabetu. Jest istotnym pojęciem w informatyce, logice matematycznej i językoznawstwie, ale nie jest tożsamy z językiem naturalnym. Alfabet formalny składa się z symboli lub tokenów, których konkatenacje tworzą łańcuchy języka.

Definicja i przykłady języków formalnych

Język formalny $L$ jest podzbiorem łańcuchów z $\backslash Sigma^*,$ gdzie $\backslash Sigma$ to alfabet. Przykłady języków formalnych obejmują:

• Wszystkie słowa z liter polskiego alfabetu w słowniku.
• Słowa z cyfr, które przedstawiają liczby pierwsze.
• Łańcuchy z zer i jedynek, w których zer jest więcej niż jedynek.
• Poprawnie napisane równania matematyczne.
• Programy, które zawieszają komputer po skompilowaniu.
• Zbiór pusty.

Alfabet

Alfabet to niepusty zbiór symboli, zazwyczaj oznaczany jako $\backslash Sigma$. Przykłady alfabetów to:

• $\backslash Sigma\; =\; \backslash lbrace\; 1,\; 0\; \backslash rbrace$ – alfabet binarny.
• $\backslash Sigma\; =\; \backslash lbrace\; a,\; b,\; \dots ,\; z\; \backslash rbrace$ – małe litery.
• Inne zbiory, np. kart do gry lub wartości kolorów piksela.

Zbiory, które nie mogą być alfabetem, to zbiór pusty i zbiory nieskończone.

Definicja słowa

Słowo to skończony ciąg symboli z alfabetu. Przykłady słów to:

• Słowa języka naturalnego, np. „ala”.
• Słowo puste $\backslash epsilon.$
• Liczby zapisane w systemie dziesiętnym.
• Wyrażenia algebraiczne.

Nie są słowami: ciągi o nieskończonej długości oraz nieuporządkowane zbiory symboli.

Gramatyki formalne

Gramatyki formalne są popularnym sposobem opisu języków formalnych. Składają się z:

• Symboli alfabetu (symboli terminalnych).
• Symboli pomocniczych (symboli nieterminalnych).
• Symbolu startowego.
• Reguł przepisywania (produkcji).

Przykładowa gramatyka opisana jest przez symbole 0 i 1 oraz reguły tworzenia łańcuchów.

Przynależność słowa do języka

Nie ma ogólnej metody, by stwierdzić, czy dane słowo należy do opisanego języka, z powodu złożoności gramatyk formalnych. Klasy języków formalnych według hierarchii Chomsky’ego obejmują:

• Gramatyki regularne.
• Gramatyki bezkontekstowe.
• Gramatyki kontekstowe.
• Dowolne gramatyki, w tym rekurencyjne.

Języki formalne a języki naturalne

Języki formalne są stosowane do opisu języków naturalnych, co jest skomplikowane ze względu na kontekstowość i zależności reguł gramatycznych.

Podsumowanie

Języki formalne i gramatyki formalne stanowią podstawę dla analizy języków naturalnych i są kluczowe w informatyce oraz logice. Mimo ich złożoności, są użyteczne w wielu dziedzinach, w tym w programowaniu i teorii automatów.