Изменения

К нулевому классу относятся все [[Формальные_грамматики|формальные грамматики]]. Элементы этого класса называются '''неограниченными грамматиками'''(англ. ''unrestricted grammars''), поскольку на них не накладывается никаких ограничений. Практического применения в силу своей сложности такие грамматики не имеютОни задают все языки, которые могут быть распознаны [[Машина_Тьюринга|машиной Тьюринга]]. Эти языки также известны как '''рекурсивно перечислимые''' (англ. ''recursively enumerable'').

Type-0 grammars (unrestricted grammars) include all formal grammarsПравила можно записать в виде: <tex>\alpha \rightarrow \beta</tex>, где <tex>\alpha</tex> — любая непустая цепочка, содержащая хотя бы один нетерминальный символ, а <tex>\beta</tex> — любая цепочка символов из алфавита. They generate exactly all languages that can be recognized by a Turing machine. These languages are also known as the recursively enumerable languages. Note that this is different from the recursive languages which can be decided by an always-halting Turing machine Практического применения в силу своей сложности такие грамматики не имеют.