Что значит формальный язык
Формальный язык
В математической логике и информатике формальный язык — это множество конечных слов (строк, цепочек) над конечным алфавитом. Понятие языка чаще всего используется в теории автоматов, теории вычислимости и теории алгоритмов. Научная теория, которая имеет дело с этим объектом, называется теорией формальных языков.
В теории моделей язык соответствует не языку в информатике, а скорее алфавиту. Язык состоит из множеств символов, функций и отношений вместе с их арностью, а также множество переменных. Каждое из этих множеств может быть бесконечным. Из языка вместе с универсальными логическими символами составляются логические высказывания.
Определение
Формальный язык может быть определён по-разному, например:
Если алфавит задан как <a, b>, а язык L включает в себя все слова над ним, то слово ababba принадлежит L. Пустое слово (то есть строка нулевой длины) допускается и часто обозначается как e, ε или Λ.
Некоторые примеры формальных языков:
Операции
Некоторые операции могут быть использованы для того, чтобы порождать новые языки из данных. Предположим, что 
и 
являются языками, определёнными над некоторым общим алфавитом.
ФОРМАЛЬНЫЙ ЯЗЫК
Смотреть что такое «ФОРМАЛЬНЫЙ ЯЗЫК» в других словарях:
формальный язык — — [http://www.iks media.ru/glossary/index.html?glossid=2400324] Тематики электросвязь, основные понятия EN formal language … Справочник технического переводчика
Формальный язык — Не следует путать с формальным стилем речи. В математической логике и информатике формальный язык это множество конечных слов (строк, цепочек) над конечным алфавитом. Понятие языка чаще всего используется в теории автоматов, теории вычислимости и … Википедия
Формальный язык — то же, что Формализованный язык. Иногда под термином «Ф. я.» понимают также формальную систему (См. Формальная система) … Большая советская энциклопедия
ФОРМАЛЬНЫЙ ЯЗЫК, ПРЕДСТАВИМЫЙ МАШИНОЙ — формальный язык, распознаваемый машиной, множество всех тех слов, при работе над к рыми машина попадает в одно из выделенных состояний. Всякое рекурсивно перечислимое множество слов есть формальный язык (ф. я.), представимый нек рой Тьюринга… … Математическая энциклопедия
Язык программирования — искусственный (формальный) язык, предназначенный для записи алгоритмов. Язык программирования задается своим описанием и реализуется в виде специальной программы: компилятора или интерпретатора. По английски: Programming language Синонимы:… … Финансовый словарь
ЯЗЫК ПРОГРАММИРОВАНИЯ — это совокупность набора символов (алфавита) системы, правил образования (синтаксис) и истолкования конструкции из символов (семантика) для задания алгоритмов с использованием символов естественного языка. В самом общем виде формальный язык… … Большая политехническая энциклопедия
язык концептуальной схемы — Формальный язык для описания концептуальной схемы, ее составных частей и действий над ними. [ГОСТ 34.320 96] Тематики базы данных EN conceptual schema language … Справочник технического переводчика
ЯЗЫК ПРОГРАММИРОВАНИЯ — формальный язык для описания данных (информации) и алгоритма (программы) их обработки на ЭВМ. Основу Я. п. составляют алгоритмические языки. Первыми Я. п. были внутренние машинные языки, представляющие собой системы команд конкретной ЭВМ,… … Большой энциклопедический политехнический словарь
формальный синтаксис — 3.4.1 формальный синтаксис: Спецификация точно сформулированных предложений формального языка с применением формальной грамматики. Примечание 1 Формальный язык это машинно ориентированный язык с интерпретированием. Примечание 2 Формальная… … Словарь-справочник терминов нормативно-технической документации
Язык (значения) — Язык: В Викисловаре есть статья «язык» Язык знаковая система для обмена информацией. Естественный язык сформи … Википедия
Формальные языки и грамматики
Мотивация
Время от времени на Хабре публикуются посты и переводные статьи, посвященные тем или иным аспектам теории формальных языков. Среди таких публикаций (не хочется указывать конкретные работы, чтобы не обижать их авторов), особенно среди тех, которые посвящены описанию различных программных инструментов обработки языков, часто встречаются неточности и путаница. Автор склонен считать, что одной из основных причин, приведших к такому прискорбному положению вещей, является недостаточный уровень понимания идей, лежащих в основании теории формальных языков.
Этот текст задуман как популярное введение в теорию формальных языков и грамматик. Эта теория считается (и, надо сказать, справедливо) довольно сложной и запутанной. На лекциях студенты обычно скучают и экзамены тем более не вызывают энтузиазма. Поэтому и в науке не так много исследователей в этой тематике. Достаточно сказать, что за все время, с зарождения теории формальных грамматик в середине 50-х годов прошлого века и до наших дней, по этому научному направлению было выпущено всего две докторских диссертации. Одна из них была написана в конце 60-х годов Алексеем Владимировичем Гладким, вторая уже на пороге нового тысячелетия — Мати Пентусом.
Далее в наиболее доступной форме описаны два основных понятия теории формальных языков: формальный язык и формальная грамматика. Если тест будет интересен аудитории, то автор дает торжественное обещание разродиться еще парой подобных опусов.
Формальные языки
Коротко говоря, формальный язык — это математическая модель реального языка. Под реальным языком здесь понимается некий способ коммуникации (общения) субъектов друг с другом. Для общения субъекты используют конечный набор знаков (символов), которые проговариваются (выписываются) в строгом временном порядке, т.е. образуют линейные последовательности. Такие последовательности обычно называют словами или предложениями. Таким образом, здесь рассматривается только т.н. коммуникативная функция языка, которая изучается с использованием математических методов. Другие функции языка здесь не изучаются и, потому, не рассматриваются.
В качестве известного примера такой математической абстракции можно привести модель, известную под неблагозвучным для русского уха названием «мешок слов». В этой модели исследуются тексты естественного языка (т.е. одного из тех языков, которые люди используют в процессе повседневного общения между собой). Основной объект модели мешка слов — это слово, снабженное единственным атрибутом, частотой встречаемости этого слова в исходном тексте. В модели не учитывается, как слова располагаются рядом друг с другом, только сколько раз каждое слово встречается в тексте. Мешок слов используется в машинном обучении на основе текстов в качестве одного из основных объектов изучения.
Но в теории формальных языков представляется важным изучить законы расположения слов рядом друг с другом, т.е. синтаксические свойства текстов. Для этого модель мешка слов выглядит бедной. Поэтому формальный язык задается как множество последовательностей, составленных из элементов конечного алфавита. Определим это более строго.
Алфавит представляет собой конечное непустое множество элементов. Эти элементы будем называть символам. Для обозначения алфавита обычно будем использовать латинское V, а для обозначения символов алфавита — начальные строчные буквы латинского алфавита. Например, выражение V =
Цепочка представляет собой конечную последовательность символов. Например, abc — цепочка из трех символов. Часто при обозначении цепочек в символах используют индексы. Сами цепочки обозначают строчными символами конца греческого алфавита. Например, omega = a1. an — цепочка из n символов. Цепочка может быть пустой, т.е. не содержать ни одного символа. Такие цепочки будем обозначать греческой буквой эпсилон.
Наконец, формальный язык L над алфавитом V — это произвольное множеств цепочек, составленных из символов алфавита V. Произвольность здесь означает тот факт, что язык может быть пустым, т.е. не иметь ни одной цепочки, так и бесконечным, т.е. составленным из бесконечного числа цепочек. Последний факт часто вызывает недоумение: разве имеются реальные языки, которые содержат бесконечное число цепочек? Вообще говоря, в природе все конечно. Но мы здесь используем бесконечность как возможность образования цепочек неограниченной длины. Например, язык, который состоит из возможных имен переменных языка программирования C++, является бесконечным. Ведь имена переменных в C++ не ограничены по длине, поэтому потенциально таких имен может быть бесконечно много. В реальности, конечно, длинные имена переменных не имеют для нас особого смысла т.к. к концу чтения такого имени уже забываешь его начало. Но в качестве потенциальной возможности задавать неограниченные по длине переменные, это свойство выглядит полезным.
Итак, формальные языки — это просто множества цепочек, составленных из символов некоторого конечного алфавита. Но возникает вопрос: как можно задать формальный язык? Если язык конечен, то можно просто выписать все его цепочки одну за другой (конечно, можно задуматься, имеет ли смысл выписывать цепочки языка, имеющего хотя бы десять тысяч элементов и, вообще, есть ли смысл в таком выписывании?). Что делать, если язык бесконечен, как его задавать? В этот момент на сцену выходят грамматики.
Формальные грамматики
Способ задания языка называет грамматикой этого языка. Таким образом, грамматикой мы называем любой способ задания языка. Например, грамматика L =
Назначение грамматики — задание языка. Это задание обязательно должно быть конечным, иначе человек не будет в состоянии эту грамматику понять. Но каким образом, конечное задание описывает бесконечные совокупности? Это возможно только в том случае, если строение всех цепочек языка основано на единых принципов, которых конечное число. В примере выше в качестве такого принципа выступает следующий: «каждая цепочка языка начинается с символов a, за которыми идет столько же символов b». Если язык представляет собой бесконечную совокупность случайным образом набранных цепочек, строение которых не подчиняется единым принципам, то очевидно для такого языка нельзя придумать грамматику. И здесь еще вопрос, можно или нет считать такую совокупность языком. В целях математической строгости и единообразия подхода обычно такие совокупности языком считают.
Итак, грамматика языка описывает законы внутреннего строения его цепочек. Такие законы обычно называют синтаксическими закономерностями. таким образом, можно перефразировать определение грамматики, как конечного способа описания синтаксических закономерностей языка. Для практики интересны не просто грамматики, но грамматики, которые могут быть заданы в рамках единого подхода (формализма или парадигмы). Иначе говоря, на основе единого языка (метаязыка) описания грамматик всех формальных языков. Тогда можно придумать алгоритм для компьютера, который будет брать на вход описание грамматики, сделанное на этом метаязыке, и что-то делать с цепочками языка.
Такие парадигмы описания грамматик называют синтаксическими теориями. Формальная грамматика — это математическая модель грамматики, описанная в рамках какой-то синтаксической теории. Таких теорий придумано довольно много. Самый известный метаязык для задания грамматик — это, конечно, порождающие грамматики Хомского. Но имеются и другие формализмы. Один из таких них — окрестностные грамматики, будет описан чуть ниже.
Окрестностные грамматики
В середине 60-х годов советский математик Юлий Анатольевич Шрейдер предложил простой способ описания синтаксиса языков на основе т.н. окрестностных грамматик. Для каждого символа языка задается конечное число его «окрестностей» — цепочек, содержащих данный символ (центр окрестности) где-то внутри. Набор таких окрестностей для каждого символа алфавита языка называется окрестностной грамматикой. Цепочка считается принадлежащей языку, задаваемому окрестностной грамматикой, если каждый символ этой цепочки входит в нее вместе с некоторой своей окрестностью.
Не всякий язык может быть описан окрестностной грамматикой. Рассмотрим, например, язык B, цепочки которого начинаются либо с символа «0», либо с символа «1». В последнем случае далее в цепочке могут идти символы «a» и «b». Если же цепочка начинается с нуля, то далее могут идти только символы «a». Нетрудно доказать, что для этого языка нельзя придумать никакой окрестностной грамматики. Легитимность вхождения символа «b» в цепочку обусловлена ее первым символом. Для любой окрестностной грамматики, в которой задается связь между символами «b» и «1» можно будет подобрать достаточно длинную цепочку, чтобы всякая окрестность символа «b» не доставала до начала цепочки. Тогда в начало можно будет подставить символ «0» и цепочка будет принадлежать языку A, что не отвечает нашим интуитивным представлениям о синтаксическом строении цепочек этого языка.
С другой стороны, легко можно построить конечный автомат, который распознает этот язык. Значит, класс языков, которые описываются окрестностными грамматиками, уже класса автоматных языков. Языки, задаваемые окрестностными грамматиками, будем называть шрейдеровскими. Таким образом, в иерархии языков можно выделить класс шрейдеровских языков, который является подклассом автоматных языков.
Можно сказать, что шрейдеровские языки задают одно простое синтаксическое отношение — «быть рядом» или отношение непосредственного предшествования. Отношение дальнего предшествования (которое, очевидно, присутствует в языке B) окрестностной грамматикой задано быть не может. Но, если визуализировать синтаксические отношения в цепочках языка, то для диаграмм отношений, в которые превращаются такие цепочки, можно придумать окрестностную грамматику.
Формальные и естественные языки
Естественные языки являются языками, на которых говорят люди, такие как английский, испанский, и французский языки. Они не были разработаны людьми (хотя люди пытаются навязать какие-то правила для них); они развивались естественным путем.
Формальные языки являются языками, которые разработаны людьми для конкретных применений. Например, нотация, которую математики используют как формальный язык, которая особенно хороша для обозначения отношений между числами и символами. Химики используют формальный язык для представления химической структуры молекул. И самое важное:
Языки программирования являются формальными языками, которые были разработаны для расчетных выражений.
Формальные языки, как правило, имеют строгие правила синтаксиса. Например, 3+3=6 является синтаксически правильным математическим утверждением, но 3=+$6 — нет. H2O является синтаксически правильным химическим названием, но 2ZZ — нет.
В качестве упражнения создайте то, что выглядит хорошо структурированным английским предложением с неузнаваемыми лексемами в нем. Затем напишите еще одно предложение со всеми действующими лексемами, но с недопустимой структурой.
Когда вы читаете предложение на английском языке или оператор на формальном языке, вы должны выяснить, какова структура предложения присутствует (хотя на естественном языке вы делаете это подсознательно). Этот процесс называется синтаксическим анализом.
Например, когда вы слышите фразу «Второй ботинок упал», вы понимаете, что «второй ботинок» является предметом, а «упал» — предикатом. После того как вы разобрали предложение, вы можете выяснить его значение либо его семантику. Предполагая, что вы знаете, что такое «ботинок» и что это значит падать, вы будете понимать общий подтекст этого предложения.
Хотя у формальных и естественных языков есть много особенностей в общих лексемах, структуре, синтаксисе и семантике, там много различий:
неоднозначность — естественные языки полны двусмысленности, когда люди общаются с помощью контекстных подсказок и другой информации. Формальные языки разработаны быть почти или полностью однозначными, что означает, что любое утверждение имеет ровно одно значение, вне зависимости от контекста.
избыточность — Для компенсации двусмысленности и уменьшения недопонимания естественные языки используют много избыточности. В результате они часто многословны. Формальные языки являются менее избыточными и более краткими.
буквальность — естественные языки полны идиом и метафор. Если я говорю: «Второй ботинок упал» там, вероятно, нет никакой обуви и нечему падать. Формальные языки означают именно то, что они говорят.
Людям, которые растут, разговаривая на естественном языке, часто приходится приспосабливаться к формальным языкам. В некотором смысле разница между формальным и естественным языками подобна разнице между поэзией и прозой, но в большей степени:
— слова используются для их впечатления, а также для их смысла, и все стихотворение вместе создает эффект или эмоциональный отклик. Неоднозначность не только общепринята, но часто является преднамеренной.
— буквальное значение слова является более важным, а структура способствует большему пониманию. Проза более поддается анализу, чем поэзия, но до сих пор часто неоднозначна.
— значение компьютерной программы однозначно и буквально, и может быть осознано полностью посредством анализа лексем и структуры.
Вот несколько советов для чтения программ (и других формальных языков). Во-первых, помните, что формальные языки являются гораздо более плотными, чем естественные языки, так что понадобится больше времени, чтобы прочитать их. Кроме того, структура очень важна, так что поэтому не очень хорошая идея читать сверху вниз, слева направо. Вместо этого, научитесь анализировать программу в вашей голове, идентифицируя лексемы и интерпретируя структуру. В довершение ко всему, детали имеют значение. Мелочи, такие как орфографические ошибки и плохая пунктуация, которые могут вам сойти с рук в естественных языках, могут иметь большое значение в формальном языке.
Традиционно первая программа, которую пишут на новом языке, называется «Hello, World!», потому что всё, что она делает — это отображает слова «Hello, World!». В Python, это выглядит следующим образом:
Это пример оператора печати, который на самом деле не печатает ничего на бумаге. Он отображает значение на экране. В этом случае результатом являются слова:
Кавычки в программе отмечают начало и конец значения; они не появляются в результате.
Некоторые люди судят о качестве языка программирования по простоте программы «Hello, World!». По этому образцу, Python делает это настолько, насколько это возможно.
Решение проблемы — процесс разработки проблемы, нахождение решения и отражение решения.
Язык программирования высокого уровня — язык программирования, подобный Python, который задуман быть легким для людей, чтобы читать и писать.
Низкоуровневый язык — язык программирования, который разработан, чтобы быть естественным для выполнения компьютером; также называемый «машинным языком» или «языком ассемблера».
Переносимость — свойство программы, которая может работать на более чем одном виде компьютеров. интерпретация — выполнение программы на языке высокого уровня с помощью перевода одной его строки за один раз.
Компиляция — одноразовый перевод программы, написанной на языке высокого уровня, на язык низкого уровня в рамках подготовки для последующего выполнения.
Исходный код — программа на языке высокого уровня перед ее компиляцией. объектный код — вывод компилятора после того, как он перевел программу. выполняемый код — другое имя для «объектного кода», который готов к выполнению. сценарий — программа, хранимая в файле (как правило та, которая будет интерпретироваться).
Программа — набор инструкций, который определяет вычисления. алгоритм — общий процесс решения класса проблем.
Баг — ошибка в программе. отладка — процесс поиска и удаления любой из трех типов ошибок программирования.
Синтаксис — структуры программы. синтаксическая ошибка — ошибка в программе, которая делает невозможным анализ (и, следовательно, невозможность интерпретации).
Ошибка выполнения — ошибка, которая не встречается, пока программа не начнет выполняться, но которая предотвращает продолжение программы.
Исключение — другое название ошибки выполнения. семантическая ошибка — ошибка в программе, которая заставляет ее делать что-то другое, чем то, что подразумевалось программистом.
Семантика — смысл программы. естественный язык — любой из языков, на котором говорят люди и которые развивались естественным образом.
Формальный язык — любой из языков, который люди разработали для определенных целей, таких как представление математических идей или компьютерных программ; все языки программирования являются формальными языками.
Лексема — один из основных элементов синтаксической структуры программы, аналогичный слову на естественном языке.
Синтаксический анализ — изучение программы и анализ синтаксической структуры.
Оператор печати — инструкция, которая вызывает интерпретатор Python для отображения значения на экране.
Статьи к прочтению:
Естественные и формальные язык. Формы представления информации | Информатика 7 класс #8 | Инфоурок
Похожие статьи:
Если речь идёт о составлении алгоритмов для процессора ЭВМ (электронно-вычислительной машины), исполнителем является процессор. Упрощённая модель…
Иску?сственные языки? — специальные языки, которые, в отличие от естественных, сконструированы целенаправленно. Таких языков существует уже более тысячи,…
Преимущества изучения формальных языков
Рубрика: Информационные технологии
Дата публикации: 25.04.2020 2020-04-25
Статья просмотрена: 91 раз
Библиографическое описание:
Смирнова, А. Ю. Преимущества изучения формальных языков / А. Ю. Смирнова. — Текст : непосредственный // Молодой ученый. — 2020. — № 17 (307). — С. 29-32. — URL: https://moluch.ru/archive/307/69233/ (дата обращения: 26.12.2021).
Человек, который хочет начать программировать, обращается в интернет, с вопросом: «С чего начать изучение программирования?» В данной анализируется, какие преимущества может получить программист, изучив формальные языки как до освоения первого языка высоко уровня, так и после.
Ключевые слова: язык, язык программирования, правило грамматики, синтаксис языка
В современном мире информационно-компьютерные технологии используются повсеместно. Вследствие этого есть потребность как в самих технологиях, так и в людях, программистах, которые создают программные продукты или их поддерживают. [1] Профессия программиста набирает всё большую популярность, поскольку актуальна и обладает низким порогом вхождения.
Человек, который хочет начать программировать, обращается в интернет, с вопросом: «С чего начать изучение программирования?» Большинство людей советуют начать с конкретного языка программирования, если быть точнее, с курсов по этому языку. [2] В случае, если вопросом интересуется ребёнок, то таким языком является Scratch, если интересуется взрослый, то в зависимости от интересующей его области программирования предлагается наиболее простой язык. Дополнительно советуют углублённо изучать информатику, математику и английский язык в школе и соответствующие им предметы в университете.
В данной статье рассматриваются основные понятия из области формальных языков, а также даётся ответ на вопрос, какие преимущества получит обучающийся, изучив данную область даже до освоения конкретного языка программирования высокого уровня.
Формальный язык — это созданный человеком, искусственный, язык, характеризующийся чёткими и однозначными правилами построения выражений и их интерпретации. [3] В основе формального, как и любого другого языка, лежит алфавит. Алфавит представляет собой конечный набор символов для обмена информацией. Далее описывается и синтаксис языка, т. е. правила построения конкретных выражений.
Наиболее эффективным способом формального описания языков программирования являются грамматики. [4] Грамматикой называется следующая четверка: терминальных символов, нетерминальных символов, правил грамматики и начального символа. Проведя параллель с вышеописанным, терминальные и нетерминальные символы составляют алфавит языка, стартовый символ так же принадлежит алфавиту, синтаксисом языка являются правила грамматики.
За счёт использования формальных грамматик можно описать любой язык программирования. [5] Если проанализировать все языки, можно заметить, что во всех есть некие общие конструкции, некоторые из которых приведены ниже:
Из вышеприведенного анализа можно поговорить о преимуществах изучения формальных языков.
В случае если формальные языки изучаются до того, как приступить к освоению первого языка программирования, преимущество заключается в более быстром пороге вхождения. Это происходит, потому что учащийся знает все конструкции, использующиеся в языке, понимает механизмы их работы и при изучении языка узнаёт только то, как они синтаксически выглядят в конкретном языке.
В случае, когда изучение формальных языков происходит когда учащийся знает уже хотя бы один язык программирования, то преимущество состоит в углублённом понимании конструкций языка и процессов работы программного кода. Важно отметить, что в данном случае при изучении второго, третьего и последующих языков, так же происходит ускорение процесса освоения соответствующего языка. Это происходит за счёт того, что обучающийся знает основу и может легко провести аналогию по уже имеющемуся опыту.
Независимо от времени обучения, знание формальных языков позволяет:
Поговорив о преимуществах, следует отметить и недостатки, которые так же важно учитывать:
Таким образом, проанализировав всю вышеприведённую информацию, можно сделать вывод, что изучение формальных языков даёт программисту ряд преимуществ. Такому человеку легче и быстрее освоить новые языки, он совершает меньше ошибок при написании кода, лучше понимает механизмы работы программ. Однако следует помнить, что детям не стоит начинать свой путь в программировании с изучения формальных языков, а взрослым, которые не понимают или не любят математику, лучше овладевать формальными языками после освоения какого-либо языка программирования.