Лекция
Привет, Вы узнаете о том , что такое иерархия хомского, Разберем основные их виды и особенности использования. Еще будет много подробных примеров и описаний. Для того чтобы лучше понимать что такое иерархия хомского, алфавит формального языка, слово формального языка , настоятельно рекомендую прочитать все из категории ОСНОВЫ НАУЧНЫХ ИССЛЕДОВАНИЙ и организация научно-исследовательской деятельности.
иерархия хомского — классификация формальных языков и формальных грамматик, согласно которой они делятся на 4 типа по их условной сложности. Предложена профессором Массачусетского технологического института, лингвистом Ноамом Хомским.
Согласно Хомскому, формальные грамматики можно разделить на четыре типа. Для отнесения грамматики к тому или иному типу необходимо соответствие всех ее правил (продукций) некоторым схемам.
Грамматика с фразовой структурой G — это алгебраическая структура, упорядоченная четверка (VT, VN, P, S), где :
— алфавит (множество) терминальных символов — терминалов,
— алфавит (множество) нетерминальных символов — нетерминалов,
— словарь 
, причем 
— конечное множество продукций (правил) грамматики, 
— начальный символ (источник).Здесь 
— множество всех строк над алфавитом 
, а 
— множество непустых строк над алфавитом .
К типу 0 по классификации Хомского относятся неограниченные грамматики — грамматики с фразовой структурой, то есть все без исключения формальные грамматики. Правила можно записать в виде:
,
где 
— любая непустая цепочка, содержащая хотя бы один нетерминальный символ, а 
— любая цепочка символов из алфавита.
Практического применения в силу своей сложности такие грамматики не имеют.
К этому типу относятся контекстно-зависимые (КЗ) грамматики и неукорачивающие грамматики. Для грамматики 
все правила имеют вид :
, где 
. Об этом говорит сайт https://intellect.icu . Такие грамматики относят к контекстно-зависимым., где 
. Такие грамматики относят к неукорачивающим.Эти классы грамматик эквивалентны. Могут использоваться при анализе текстов на естественных языках, однако при построении компиляторов практически не используются в силу своей сложности. Для контекстно-зависимых грамматик доказано утверждение: по некоторому алгоритму за конечное число шагов можно установить, принадлежит цепочка терминальных символов данному языку или нет.
К этому типу относятся контекстно-свободные (КС) грамматики. Для грамматики все правила имеют вид:
, где 
(для неукорачивающих КС-грамматик) или (для укорачивающих), 
. То есть грамматика допускает появление в левой части правила только нетерминального символа.КС-грамматики широко применяются для описания синтаксиса компьютерных языков (см. синтаксический анализ).
К третьему типу относятся регулярные грамматики (автоматные) — самые простые из формальных грамматик. Они являются контекстно-свободными, но с ограниченными возможностями.
Все регулярные грамматики могут быть разделены на два эквивалентных класса, которые для грамматики вида III будут иметь правила следующего вида:
или 
, где 
(для леволинейных грамматик).
; или , где (для праволинейных грамматик).Регулярные грамматики применяются для описания простейших конструкций: идентификаторов, строк, констант, а также языков ассемблера, командных процессоров и др.
Формальные языки классифицируются в соответствии с типами грамматик, которыми они задаются. Однако, один и тот же язык может быть задан разными грамматиками, относящимися к разным типам. В таком случае, считается, что язык относится к наиболее простому из них. Так, язык, описанный грамматикой с фразовой структурой, контекстно-зависимой и контекстно-свободной грамматиками, будет контекстно-свободным.
Так же, как и для грамматик, сложность языка определяется его типом. Наиболее сложные — языки с фразовой структурой (сюда можно отнести естественные языки), далее — КЗ-языки, КС-языки и самые простые — регулярные языки.
Иерархия языков, грамматик и автоматов:
Алфавит формального языка — множество атомарных (неделимых) символов какого-либо формального языка (иногда их называют буквами по аналогии с алфавитами естественных языков или символами). Из символов алфавита формального языка строятся слова, а заданием формальной грамматики — допустимые выражения языка.
Чаще всего алфавит рассматривается как непустое конечное множество. Например, алфавит 
лежит в основе азбуки Морзе, алфавит 
— общепринятый набор символов для представления информации в компьютерах. Нотные знаки, цифры — также примеры конечных алфавитов. В некоторых случаях рассматриваются и бесконечные алфавиты, например, множество натуральных чисел 
— простейший пример счетного алфавита (при этом натуральные числа могут быть рассмотрены и как слова над конечным алфавитом цифр).
Понятие алфавита формального языка широко применяется в лингвистике (в разделах, изучающих формальные грамматики), математической логике (прежде всего — теории моделей), теории автоматов, искусственном интеллекте (в том числе, в компьютерной лингвистике), информатике (в частности, в теории языков программирования). Отдельные теоретические проблемы построения слов и выражений формальных языков над алфавитами исследуются средствами общей алгебры и комбинаторики.
Слово формального языка (также — цепочка, строка) — произвольная последовательность символов из данного алфавита. Число символов в слове 
называют его длиной и обозначают 
. Может допускаться существование единственного слова длины 0, (пустое слово), не содержащее ни одного символа (обозначается 
, 
или 
).
Множество всех слов длины 
в алфавите 
обозначают через 
, в конечном алфавите число таких слов в точности равно размеру алфавита в степени (
). Множество всех слов в алфавите (произвольной длины) обозначают через 
(звезда Клини), таким образом:
На словах над данным алфавитом определена операция конкатенации — последовательного склеивания слов. Множество всех слов в алфавите с операцией конкатенации образует моноид (свободный моноид[en]). Множество всех непустых слов над алфавитом с операцией конкатенации образует полугруппу.
Данная статья про иерархия хомского подтверждают значимость применения современных методик для изучения данных проблем. Надеюсь, что теперь ты понял что такое иерархия хомского, алфавит формального языка, слово формального языка и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории ОСНОВЫ НАУЧНЫХ ИССЛЕДОВАНИЙ и организация научно-исследовательской деятельности
Из статьи мы узнали кратко, но содержательно про иерархия хомского
Комментарии
Оставить комментарий
Основы научных исследований и организация научно-исследовательской деятельности
Термины: Основы научных исследований и организация научно-исследовательской деятельности