Формальные языки в информатике сообщение

Обновлено: 18.05.2024

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

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

Обсуждая проблему восприятия человеком информации из внешнего мира, нужно обратить внимание учеников на то, что человек обладает множеством каналов, по которым в его мозг (память) поступает информация. Эти каналы - наши органы чувств. Их пять: зрение, слух, вкус, обоняние, осязание. Если роль первых двух для восприятия информации очевидна, то понимание того, что вкусовые и осязательные ощущения, запахи также являются источниками информации, требуют пояснения. Объяснение этому следующее: мы помним запахи знакомых предметов, вкус знакомой пищи, на ощупь узнаем некоторые вещи. Но то, что мы помним, - хранится в нашей памяти. Значит, это тоже наши знания, а стало быть, информация.

Образная информация - это сохраненные в памяти ощущения человека от контакта с источником; она воспринимается всеми органами чувств человека.

Целью исследования в данной работе является проработка проблемы изучения основ линии представления информации в базовом курсе информатики.

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

Предметом исследования является теория и методика обучения информатике, а объектом является обучение представлению информации в базовом курсе информатики.

Глава 1. Представление информации

Роль и место понятия языка в информатике

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

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

С любым языком связаны следующие понятия: алфавит - множество используемых символов; синтаксис - правила записи языковых конструкций (текста на языке); семантика - смысловая сторона языковых конструкций; прагматика- практические последствия применения текста на данном языке.

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

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

Формальные языки в курсе информатики

В данном разделе хотелось бы рассказать о языках, используемых при работе ЭВМ, в компьютерных информационных технологиях.

Информацию, циркулирующую в компьютере, можно разделить на два вида: обрабатываемая информация (данные) и информация, управляющая работой компьютера (команды, программы, операторы).

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

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

Языки внешнего представления данных обычно приближены к привычной для человека форме: числа представляются в десятичной системе, при записи текстов используются алфавиты естественных языков, традиционная математическая символика и пр. В представлении структур данных используется удобная табличная форма (реляционные базы данных). Но и в этом случае всегда существуют определенные правила синтаксиса и семантики языка, применяется ограниченное множество допустимых символов. Внутренним языком представления действий над данными (языком управления работой компьютера) является командный язык процессора ЭВМ. К внешним языкам представления действий над Данными относятся языки программирования высокого уровня, входные языки пакетов прикладных программ, командные языки операционных систем, языки манипулирования данными в СУБД и пр.

Тема представления информации является сквозной в курсе информатики. Ключевым понятием этой темы выступает понятие языка.

Обсуждая проблему восприятия человеком информации из внешнего мира, нужно обратить внимание учеников на то, что человек обладает множеством каналов, по которым в его мозг (память) поступает информация. Эти каналы – наши органы чувств. То, что мы помним, - храниться в нашей памяти. Значит, это тоже наши знания, а стало быть, информация.

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

Образная информация – это сохраненные в памяти ощущения человека от контакта с источником; она воспринимается всеми органами чувств человека.

Далее речь будет идти лишь о символьной информации. Язык – это определенная система символьного представления информации. Языки делятся на 2 группы: естественные и формальные. Естественные языки – это исторически сложившиеся языки национальной речи. Формальные языки – это искусственно созданные языки для профессионального применения. Они носят международный характер и имеют письменную форму (язык математики, химии, нотная грамота и др.).

С любым языком связаны следующие понятия:

o алфавит – множество используемых символов;

o синтаксис – правила записи языковых конструкций (текста на языке);

o семантика – смысловая сторона языковых конструкций;

o прагматика – практические последствия применения текста на данном языке.

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

Формальные языки в курсе информатики

Информацию, циркулирующую в компьютере, можно разделить на два вида: обрабатываемая информация (данные) и информация, управляющая работой компьютера (команды, программы, операторы).

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

Для каждого типа данных различается внешнее (ориентированное на человека) и внутреннее (представление на носителях информации в компьютере) представление данных. В самом общем смысле можно сказать, что языком представления данных ЭВМ является язык двоичных кодов. Общим в нем является лишь двоичный алфавит: 0 и 1. Но для различных типов данных различаются правила синтаксиса и семантики языка внутреннего представления ( двоичный код 0100000100101011 на языке представления целых чисел обозначает десятичное число 16683, а на языке представления символьных данных – два символа А+. Таким образом, для разных типов данных используются разные языки внутреннего представления.

Внутренним языком представления действий над данными (языком управления работой компьютера) является командный язык процессора ЭВМ. К внешним языкам представления действий над данными относятся языки программирования высокого уровня, входные языки пакетов прикладных программ, командные языки операционных систем, языки манипулирования данными в СУБД и пр.

Роль и место понятия языка в информатике

Обсуждая проблему восприятия человеком информации из внешнего мира, нужно обратить внимание учеников на то, что человек обладает множеством каналов, по которым в его мозг (память) поступает информация. Эти каналы – наши органы чувств. То, что мы помним, - храниться в нашей памяти. Значит, это тоже наши знания, а стало быть, информация.

С любым языком связаны следующие понятия:

o алфавит – множество используемых символов;

o синтаксис – правила записи языковых конструкций (текста на языке);

o семантика – смысловая сторона языковых конструкций;

o прагматика – практические последствия применения текста на данном языке.

Формальные языки в курсе информатики

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

Этот текст задуман как популярное введение в теорию формальных языков и грамматик. Эта теория считается (и, надо сказать, справедливо) довольно сложной и запутанной. На лекциях студенты обычно скучают и экзамены тем более не вызывают энтузиазма. Поэтому и в науке не так много исследователей в этой тематике. Достаточно сказать, что за все время, с зарождения теории формальных грамматик в середине 50-х годов прошлого века и до наших дней, по этому научному направлению было выпущено всего две докторских диссертации. Одна из них была написана в конце 60-х годов Алексеем Владимировичем Гладким, вторая уже на пороге нового тысячелетия — Мати Пентусом.

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

Формальные языки

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

Но в теории формальных языков представляется важным изучить законы расположения слов рядом друг с другом, т.е. синтаксические свойства текстов. Для этого модель мешка слов выглядит бедной. Поэтому формальный язык задается как множество последовательностей, составленных из элементов конечного алфавита. Определим это более строго.

Алфавит представляет собой конечное непустое множество элементов. Эти элементы будем называть символам. Для обозначения алфавита обычно будем использовать латинское V, а для обозначения символов алфавита — начальные строчные буквы латинского алфавита. Например, выражение V = обозначает алфавит из двух символов a и b.

Цепочка представляет собой конечную последовательность символов. Например, abc — цепочка из трех символов. Часто при обозначении цепочек в символах используют индексы. Сами цепочки обозначают строчными символами конца греческого алфавита. Например, omega = a1. an — цепочка из n символов. Цепочка может быть пустой, т.е. не содержать ни одного символа. Такие цепочки будем обозначать греческой буквой эпсилон.

Наконец, формальный язык L над алфавитом V — это произвольное множеств цепочек, составленных из символов алфавита V. Произвольность здесь означает тот факт, что язык может быть пустым, т.е. не иметь ни одной цепочки, так и бесконечным, т.е. составленным из бесконечного числа цепочек. Последний факт часто вызывает недоумение: разве имеются реальные языки, которые содержат бесконечное число цепочек? Вообще говоря, в природе все конечно. Но мы здесь используем бесконечность как возможность образования цепочек неограниченной длины. Например, язык, который состоит из возможных имен переменных языка программирования C++, является бесконечным. Ведь имена переменных в C++ не ограничены по длине, поэтому потенциально таких имен может быть бесконечно много. В реальности, конечно, длинные имена переменных не имеют для нас особого смысла т.к. к концу чтения такого имени уже забываешь его начало. Но в качестве потенциальной возможности задавать неограниченные по длине переменные, это свойство выглядит полезным.

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

Формальные грамматики

Способ задания языка называет грамматикой этого языка. Таким образом, грамматикой мы называем любой способ задания языка. Например, грамматика L = (здесь n — натуральное число) задает язык L, состоящий из цепочек вида ab, aabb, aaabbb и т.д. Язык L представляет собой бесконечное множество цепочек, но тем не менее, его грамматика (описание) состоит всего из 10 символов, т.е. конечна.

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

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

Окрестностные грамматики

С другой стороны, легко можно построить конечный автомат, который распознает этот язык. Значит, класс языков, которые описываются окрестностными грамматиками, уже класса автоматных языков. Языки, задаваемые окрестностными грамматиками, будем называть шрейдеровскими. Таким образом, в иерархии языков можно выделить класс шрейдеровских языков, который является подклассом автоматных языков.

ГОСТ

Общее понятие кодирования информации

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

Естественные и формальные языки представления информации

Язык — это знаковая система для представления и передачи информации.

естественные (например, мимика и жесты, музыка, живопись, речь человека);
формальные (например, математическая символика, чертежи и схемы, нотная грамота, языки программирования).

Естественный язык можно формализовать. Так для формализации музыки изобрели нотную грамоту, для формализации речи создали национальные алфавиты (например, латинский ($26$ символов), русский ($33$ символа)), кроме этого арабские цифры, азбуку Морзе и т.д.

Естественные языки развивались веками и служили для общения людей между собой. Формальные языки разрабатываются для специальных применений.

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

Алфавиты представления информации

Первобытные люди для обозначения каждого нового предмета придумывали новые имена. Для получения необходимого разнообразия имен, названий они стали комбинировать звуки таким образом, чтобы получить в результате слова. Так в ходе эволюции человека появилась идея создания конечного алфавита, т.е. некоторого фиксированного набора знаков, из которого можно составить как угодно много слов. Комбинация знаков алфавита называется словом. Из слов можно составлять фразы, которые будут нести определенную смысловую нагрузку.

Готовые работы на аналогичную тему

Таким образом, алфавит – это упорядоченный набор символов или сигналов, который составляет основу языка.

Мощность алфавита - это количество составляющих его символов.

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

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

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

Общее понятие кодирования информации

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

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

Люди сохраняют свои знания, записывая их на различных носителях. Благодаря чему эти знания передаются не только в пространстве, но и во времени — от одного поколения к другому.

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

Каждый народ имеет свой язык, состоящий из набора символов (букв): русский, английский, японский и многие другие. Об этом уже упоминалось ранее.

Представление информации с помощью какого-либо языка часто называют кодированием.

Код — это набор символов либо условных обозначений, используемый для представления информации.

Алфавит кодирования содержит полный набор кодов.

Кодирование — это процесс представления информации с помощью кода.

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

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

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

В процессе развития технических средств появлялись новые способы кодирования информации. Так во второй половине XIX века американский изобретатель Сэмюэль Морзе придумал удивительно простой код, который применяется до сих пор. Используя этот код, информацию можно представить в виде: длинного сигнала (тире), короткого сигнала (точки) и отсутствия сигнала (паузы) для разделения букв. Таким образом, принцип кодирования сводился к использованию набора символов, расположенных в строго определенном порядке.

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

В настоящее время этот способ представления информации с помощью языка, в состав которого входит всего два символа: $0$ и $1$, называется двоичным кодированием информации и широко используется в технических устройствах, в том числе и в компьютере. Эти два символа $0$ и $1$ принято называть двоичными цифрами или битами (от англ. bit — Binary Digit - двоичный знак).

Каждому человеку ежедневно в бытовых условиях приходится сталкиваться с устройствами, которые могут находиться только в двух устойчивых состояниях: включено или выключено. И это хорошо известные всем выключатели. Однако изобрести выключатель, который был бы способен устойчиво и быстро переключаться в любое из $10$ состояний, оказалось невозможно. В итоге после ряда неудачных попыток разработчики сделали вывод о невозможности создания компьютера на основе десятичной системы счисления. Поэтому представление чисел в компьютере осуществляется с помощью двоичной системы счисления.

Способ кодирования информации зависит от цели, которая при этом должна быть достигнута. Целью может являться сокращение записи, засекречивание (шифровка) информации, или, напротив, достижение взаимопонимания. Например, система дорожных знаков, флажковая азбука на флоте, специальные научные языки и символы ― химические, математические, медицинские и др., предназначены для того, чтобы люди могли общаться и понимать друг друга. От того, как представлена информация, зависит способ ее обработки, хранения, передачи и т.д.

Читайте также: