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

* <math>00011111</math> <math>(C \to 1)</math>

 

Nie istnieje ogólna metoda, która dla danej gramatyki 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ść.