Теория автоматов Часть 2

Как происходят стратегические изменения

Матрица “изменения - сопротивления”

Отношение к изменениям
“Сторонник”	“Противник”
Пассивные сторонники	Опасный элемент	Открытое	Проявление отношения к изменениям
Да	Нет	Скрытое

Выявить опасный элемент.

Перетянуть противника в пассивные сторонники.

Руководство может выработать несколько стилей для уменьшения сопротивления изменениям:

1. Конкурентный (победитель - побежденный)

2. Самоустранения (а что произойдет дальше)

3. Компромиссный – паритетность (чтобы было выгодно всем)

4. Приспособленческий – руководство будет ориентировано под ранее сложившиеся структуры.

Чем выше сопротивление изменениям, тем больше нестабильность системы.

Формальные грамматики и языки. Применение.

Основные понятия и определения

Теория формальных грамматик (ФГ) дает:

- способы задания входных данных;

- способы задания и генерации выходных данных;

- способы задания функции, алгоритма преобразования входных данных в выходные;

- способы анализа входных данных

и др.

Основное применение ФГ:

- разработка собственных компиляторов;

- разработка переводчиков;

- преобразование строк, массивов;

- разработка поисковых запросов.

Опр. Алфавит V - конечное непустое множество элементов, называемых символами (буквами).

Опр. Цепочкой a в алфавите V называется любая конечная последовательность символов этого алфавита.

Пример. Пусть алфавит V = {a,b,c}. Тогда baaa является словом в алфавите V.

Опр. Цепочка, которая не содержит ни одного символа, называется пустой цепочкой и обозначается e(l).

Опр. Длиной цепочки w называется число составляющих ее символов (обозначается | w |), причём каждый символ считается столько раз, сколько раз он встречается в w.

Пример. Очевидно, |baaa| = 4 и | e | = 0.

Обозначим через V* множество, содержащее все цепочки в алфавите V, включая пустую цепочку e, а через V + - множество, содержащее все цепочки в алфавите V, исключая пустую цепочку e.

Пример. Пусть V = {1,0}, тогда V* = {e, 0,l,00,01,10,11,000,...},

а V+ ={0,1,00,01,10,11,000,...}.

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

Опр. Если х - слово и п Î N, то через х^п обозначается слово х × х ×... × x. По определению х⁰ = e.

Пример. ba³ = bааа и (ba)³ = bababa.

Опр. Говорят, что слово х - префикс (начало) слова у, если у = хи.

Опр. Говорят, что слово х - суффикс (конец) слова у, если у = их.

Опр. Говорят, что слово х — подслово слова у, если у = uxv для некоторых слов и и v.

Опр. Через |w|a обозначается количество вхождений символа а в слово w.

Пример. Если V = {a,b,c}, то |baaa| а = 3, |baaa| b = 1 и |baaa| c = 0.

Опр. Формальный язык – это множество конечных слов (строк, цепочек) над конечным алфавитом V.

Поскольку каждый язык является множеством, можно рассматривать операции объединения, пересечения, разности и дополнения языков, заданных над одним и тем же алфавитом (обозначения L1 È L2, L1 Ç L2, L1 — L2).

Пример. Множество {a, abb} является языком над алфавитом { a,b }.

Пример. Множество {a^kba^l | k ≤ l } является языком над алфавитом {a,b}.

Необходимо различать пустой язык L=0 и язык, содержащий только пустую цепочку: L={e}≠0.

Опр. Пусть L – язык над алфавитом V*. Тогда язык V* — L называется дополнением языка L относительно алфавита V. Когда из контекста ясно, о каком алфавите идёт речь, говорят просто, что язык V* — L является дополнением языка L.

Опр. Грамматика – система правил, предназначенная для задания множества цепочек и символов данного алфавита. G – грамматика; L(G) – язык этой грамматики.

Выделяют 3 группы формальных грамматик:

1. Порождающие (позволяют строить правильную цепочку в заданном алфавите с описанием ее строения и не позволяют строить ни одной неправильной цепочки).

2. Распознающие (позволяют определить к каждой входной цепочке: является ли она правильной; в случае положительного ответа распознающая ФГ выдает строение цепочки).

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

Способы описания языков

Конечный язык можно описать простым перечислением его цепочек.

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

Можно выделить два основных подхода для такого представления: механизм распознавания и механизм порождения (генерации).

Механизм распознавания (распознаватель), по сути, является процедурой специального вида, которая по заданной цепочке определяет, принадлежит ли она языку. Если принадлежит, то процедура останавливается с ответом «да», т. е. допускает цепочку; иначе – останавливается с ответом «нет» или зацикливается. Язык, определяемый распознавателем – это множество всех цепочек, которые он допускает.

Примеры распознавателей:

· Машина Тьюринга (МТ). Язык, который можно задать с помощью МТ, называется рекурсивно перечислимым. Вместо МТ можно использовать эквивалентные алгоритмические схемы: нормальный алгоритм Маркова (НАМ), машину Поста и др.

· Линейно ограниченный автомат (ЛОА). Представляет собой МТ, в которой лента не бесконечна, а ограничена длиной входного слова. Определяет контекстно-зависимые языки.

· Автомат с магазинной (внешней) памятью (МП-автомат). В отличие от ЛОА, головка не может изменять входное слово и не может сдвигаться влево; имеется дополнительная бесконечная память (магазин, или стек), работающая по дисциплине LIFO. Определяет контекстно-свободные языки.

· Конечный автомат (КА). Отличается от МП-автомата отсутствием магазина. Определяет регулярные языки.

Основной способ реализации механизма порождения — использование порождающих грамматик, которые иногда называют грамматиками Хомского. Порождающие ФГ являются наиболее важными и распространенными.

Порождающей ФГ называется четверка вида: G = (VT,VN,P,S),

где VN - конечное множество нетерминальных символов грамматики (обычно прописные латинские буквы);

VT - множество терминальных символов грамматики (обычно строчные латинские буквы, цифры, и т.п.), VT Ç VN = 0;

Р - множество правил вывода грамматики; элемент (α,β) множества Р называется правилом вывода и записывается в виде α→β (читается: «из цепочки α выводится цепочка β»)

S - начальный символ грамматики, S Î VN.

Для записи правил вывода с одинаковыми левыми частями вида α→β1, α→β2,…,α→βn используется сокращенная форма записи α→β1|β2|…|βn.

Пример. Грамматика G 1 = ({0, 1}, {A, S}, Р1, S), где множество Р1 состоит из правил вида: 1) S→0A1; 2) 0А→00А1; 3)А→ e.

Опр. Цепочка βÎ (VT È VN)* непосредственно выводима из цепочки αÎ (VT È VN)+ в грамматике G = (VT,VN,P,S) (обозначается: αÞβ ), если α=ξ1γξ2 и β=ξ1δξ2, где ξ1, ξ2, δ Î V*, γÎV+ и правило вывода γ→δ содержится во множестве Р.

Опр. Цепочка βÎ V* выводима из цепочки αÎ V+ в грамматике G =(VT,VN,P,S) (обозначается: αÞ*β ), если существует последовательность цепочек γ0,γ1,…,γn (n≥0) такая, что α=γ0Þγ1Þ…Þγn=β.

Пример. В грамматике G1 S=>*000111, т.к. существует вывод S => 0А1=> 00А11 => 000A111 => 000111.

Опр. Языком, порожденным грамматикой G = (VT, VN,P,S), называется множество всех цепочек в алфавите VT, которые выводимы из начального символа грамматики S с помощью правил множества Р, т.е. множество L(G)= {α Î V* |S Þ *α}.

Пример. Для грамматики G1 L(G1)={0 ⁿ 1 ⁿ | п>0}.

Опр. Цепочка αÎV *, для которой существует вывод S Þ *α, называется сентенциальной формой в грамматике G = (VT, VN,P, S).

Опр. Грамматики G1 и G2 называются эквивалентными, если L(G1) =L(G2).

Пример. Для грамматики G1 эквивалентной будет грамматика G2 = ({0, 1}, {S}, Р2, S), где множество правил вывода Р2 содержит правила вида S→0S1|01.

Классификация грамматик и языков по Хомскому

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

Тип 0. (формальные грамматики с фразовой структурой, неограниченные). Грамматика G = (VT, VN,P, S) называется грамматикой типа 0, если на ее правила вывода не накладывается никаких ограничений, кроме тех, которые указаны в определении грамматики. Любое правило α→β может быть построено с использованием произвольных цепочек α, βÎ(V_TÈV_N). Этот тип грамматик самый общий, включающий все грамматики. Однако некоторые грамматики могут принадлежать только к этому типу. Практического применения в силу своей сложности такие грамматики не имеют. Например:

P = TR→HT или abC→xDa.

Тип 1. (контекстно-зависимые, контекстные грамматики, грамматика непосредственно составляющих, НС-грамматика). К этому типу относятся контекстно-зависимые (КЗ) грамматики и неукорачивающие грамматики.

Грамматика G = (VT,VN,P,S) называется контекстно-зависимой грамматикой (КЗ-грамматикой), если каждое правило вывода из множества Р имеет вид αAβ→αγβ, где α, β∈V*, γ∈V+, A∈V_N.

Грамматика G = (VT,VN,P,S) называется неукорачивающий грамматикой, если каждое правило вывода из множества Р имеет вид αAβ→αγβ, где α, β∈V*, γ∈V+, A∈V_N и |A|<=|γ|.

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

Тип 2. (Контекстно-свободной грамматикой, КС-грамматикой, бесконтекстной грамматикой). Грамматика G = (VT,VN,P,S) называется контекстно-свободной грамматикой (КС-грамматикой), если ее правила вывода имеют вид: A→β, где β∈V+ (для неукорачивающих КС-грамматик, β∈V* для укорачивающих), A∈V_N. То есть грамматика допускает появление в левой части правила только нетерминального символа. КС-грамматики широко применяются для описания синтаксиса компьютерных языков (программирования).

Тип 3. (регулярная, Р-грамматика, линейная. К третьему типу относятся регулярные грамматики (автоматные) — самые простые из формальных грамматик. Они являются контекстно-свободными, но с ограниченными возможностями. Все регулярные

грамматики могут быть разделены на два эквивалентных класса:

· Грамматика G = (VT, VN, Р, S) называется праволинейной, если ее правила вывода имеют вид A→γB или A→γ, где γ∈V_T*, A, B∈V_N;

· Грамматика G = (VT, VN, Р, S) называется леволинейной, если ее правила вывода имеют вид A→Bγ или A→γ, где γ∈V_T*, A, B∈V_N.

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

Дата добавления: 2015-05-26