Формальный язык что это
Формальный язык
В математической логике и информатике формальный язык — это множество конечных слов (строк, цепочек) над конечным алфавитом. Понятие языка чаще всего используется в теории автоматов, теории вычислимости и теории алгоритмов. Научная теория, которая имеет дело с этим объектом, называется теорией формальных языков.
В теории моделей язык соответствует не языку в информатике, а скорее алфавиту. Язык состоит из множеств символов, функций и отношений вместе с их арностью, а также множество переменных. Каждое из этих множеств может быть бесконечным. Из языка вместе с универсальными логическими символами составляются логические высказывания.
Определение
Формальный язык может быть определён по-разному, например:
Если алфавит задан как <a, b>, а язык L включает в себя все слова над ним, то слово ababba принадлежит L. Пустое слово (то есть строка нулевой длины) допускается и часто обозначается как e, ε или Λ.
Некоторые примеры формальных языков:
Операции
Некоторые операции могут быть использованы для того, чтобы порождать новые языки из данных. Предположим, что 
и 
являются языками, определёнными над некоторым общим алфавитом.
Формальные языки и грамматики
Мотивация
Время от времени на Хабре публикуются посты и переводные статьи, посвященные тем или иным аспектам теории формальных языков. Среди таких публикаций (не хочется указывать конкретные работы, чтобы не обижать их авторов), особенно среди тех, которые посвящены описанию различных программных инструментов обработки языков, часто встречаются неточности и путаница. Автор склонен считать, что одной из основных причин, приведших к такому прискорбному положению вещей, является недостаточный уровень понимания идей, лежащих в основании теории формальных языков.
Этот текст задуман как популярное введение в теорию формальных языков и грамматик. Эта теория считается (и, надо сказать, справедливо) довольно сложной и запутанной. На лекциях студенты обычно скучают и экзамены тем более не вызывают энтузиазма. Поэтому и в науке не так много исследователей в этой тематике. Достаточно сказать, что за все время, с зарождения теории формальных грамматик в середине 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) окрестностной грамматикой задано быть не может. Но, если визуализировать синтаксические отношения в цепочках языка, то для диаграмм отношений, в которые превращаются такие цепочки, можно придумать окрестностную грамматику.
Формальный язык
Смотреть что такое «Формальный язык» в других словарях:
формальный язык — — [http://www.iks media.ru/glossary/index.html?glossid=2400324] Тематики электросвязь, основные понятия EN formal language … Справочник технического переводчика
Формальный язык — Не следует путать с формальным стилем речи. В математической логике и информатике формальный язык это множество конечных слов (строк, цепочек) над конечным алфавитом. Понятие языка чаще всего используется в теории автоматов, теории вычислимости и … Википедия
ФОРМАЛЬНЫЙ ЯЗЫК — в математической лингвистике произвольное множество цепочек (т. е. слов )в нек ром (конечном или бесконечном) алфавите V (иногда называемом также словарем), т. е. выражений вида где число k, обычно обозначаемое есть длина цепочки Рассматривается… … Математическая энциклопедия
ФОРМАЛЬНЫЙ ЯЗЫК, ПРЕДСТАВИМЫЙ МАШИНОЙ — формальный язык, распознаваемый машиной, множество всех тех слов, при работе над к рыми машина попадает в одно из выделенных состояний. Всякое рекурсивно перечислимое множество слов есть формальный язык (ф. я.), представимый нек рой Тьюринга… … Математическая энциклопедия
Язык программирования — искусственный (формальный) язык, предназначенный для записи алгоритмов. Язык программирования задается своим описанием и реализуется в виде специальной программы: компилятора или интерпретатора. По английски: Programming language Синонимы:… … Финансовый словарь
ЯЗЫК ПРОГРАММИРОВАНИЯ — это совокупность набора символов (алфавита) системы, правил образования (синтаксис) и истолкования конструкции из символов (семантика) для задания алгоритмов с использованием символов естественного языка. В самом общем виде формальный язык… … Большая политехническая энциклопедия
язык концептуальной схемы — Формальный язык для описания концептуальной схемы, ее составных частей и действий над ними. [ГОСТ 34.320 96] Тематики базы данных EN conceptual schema language … Справочник технического переводчика
ЯЗЫК ПРОГРАММИРОВАНИЯ — формальный язык для описания данных (информации) и алгоритма (программы) их обработки на ЭВМ. Основу Я. п. составляют алгоритмические языки. Первыми Я. п. были внутренние машинные языки, представляющие собой системы команд конкретной ЭВМ,… … Большой энциклопедический политехнический словарь
формальный синтаксис — 3.4.1 формальный синтаксис: Спецификация точно сформулированных предложений формального языка с применением формальной грамматики. Примечание 1 Формальный язык это машинно ориентированный язык с интерпретированием. Примечание 2 Формальная… … Словарь-справочник терминов нормативно-технической документации
Язык (значения) — Язык: В Викисловаре есть статья «язык» Язык знаковая система для обмена информацией. Естественный язык сформи … Википедия
Формальные языки и грамматики
Математический язык как форма выражения научного знания использовался еще в древности при решении практических задач.
Большую роль в развитии математики как языка – метаязыка наук – сыграла математическая логика, аксиоматизировавшая ряд теории, изучившая их логику, внутреннюю структуру.
Язык как коммуникативный аппарат должен иметь определяющие конструкции слов над данным алфавитом, грамматические правила образования предложений из слов и соотнесения этих предложений тем явлениям и процессам, которые они описывают, или синтаксическим и семантическим правилам.
Пример. В частности, семантика изучает связи вида:
«знак, структура знаков 
значение объект «;
синтаксис – связи вида:
«знак, структура знаков объект «.
Пример. Запишем более кратко, сжато, точно (формализованно) факт » целое число x делится на целое число y без остатка». На математическом языке это будет иметь вид «Число x кратно числу y «. Факт, что числа x, y – целые, уже можно специально, как выше, не оговаривать, так как математическое понятие кратности это уже предполагает ( аксиома ). Запишем еще более кратко и формализованно на алгоритмическом языке Паскаль : » x mod y = 0 «. Здесь уже условие кратности область изменения аргументов не нужно оговаривать – они декларированы в языке Паскаль (в описаниях типов и операции mod ).
Языки бывают естественного происхождения (например языки общения) и искусственного происхождения или формальные языки, разрабатываемые для общения человека с автоматом (компьютером) либо для описания и получения знаний.
Язык (множество слов S(X) ) задается грамматикой G(S) – структурой правил, которые позволяют порождать все слова 
и только их.
Грамматический анализ – процесс редукции к нетерминальному символу или слову.
Естественные и формальные языки. Формы представления информации.
Урок 7. Информатика 7 класс (ФГОС)
В данный момент вы не можете посмотреть или раздать видеоурок ученикам
Чтобы получить доступ к этому и другим видеоурокам комплекта, вам нужно добавить его в личный кабинет, приобрев в каталоге.
Получите невероятные возможности
Конспект урока «Естественные и формальные языки. Формы представления информации.»
На прошлых уроках мы узнали:
· Информация для человека – это система некоторых посланий, информационных сигналов, которые человек получает из различных источников.
· Информационные сигналы представляют собой некоторые изменения физических величин. Человек получает информационные сигналы и каким-то образом интерпретирует.
· Чтобы сохранить или передать информацию, человек кодирует её с помощью знаков.
· Знак – это объект-заменитель, который может обозначать другой объект, явление или отношение. Большинство знаков являются частью знаковых систем.
· Знаковая система – это совокупность знаков, которые обладают набором правил образования, осмысления и употребления, а также служат для передачи некоторых сообщений.
· Язык – это знаковая система, которую человек использует чтобы выразить свои мысли или для общения с другими людьми.
· Формы представления информации.
И так из прошлого урока мы помним, что при помощи языка мы можем выразить всё, что угодно и передать сообщение любого содержания. Мы можем передавать эти сообщения устно и письменно. Для этого в русском языке есть два набора знаков, звуковые, которые называются фонемами и визуальные знаки, которые называются буквами. Для того, чтобы состоялась передача информации с помощью языка, им должны владеть и отправитель, и получатель.
Языки, которые люди используют для общения между собой называются естественными. К таким языкам относятся русский, английский, китайский и другие языки народов мира. Всего в мире их насчитывается больше двух тысяч. Такие языки складывались стихийно в течение очень долгого периода времени. Каждый естественный язык имеет свою историю возникновения и развития. Эта история неотделима от истории народа, который говорит на этом языке.
Черты естественных языков:
· Естественными языками пользуются большие группы людей. Их знают большинство членов национального сообщества, которому язык принадлежит.
· Естественные языки имеют очень широкую сферу применения. При помощи таких языков люди могут передавать любую информацию. От простого сообщения о погоде, до объяснения устройства какой-нибудь технической системы.
· В естественных языках есть большое количество правил. Некоторые из них имеют явный характер, например правила грамматики, а другие – неявные, например правила употребления слов и их осмысления.
· Такой язык обычно достаточно гибкий. То есть его можно применять для описания самых разных ситуаций, в том числе и новых, для которых до этого он не применялся. И при этом все участники разговора будут понимать, о чём идёт речь.
· Естественные языки обычно достаточно открыты. Носитель языка может образовывать новые слова, которые при этом будут понятны его собеседникам. То есть в таких языках развиты механизмы словообразования. Так человек, который услышал или увидел новое для себя слово может догадаться по составу о его происхождении и значении.
· Такие языки всегда динамично развиваются и подстраиваются под потребности взаимодействия людей, которые им владеют. Это хорошо видно на примере различных профессиональных диалектов. Люди различных профессий часто передают друг другу информацию разного рода. Для того, чтобы делать это оперативно и точно постоянно появляются все новые и новые слова самых разных значений.
Многие профессиональные отрасли распространяются далеко за границы государств. Поэтому с развитием науки и техники стали появляться формальные языки. Многие формальные языки конструировались на базе языка математики. Большое развитие некоторые из них получили в двадцатом веке. В таких языках одинаковые сочетания знаков всегда имеют одинаковый смысл. То есть каждое слово в таком языке можно интерпретировать только однозначно. Свои формальные языки применяются специалистами в конкретных профессиональных областях и часто они применяются на международном уровне. Например, химические формулы и нотная грамота.
К формальным языкам относится и десятичная система счисления. Она позволяет записывать числа, называть их и выполнять над ними ряд математических операций. Информатика тоже изучает некоторые формальные языки. Среди них есть языки программирования, язык формальной логики и языки запросов к базам данных. С некоторыми из них вы познакомитесь во время изучения информатики в школе.
Главная особенность всех формальных языков в том, что все их правила носят явный характер, то есть отправитель и получатель всегда воспринимают информацию однозначно.
Из предыдущих уроков мы помним, что одной из разновидностей обработки информации является её кодирование. Так называется изменение формы представления информации на более удобную для её хранения и передачи. Существует всего две формы представления информации: знаковая и образная. К знаковой форме представления относится информация на одном из естественных или формальных языков. Это может быть набор предложений на русском, английском или другом языке, понятном получателю. Это может быть набор математических или химических формул, или алгоритм, который записан на одном из языков программирования. Примеры представления информации в образной форме – это изображение или звук.
Формы представления информации
Как мы помним из прошлых уроков, информационные сигналы могут быть двух видов: непрерывные и дискретные. Непрерывные информационные сигналы могут принимать бесконечное множество значений на некотором непрерывном промежутке. А дискретные сигналы могут иметь лишь конечное число значений.
Главная разница между знаковой и образной формами представления информации в том, что знаковая информация всегда состоит из дискретных сигналов. Мы можем подсчитать количество буков в алфавите, цифр в десятичной системе счисления или фонем в русском языке. То есть на каждой знаковой позиции при такой форме представления может стоять символ из строго определённого конечного набора. Информация в образной форме всегда состоит из непрерывных сигналов. Можно бесконечно уточнять громкость каждого конкретного звука, или цвет каждой отдельной точки на рисунке. Большая часть информационных сигналов, которые получает человек, непрерывны. Однако компьютер работает лишь с дискретными величинами. Для того, чтобы информацию можно было точно сохранить или передать с помощью компьютера, нужно закодировать её в знаковой форме, то есть представить в виде дискретных сигналов, например в виде цифр.
· Все языки, используемые людьми, можно разделить на естественные и формальные.
· К естественным языкам относятся языки, на которых люди общаются между собой, это все языки народов мира. Они возникли естественным образом, длительно развивались и продолжают развиваться. Такие языки имеют достаточную гибкость, однако информация, которая на них записана, воспринимается субъективно.
· Большинство формальных языков были созданы искусственно. В них одни и те же сочетания знаков всегда имеют одинаковые значения, то есть информация, которая на них записана всегда объективна.
· Человек может представлять информацию в знаковой и образной форме.
· Информация в знаковой форме записана на каком-либо формальном или неформальном языке и имеет дискретную, то есть прерывную форму.
· В образной форме информация представляется звуком или изображением и имеет непрерывную форму.