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 Chomskiego wprowadza podział na następujące klasy, które można zdefiniować przez złożoność automatu rozpoznającego należenie do języka: Gramatyki regularne – rozpoznawalne przez automaty skończone, Gramatyki bezkontekstowe – rozpoznawalne przez automaty ze stosem, Gramatyki kontekstowe – rozpoznawalne przez automaty liniowo ograniczone, Dowolne gramatyki – w ogólności nierozpoznawalne automatycznie. Ich podzbiór, rozpoznawalny przez maszyny Turinga, definiuje klasę języków określanych jako rekurencyjne.
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 Chomskiego. 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.
Przypisy
Bibliografia
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) Formal languages and systems , Routledge Encyclopedia of Philosophy, rep.routledge.com [dostęp 2023-05-10].