Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 11)

Определение формальной грамматики требует наличия еще одного алфавита V_N – непустого конечного множества нетерминальных символов (V_N ∧ V_Т = 0). Объединение этих алфавитов назовем словарем формального языка L: V = V_N ∨ V_Т.

Условимся обозначать элементы алфавита V_Т строчными латинскими буквами, элементы множества V_N – прописными латинскими буквами, элементы словаря V*, (цепочки символов словаря) – греческими буквами.

Определим также множество упорядоченных пар (полутуэвских соотношений) следующим образом:

П = {(α, β) | α ∈ V* V_N V* ∧ β ∈ V+}.

Каждая пара (α, β) называется продукцией и обозначается как α → β.

Заметим, что β является элементом усеченной итерации словаря, поэтому среди продукций нет пар вида α → ε, где ε – пустая цепочка.

Определение.

Формальная грамматика G – это совокупность четырех объектов (четвёрка): G = (V_T, V_N, P, S),

где V_Т – алфавит терминальных символов (множество основных понятий языка);

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

Р – непустое конечное подмножество продукций (П) – полутуэвская система подстановок;

S ∈ V_N – множества начальных символов.

Определение.

Языком L(G), порождаемым грамматикой G, будем называть множество цепочек α ∈ V_Т , каждая из которых порождается из начального символа S в смысле полутуэвских соотношений Р данной грамматики. Другими словами, L(G) = {α | α ∈ V_T* ∧ S ⇒ *α}.

29.Классификация формальных языков по Хомскому.

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

Типы грамматик по Хомскому располагаются по убыванию сложности языка и обозначают: тип 0, тип 1, тип 2 и тип 3.

Соответствующий тип грамматики определяется теми ограничениями, которые налагаются на продукцию Р.

Рис. 3.1. Иерархия грамматик, языков и автоматов.

Определение.

Если никаких ограничений нет, то грамматика принадлежит к типу 0 — грамматика без ограничений.

Определение.

Ограничение, налагаемое на длину цепочек α и β: | α | ≤ | β |, относит грамматики к типу 1. Такие грамматики также называют контекстно-зависимыми, то есть грамматиками непосредственных составляющих (НС-грамматиками).

Определение.

В том случае, когда цепочка α состоит из одного символа, т. е. α ∈ V_N, грамматики относят к типу 2. В этом случае их называют бесконтекстными (контекстно-свободными или КС-грамматиками).

Определение.

Регулярными грамматиками (типа 3) называют такие, для которых α ∈ V_N , а β ∈ V_Т V_N, либо β ∈ V_Т. Иными словами, правые части продукций регулярных грамматик состоят либо из одного терминального и одного нетерминального символов, либо из одного терминального символа.

Нетрудно видеть, что каждая регулярная грамматика является бесконтекстной, а каждая бесконтекстная грамматика является контекстно-зависимой. В свою очередь, каждая контекстно-зависимая грамматика – это грамматика типа 0. Обратное утверждение неверно.

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

С другой стороны, типы языков могут быть определены типами абстрактных распознающих устройств (автоматов). При этом язык определяется как множество цепочек, допускаемых распознающим устройством определенного типа. На рис. 3.1 приведена иерархия языков и соответствующие ей иерархии грамматик и автоматов как распознающих устройств. Любое множество, порождаемое автоматическим устройством произвольного вида, порождается некоторой грамматикой типа 0 по Хомскому.

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

Таким образом, грамматики типа 0 представляют собой порождающие устройства очень общего характера. Формальные языки, с которыми имеют дело автоматно-лингвистические модели (язык программирования, ограниченные естественные языки), как показывает практика, всегда описываются языками типа 1 или 2.

Языки типа 3, которые называют автоматными языками, языками с конечным числом состояний, нашли широкое применение в исследовании электронных схем, а также в ряде других областей (например, исследование цепей Маркова).

1. Теория автоматов.

30. Основные понятия теории автоматов.

Термин «автомат», как правило, используется в двух аспектах.

С одной стороны, автомат — это устройство, выполняющее некоторые функции без непосредственного участия человека. В этом смысле мы говорим, что ЭВМ – автомат, так как после загрузки программы и исходных данных ЭВМ решает заданную задачу без участия человека.

С другой стороны, термин «автомат» как математическое понятие обозначает математическую модель реальных технических автоматов. В этом смысле автомат представляется как «черный ящик», имеющий конечное число входов и выходов и некоторое множество внутренних состояний Q = {q₁(t), q₂(t), ..., q_n(t)}, в которые он под действием входных сигналов переходит скачкообразно, то есть практически мгновенно, минуя промежуточное состояние. Конечно, это условие не выполняется в реальности, так как любой переходный процесс длится конечное время.

Определение.

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

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

Результатом работы цифрового автомата является выдача выходных сигналов.

В отношении выходных сигналов вводятся допущения, аналогичные допущениям для входных сигналов. Во-первых, число различных выходных сигналов для любого цифрового автомата всегда конечно. Во-вторых, каждому отличному от нуля моменту автоматного времени относится соответствующий ему входной сигнал. Реальный физический выходной сигнал y(t), отнесенный к моменту времени t, появляется всегда после соответствующего этому же моменту времени входного сигнала x(t). Что же касается момента времени t перехода автомата из состояния q(t–1) в состояние q(t), то сигнал y(t) может фактически появится либо раньше, либо позже этого момента.

В первом случае принимается, что выходной сигнал y(t) однозначно определяется входным сигналом x(t) и состоянием q(t–1) автомата в предыдущий момент времени, во втором случае сигнал y(t) однозначно определяется парой (x(t), q(t)).

Будем считать, что для любого момента времени всегда имеет место лишь одна из этих возможностей (одновременно для всех переходов).

Определение.

Цифровые автоматы, в которых выходной сигнал y(t) определяется парой (x(t), q(t – 1)), будем называть автоматами первого рода или автоматами Мили, а автоматы, в которых сигнал y(t) определяется парой (x(t), q(t)), – автоматами второго рода или автоматами Мура.

Определение.

Цифровой автомат (первого или второго рода) называется правильным, если выходной сигнал y(t) определяется одним лишь его состоянием (q(t –1) или q(t)) и не зависит явно от входного сигнала x(t).

Общая теория автоматов разбивается на две большие части, которым присвоены названия абстрактной теории автоматов и структурной теории автоматов.

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

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

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

Частным случаем дискретных автоматов являются автоматы, обладающие лишь одним внутренним состоянием. Такие автоматы называются комбинационными схемами или автоматами без памяти. Работа таких автоматов состоит в том, что они сопоставляют каждому входному сигналу x(t) выходной сигнал y(t).

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

31. Способы задания автоматов. Таблица переходов.

Определение.

Таблица переходов (таблица выходов) автомата Мили представляет собой таб­лицу, в которой левый столбец обозначается входными сигналами (алфавитом не терминалов), а верхняя строка – состояниями, начиная с начального состояния. На пересечении строки и столбца ука­зывается следующее состояние, в которое переходит автомат (в таблице переходов) или выходной сигнал, выдаваемый им (в таблице выходов).

Представим автоматы Мили и Мура табличным способом.

Описание работы автомата Мили таблицами переходов и выходов иллюстриру­ется на примере автомата А₁ (рис. 4.1): Х – алфавит входных сигналов; Y – алфавит выходных сигналов; Q - алфавит состояний; – функция переходов; X – функция вы­ходов

Рис. 4.1. Таблицы переходов (а) и выходов (б) автомата А₁.

Автомат, имея один вход и один выход, работает в дискретном времени, принимающем значения t = 1, 2, 3, ... На вход автомата поступают входные сигналы x_f (например, сигналы x₁ и x₂). В каждый момент t автомат находится в некотором состоянии q(t), начиная с начального состояния q₁.

На пересечении столбца q_m и строки x_f в таблице переходов ставится состояние q_s = δ (q_m, x_f), в которое автомат переходит из состояния q_m под действием сигнала x_f, а в таблице выходов – соответствующий этому переходу выходной сигнал y_g = λ (q_m, x_f).

Определение.

Иногда при задании автоматов Мили используют одну совмещенную таблицу переходов и выходов, в которой на пересечении столбца q_m и строки x_f записываются в виде q_s / y_g следующее состояние и выдаваемый выходной сигнал.

На рис. 4.2 представлена совмещенная таблица автомата А₁.

Характеристики

Список файлов лекций