Формальные языки и формальные грамматики Общие понятия - Иерархия Хомского, Алфавит,Слово кратко

Привет, Вы узнаете о том , что такое иерархия хомского, Разберем основные их виды и особенности использования. Еще будет много подробных примеров и описаний. Для того чтобы лучше понимать что такое иерархия хомского, алфавит формального языка, слово формального языка , настоятельно рекомендую прочитать все из категории ОСНОВЫ НАУЧНЫХ ИССЛЕДОВАНИЙ и организация научно-исследовательской деятельности.

иерархия хомского — классификация формальных языков и формальных грамматик, согласно которой они делятся на 4 типа по их условной сложности. Предложена профессором Массачусетского технологического института, лингвистом Ноамом Хомским.

Классификация грамматик

Согласно Хомскому, формальные грамматики можно разделить на четыре типа. Для отнесения грамматики к тому или иному типу необходимо соответствие всех ее правил (продукций) некоторым схемам.

Тип 0 — неограниченные

Грамматика с фразовой структурой G — это алгебраическая структура, упорядоченная четверка (V_T, V_N, P, S), где :

• — алфавит (множество) терминальных символов — терминалов,
• — алфавит (множество) нетерминальных символов — нетерминалов,
• — словарь , причем
• — конечное множество продукций (правил) грамматики,
• — начальный символ (источник).

Здесь — множество всех строк над алфавитом , а — множество непустых строк над алфавитом .

К типу 0 по классификации Хомского относятся неограниченные грамматики — грамматики с фразовой структурой, то есть все без исключения формальные грамматики. Правила можно записать в виде:

,

где — любая непустая цепочка, содержащая хотя бы один нетерминальный символ, а — любая цепочка символов из алфавита.

Практического применения в силу своей сложности такие грамматики не имеют.

Тип 1 — контекстно-зависимые

К этому типу относятся контекстно-зависимые (КЗ) грамматики и неукорачивающие грамматики. Для грамматики все правила имеют вид :

• , где . Об этом говорит сайт https://intellect.icu . Такие грамматики относят к контекстно-зависимым.
• , где . Такие грамматики относят к неукорачивающим.

Эти классы грамматик эквивалентны. Могут использоваться при анализе текстов на естественных языках, однако при построении компиляторов практически не используются в силу своей сложности. Для контекстно-зависимых грамматик доказано утверждение: по некоторому алгоритму за конечное число шагов можно установить, принадлежит цепочка терминальных символов данному языку или нет.

Тип 2 — контекстно-свободные

К этому типу относятся контекстно-свободные (КС) грамматики. Для грамматики все правила имеют вид:

• , где (для неукорачивающих КС-грамматик) или (для укорачивающих), . То есть грамматика допускает появление в левой части правила только нетерминального символа.

КС-грамматики широко применяются для описания синтаксиса компьютерных языков (см. синтаксический анализ).

Тип 3 — регулярные

К третьему типу относятся регулярные грамматики (автоматные) — самые простые из формальных грамматик. Они являются контекстно-свободными, но с ограниченными возможностями.

Все регулярные грамматики могут быть разделены на два эквивалентных класса, которые для грамматики вида III будут иметь правила следующего вида:

• или , где (для леволинейных грамматик).
• ; или , где (для праволинейных грамматик).

Регулярные грамматики применяются для описания простейших конструкций: идентификаторов, строк, констант, а также языков ассемблера, командных процессоров и др.

Классификация языков

Формальные языки классифицируются в соответствии с типами грамматик, которыми они задаются. Однако, один и тот же язык может быть задан разными грамматиками, относящимися к разным типам. В таком случае, считается, что язык относится к наиболее простому из них. Так, язык, описанный грамматикой с фразовой структурой, контекстно-зависимой и контекстно-свободной грамматиками, будет контекстно-свободным.

Так же, как и для грамматик, сложность языка определяется его типом. Наиболее сложные — языки с фразовой структурой (сюда можно отнести естественные языки), далее — КЗ-языки, КС-языки и самые простые — регулярные языки.

Иерархия языков, грамматик и автоматов:

алфавит формального языка

Алфавит формального языка — множество атомарных (неделимых) символов какого-либо формального языка (иногда их называют буквами по аналогии с алфавитами естественных языков или символами). Из символов алфавита формального языка строятся слова, а заданием формальной грамматики — допустимые выражения языка.

Чаще всего алфавит рассматривается как непустое конечное множество. Например, алфавит лежит в основе азбуки Морзе, алфавит — общепринятый набор символов для представления информации в компьютерах. Нотные знаки, цифры — также примеры конечных алфавитов. В некоторых случаях рассматриваются и бесконечные алфавиты, например, множество натуральных чисел — простейший пример счетного алфавита (при этом натуральные числа могут быть рассмотрены и как слова над конечным алфавитом цифр).

Понятие алфавита формального языка широко применяется в лингвистике (в разделах, изучающих формальные грамматики), математической логике (прежде всего — теории моделей), теории автоматов, искусственном интеллекте (в том числе, в компьютерной лингвистике), информатике (в частности, в теории языков программирования). Отдельные теоретические проблемы построения слов и выражений формальных языков над алфавитами исследуются средствами общей алгебры и комбинаторики.

слово формального языка

Слово формального языка (также — цепочка, строка) — произвольная последовательность символов из данного алфавита. Число символов в слове называют его длиной и обозначают . Может допускаться существование единственного слова длины 0, (пустое слово), не содержащее ни одного символа (обозначается , или ).

Множество всех слов длины в алфавите обозначают через , в конечном алфавите число таких слов в точности равно размеру алфавита в степени (). Множество всех слов в алфавите (произвольной длины) обозначают через (звезда Клини), таким образом:

На словах над данным алфавитом определена операция конкатенации — последовательного склеивания слов. Множество всех слов в алфавите с операцией конкатенации образует моноид (свободный моноид^[en]). Множество всех непустых слов над алфавитом с операцией конкатенации образует полугруппу.

Вау!! 😲 Ты еще не читал? Это зря!

• формальные языки , формальные грамматики , аналитические грамматики ,

Данная статья про иерархия хомского подтверждают значимость применения современных методик для изучения данных проблем. Надеюсь, что теперь ты понял что такое иерархия хомского, алфавит формального языка, слово формального языка и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории ОСНОВЫ НАУЧНЫХ ИССЛЕДОВАНИЙ и организация научно-исследовательской деятельности

Из статьи мы узнали кратко, но содержательно про иерархия хомского