Ієрархія Хомського формальних граматик
До нульового класу належать усі формальні граматики. Елементи цього класу називаютьсянеобмеженими граматиками(англ.unrestricted grammars), оскільки на них не накладається жодних обмежень. Вони задають усі мови, які можуть бути розпізнані машиною Тьюринга. Ці мови також відомі якрекурсивно перераховані(англ.recursively enumerable).
Правила можна записати у вигляді:
[math]\alpha \rightarrow \beta[/math] , де [math]\alpha[/math] - будь-який непустий ланцюжок, що містить хоча б один нетермінальний символ, а [math]\beta[/math] - будь-який ланцюжок символів з алфавіту.
Практичного застосування через свою складність такі граматики не мають.
Приклад [ред.]
[math] S \rightarrow aBcc \\ B \rightarrow A \\ BAA \rightarrow d \\ Ac \rightarrow B \\ A \rightarrow AAA\ dB \[/math]
Виведемо в даній граматиці рядок [math]addd[/math] :
Перший клас представленийнекоротливимиіконтекстно-залежнимиграматиками.
Мови, задані цими граматиками, розпізнаються за допомогоюлінійно обмеженого автомата(англ.linear bounded automaton) (недетермінована машина Тьюринга, чия стрічка обмежена константою, яка залежить від довжини входу.)
Відомо, що гратики, що не коротять, еквівалентні контекстно-залежним.
Приклад [ред.]
[math] S \rightarrow 012 \\ S \rightarrow 0AS2 \ A0 \rightarrow 0A \ A1 \rightarrow 11 [/math]
Другий клас складають контекстно-вільні граматики, які задають контекстно-вільні мови. Ці мови розпізнаються за допомогою автоматів із магазинною пам'яттю.
Тобто граматика припускає появу в лівій частині правила лише одного нетермінального символу.
Приклад [ред.]
Продукції: [math]S\rightarrow\alpha S\alpha\,\,\alpha\,\,varepsilon, \alpha \in \Sigma[/math]
До третього типу належатьавтоматніаборегулярні граматики(англ.regular grammars) — найпростіші з формальних граматик, які задають регулярні мови. Вони є контекстно-вільними, але з обмеженими можливостями.
Всі регулярні граматики можуть бути поділені на два еквівалентні класи наступного виду:
Обидва види задають однакові мови. При цьому якщо правила ліволінійної та праволінійної граматик об'єднати, то мова вже не повинна бути регулярною.
Також можна показати, що безліч мов, що задаються праволінійними граматиками, збігаються з безліччю мов, що задаються кінцевими автоматами.
Приклад [ред.]
[math]L[/math] для регулярного вираження [math]a^*bc^*[/math] .
[math] S \rightarrow aS\ bA \\ A \rightarrow \varepsilon\ cA [/math]