Лекции Русакова, страница 12

цепочек, состоящих только из терминальныхсимволов, выводимых из начального символа в грамматике G, называетсяязыком, порожденным грамматикой G, и обозначается L(G).Следовательно, применение грамматики – это построение полныхвыводов, последние цепочки которых и образуют язык, порожденныйграмматикой.Определение.Две различные грамматики могут порождать один и тот же язык, тоесть одно и то же множество терминальных цепочек. Такие грамматикиназываются эквивалентными грамматиками.114Пусть алфавит символов (непустое конечное множество), из которыхстроятся цепочки языка L, представляет собой алфавит терминальныхсимволов VТ. Очевидно, что L ≤ VТ *.Определение формальной грамматики требует наличия еще одногоалфавита VN – непустого конечного множества нетерминальных символов(VN ∧ VТ = 0).

Объединение этих алфавитов назовем словарем формальногоязыка L: V = VN ∨ VТ.Условимся обозначать элементы алфавита VТ строчными латинскимибуквами, элементы множества VN – прописными латинскими буквами,элементы словаря V*, (цепочки символов словаря) – греческими буквами.Определим также множество упорядоченных пар (полутуэвскихсоотношений) следующим образом:П = {(α, β) | α ∈ V* VN V* ∧ β ∈ V+}.Каждая пара (α, β) называется продукцией и обозначается как α → β.Заметим, что β является элементом усеченной итерации словаря,поэтому среди продукций нет пар вида α → ε, где ε – пустая цепочка.Определение.Формальная грамматика G – это совокупность четырех объектов(четвёрка): G = (VT, VN, P, S),где VТ – алфавит терминальных символов (множество основныхпонятий языка);VN – непустое конечное множество нетерминальных символов(вспомогательных понятий – обозначений конкретных классов слов,например, глаголов или предлогов, слогов, букв);Р – непустое конечное подмножество продукций (П) – полутуэвскаясистема подстановок;115S ∈ VN – множества начальных символов.Определение.ЯзыкомL(G),порождаемымграмматикойG,будемназыватьмножество цепочек α ∈ VТ , каждая из которых порождается из начальногосимвола S в смысле полутуэвских соотношений Р данной грамматики.Другими словами, L(G) = {α | α ∈ VT* ∧ S ⇒ *α}.3.04.

КлассификацияформальныхязыковпоХомскому.Н. Хомский определил четыре типа грамматик, на основе которыхоцениваются возможности других способов описания языков.Типы грамматик по Хомскому располагаются по убыванию сложностиязыка и обозначают: тип 0, тип 1, тип 2 и тип 3.Соответствующий тип грамматики определяется теми ограничениями,которые налагаются на продукцию Р.116Рис. 3.1. Иерархия грамматик, языков и автоматов.Определение.Если никаких ограничений нет, то грамматика принадлежит к типу 0— грамматика без ограничений.Определение.Ограничение, налагаемое на длину цепочек α и β: | α | ≤ | β |, относитграмматики к типу 1.

Такие грамматики также называют контекстнозависимыми, то есть грамматиками непосредственных составляющих (НСграмматиками).Определение.В том случае, когда цепочка α состоит из одного символа, т. е. α ∈ VN,грамматики относят к типу 2. В этом случае их называют бесконтекстными(контекстно-свободными или КС-грамматиками).117Определение.Регулярными грамматиками (типа 3) называют такие, для которых α∈ VN , а β ∈ VТ  VN, либо β ∈ VТ. Иными словами, правые частипродукций регулярных грамматик состоят либо из одного терминального иодного нетерминального символов, либо из одного терминального символа.Нетрудно видеть, что каждая регулярная грамматика являетсябесконтекстной, а каждая бесконтекстная грамматика является контекстнозависимой.

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

На рис. 3.1 приведена иерархия языков исоответствующие ей иерархии грамматик и автоматов как распознающихустройств. Любое множество, порождаемое автоматическим устройствомпроизвольного вида, порождается некоторой грамматикой типа 0 поХомскому.Заметим, что для любого естественного языка, в принципе, возможнопостроить математическую модель, использующую такую грамматику.Таким образом, грамматики типа 0 представляют собой порождающиеустройства очень общего характера. Формальные языки, с которыми имеютделоавтоматно-лингвистическиемодели118(языкпрограммирования,ограниченные естественные языки), как показывает практика, всегдаописываются языками типа 1 или 2.Языки типа 3, которые называют автоматными языками, языками сконечным числом состояний, нашли широкое применение в исследованииэлектронных схем, а также в ряде других областей (например, исследованиецепей Маркова).Глава 4.

Теория автоматов.4.01. Основные понятия теории автоматов.Термин «автомат», как правило, используется в двух аспектах.С одной стороны, автомат — это устройство, выполняющее некоторыефункции без непосредственного участия человека. В этом смысле мыговорим, что ЭВМ – автомат, так как после загрузки программы и исходныхданных ЭВМ решает заданную задачу без участия человека.С другой стороны, термин «автомат» как математическое понятиеобозначает математическую модель реальных технических автоматов.В этом смысле автомат представляется как «черный ящик», имеющийконечное число входов и выходов и некоторое множество внутреннихсостояний Q = {q1(t), q2(t), ..., qn(t)}, в которые он под действием входныхсигналов переходит скачкообразно, то есть практически мгновенно, минуяпромежуточное состояние.

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

Во-вторых,каждому отличному от нуля моменту автоматного времени относитсясоответствующий ему входной сигнал. Реальный физический выходнойсигнал 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)), – автоматами второго рода или автоматами Мура.Определение.120Цифровойавтомат(первогоиливторогорода)называетсяправильным, если выходной сигнал y(t) определяется одним лишь егосостоянием (q(t –1) или q(t)) и не зависит явно от входного сигнала x(t).Общая теория автоматов разбивается на две большие части, которымприсвоены названия абстрактной теории автоматов и структурной теорииавтоматов.Различие между ними заключается в том, что в абстрактной теории неучитываются структура как самого автомата, так и структуры его входных ивыходных сигналов.

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

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