Программа построения грамматики для конечного автомата

37

Введение

Электронные средства связи это техника передачи информации из одного места в другое в виде электрических сигналов, посылаемых по проводам, кабелю, оптоволоконным линиям или вообще без направляющих линий. Направленная передача по проводам обычно осуществляется из одной конкретной точки в другую, как, например, в телефонии или телеграфии. Ненаправленная передача, напротив, обычно используется для передачи информации из одной точки на множество других точек, рассеянных в пространстве, т.е. в широковещательных целях. Примером ненаправленной передачи может служить радиовещание. Каждый этап развития электроники сопровождался значительным повышением надежности электронных компонентов. При этом удавалось также существенно уменьшить размеры, потребляемую мощность и стоимость многих видов электронной аппаратуры. Широкое применение такой техники, как компьютеры, волоконно-оптические линии, спутники связи, телефоны прямого набора, видеотелефоны, транзисторные радиоприемники и кабельное телевидение, привело к полному пересмотру традиционной классификации методов связи. Сейчас уже практически не отождествляют передачу по проводам с прямой адресной связью, а беспроводную передачу - с радиовещанием. Вероятно, наиболее сильное влияние на развитие техники связи оказало значительное увеличение пропускной способности средств связи как по эфиру, так и по проводам. Эта возросшая пропускная способность используется для постоянно увеличивающегося глобального трафика телевидения, телефонии и цифровой информации. Спутники связи. Первые спутники связи, размещавшиеся на околоземных орбитах в начале 1960-х годов, несли аппаратуру пассивного типа и служили лишь ретрансляторами сигнала. Современные спутники связи обычно выводятся на геостационарную орбиту высотой 35 900 км над поверхностью Земли. На каждом спутнике имеется 10 или большее число микроволновых приемников и передатчиков. Современный спутник позволяет передавать через океаны на целые континенты несколько телевизионных программ и обеспечивать работу более десятков тысяч телефонных каналов. Кабели. Во время Первой мировой войны специалисты по технике связи разработали метод использования пары проводов для одновременной передачи нескольких телефонных разговоров. Этот метод, названный частотным уплотнением каналов, основан на возможности передачи по паре проводов широкого спектра звуковых частот. При этом сигналы каждого из нескольких передатчиков разносятся по частоте (с помощью модуляции) и полученный более высокочастотный объединенный сигнал передается на приемный терминал, где разделяется на составляющие сигналы посредством демодуляции. Телефонный кабель с защитной оболочкой может содержать от десятков до сотен скрученных проводных пар, каждая из которых позволяет обеспечить работу до 24 телефонных каналов. Однако кабелям, состоящим из проводных пар, присущи определенные ограничения. С превышением некоторой частоты сигналы, передаваемые по одной паре, начинают создавать помехи сигналам соседней пары. Чтобы решить эту проблему, была разработана передающая среда нового типа - коаксиальный кабель. Такой кабель, содержащий 22 коаксиальные пары, может обеспечить одновременную работу 132 000 телефонных каналов. Каждая пара в таком кабеле представляет собой центральный провод, заключенный в трубку второго проводника. Центральный проводник и трубка электрически изолированы друг от друга. Импульсно-кодовая модуляция. Этот способ передачи сигналов средствами цифровой техники особенно удобен при использовании больших интегральных схем (БИС и СБИС), а также волоконно-оптических линий. Такая цифровая (ИКМ) передача речи и ТВ-сигналов в конце концов заменит другие средства связи. При использовании импульсно-кодовой модуляции сигналы речи или изображения можно разделять на множество малых временных интервалов; на каждом интервале ряд импульсов постоянной амплитуды представляет сигнал. Эти импульсы посылаются на принимающую станцию вместо оригинальных сигналов. Одно из преимуществ ИКМ связано с тем, что дискретные электронные импульсы постоянной амплитуды нетрудно отличить от случайных помех произвольной амплитуды (электростатического происхождения), которые в той или иной степени присутствуют в любой среде передачи. Такие импульсы можно передавать, по существу, без помех от стороннего шума, так как их легко отделить. ИКМ используется для самых разных сигналов. Телеграфные и факсимильные сообщения, а также другие данные, которые ранее пересылались по телефонным линиям другими методами, можно гораздо более эффективно передавать в импульсной форме. Трафик таких неречевых сигналов непрерывно возрастает; существуют также системы, позволяющие передавать смешанные сигналы речи, данных и видеоинформации. Видеотелефон. Новые средства электроники позволяют дополнять изображениями передаваемую по телефону звуковую информацию. Видеопередачи между конференц-залами, находящимися в нескольких городах, используются для того, чтобы избежать необходимости переездов участников конференций. Видеопередачи начали широко применяться для обучения - лекции передаются из одной аудитории в другую (удаленную) и записываются на видеоленту для использования в тех же целях. Системы кабельного телевидения. Хотя лазерное излучение и миллиметровые волны могут быть использованы для вещания, ограничения, обусловленные поглощением в атмосфере, и разные помехи другого рода удается преодолеть лишь ценой больших затрат. Поэтому при поиске путей расширения вещания, позволяющих избежать ограничений, связанных с использованием электромагнитных излучений, все больше используются кабельные системы. Для кабельного телевидения требуется прокладка кабелей от передающих до принимающих станций, расположенных, например, в домах. Радиослушатель или телезритель кабельного вещания не испытывает неудобств от замираний, двоения изображений и других помех. Кроме того, благодаря тому, что число каналов, передаваемых по кабелю, практически неограниченно (тогда как обычная станция ТВ-вещания передает в данный момент лишь одну программу), телезрителю предоставляется гораздо более широкий выбор программ. Модемы. В последнее время модемы становятся неотъемлемой частью компьютера. Установив модем на компьютер, перед вами открывается новый мир. Модем позволяет, не выходя из дома, получать доступ к базам данных, которые могут быть удалены от вас на многие тысячи километров. Кроме того, воспользовавшись глобальными сетями (RelCom, FidoNet, Internet) можно принимать и посылать электронные письма не только внутри города, но и в любой конец земного шара. Глобальные сети дают возможность не только обмениваться почтой, но и участвовать во всевозможных конференциях, получать новости по любой интересующей вас тематике. Интернет. Глобальная компьютерная сеть, охватывающая весь мир. Сегодня интернет имеет около 19 миллионов абонентов в более чем 150 странах мира. Ежемесячно размер сети увеличивается на 7-10%. Интернет образует как бы ядро, обеспечивающее связь различных информационных сетей, принадлежащих различным учреждениям во всем мире, одна с другой. Если ранее сеть использовалась исключительно в качестве среды передачи файлов и сообщений электронной почты, то сегодня решаются более сложные задачи распределенного доступа к ресурсам. Около двух лет назад были созданы оболочки, поддерживающие функции сетевого поиска и доступа к распределенным информационным ресурсам, электронным архивам. Кроме того интернет предоставляет уникальные возможности дешевой, надежной и конфиденциальной глобальной связи по всему миру. Это оказывается очень удобным для фирм имеющих свои филиалы по всему миру, транснациональных корпораций и структур управления. Обычно, использование инфраструктуры интернета для международной связи обходится значительно дешевле прямой компьютерной связи через спутниковый канал или через телефон.

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

а) входной алфавит V конечного автомата (конечное множество входных символов, которые будет распознавать КА);

б) конечное множество состояний S;

в) начальное состояние КА - s0 (состояние, с которого начинает работу КА при обработке новой цепочки);

г) множество допускающих состояний - Sдоп (подмножество состояний, с элементами которого сравнивается достигнутое КА состояние после прихода символа "конец цепочки");

д) таблица переходов (управляющая таблица), которая паре "текущее состояние - входной символ" ставит в соответствие новое состояние КА из множества состояний S).

- В множество входных символов обязательно включают особый символ "конец цепочки", который сообщает КА о том, что нужно достигнутое состояние si сравнить с элементами множества Sдоп и, если si Sдоп, пропустить цепочку; в противном случае цепочка отвергается.

В коде программы этот символ будет иметь вид « * ». Часто при распознании цепочек возникает ситуация, когда невозможно текущей паре "состояние - входной символ" поставить в соответствие новое состояние. По сути это означает, что цепочка не принадлежит распознаваемому множеству, хотя она и не просмотрена до символа "конец цепочки". Такие ситуации в таблице переходов помечаются символом "error"; попав в такое состояние, КА отвергает проверяемую цепочку и переходит в начальное состояние.

КА всегда начинает работать из начального состояния s0. Символы распознаваемой цепочки поступают посимвольно, начиная с первого, и изменяют состояния КА в соответствии с таблицей переходов. После поступления символа "конец цепочки" достигнутое автоматом состояние фиксируется и сравнивается с множеством допускающих состояний. На основании этого сравнения цепочка допускается или отвергается.

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

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

- распознаваемые цепочки содержат определенные сочетания символов в начале, конце или (и) середине цепочки;

- распознаваемые цепочки содержат ограниченное число повторений определенных символов или их сочетаний (не больше n; точно n; не меньше n, причем n = 1,2,3);

- распознаваемые цепочки содержат запрет на определенные сочетания символов в начале, конце или (и) во всей цепочке;

- распознаваемые цепочки содержат комбинации названных выше ограничений.

1.1.2 Эквивалентные состояния КА

Состояния s и t двух различных конечных автоматов эквивалентны тогда и только тогда, когда первый КА, начав работу из состояния s, будет допускать те же цепочки, что и второй КА, начав работу из состояния t. Если эти состояния начальные, то эти автоматы эквивалентны.

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

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

Эквивалентные состояния, принадлежащие одному КА, не нарушая эквивалентности, можно заменить одним (в таблице переходов оставить одну из строк эквивалентных состояний, удалив остальные, при этом заменить имена удаленных состояний на оставленное).

1.1.3 Недостижимые состояния КА

Недостижимыми называются такие состояния КА, которые не могут быть достигнуты из начального состояния воздействием любых входных символов.

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

Шаг 1: записать одноэлементное множество, в которое входит начальное состояние.

Шаг 2: дополнить это множество состояниями, в которые переходит КА из состояний, уже присутствующих в множестве при воздействии любых входных символов.

Шаг 3: если на шаге 2 множество не пополняется новыми элементами, то получен исчерпывающий список достижимых состояний; остальные состояния КА недостижимы

Конечный автомат, в котором исключены недостижимые и эквивалентные состояния называется минимальным КА.

Страницы: 1, 2, 3