6. Минимизация числа состояний методом таблиц.

Пример: Пусть задан автомат следующей автоматной таблицей.

Таблица Р₀

y_i=(x_i;s_i) s_i+1=δ(x_i, s_i)

				
si \ xi						
1	1	0	0	2	2	5
2	0	1	1	1	4	4
3	1	0	0	2	2	5
4	0	1	1	3	2	2
5	1	0	0	6	4	3
6	0	1	1	8	9	6
7	1	0	0	6	2	8
8	1	0	0	4	4	7
9	0	1	1	7	9	7

Автоматная таблица– таблица выходов и таблица переходов.

Строят таблицу Р₁, при этом изменяют порядок следования строк так, чтобы одинаковые строки стали соседними. Каждая группа таких строк в таблице выходов соответствует классу эквивалентности.

Таблица Р₁

	si \ xi			
A	1	2b	2b	5a
	3	2b	2b	5a
	5	6b	4b	3a
	7	6b	2b	8a
	8	4b	4b	7a
B	2	1a	4b	4b
	4	3a	2b	2b
	6	8a	9b	6b
	9	7a	9b	7a

Каждое значение состояния s_i+1 в таблице Р₁снабжается индексом, указывающим группу, к которой данное состояние относится. Построение таблицы Р_k+1по таблице Р_k, гдеk1. Две смежные строки таблицы Р_к, имеющие во всех столбцах одинаковые индексы, являются смежными в таблице Р_к+1.Две смежные строки в таблице Р_к , имеющие в некоторых столбцах разные индексы, являются разобщенными в таблице Р_к+1. Разобщенные строки в таблице Р_к являются также разобщенными в таблице Р_к+1. Группа, состоящая из одной строки таблицы Р_к , состоит из одной строки и в таблице Р_к+1.Таблица Р_к+1 строится до тех пор, пока не будет получена таблица, в которой все смежные строки имеют одинаковые индексы во всех столбцах.

Задание.

1. Минимизировать автомат Мили:

2. Минимизировать автомат Мура.

Тема 12. Языки, распознаваемые автоматами. Характеризация праволинейных языков. Нормальная форма праволинейных грамматик. Свойства замкнутости класса автоматных языков. Пересечение и дополнение автоматных языков.

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

Определение 1.1.1. Будем называть натуральными числами неотрицательные целые числа. Множество всех натуральных чисел {0, 1, 2, ...} обозначается N.

Определение 1.1.2. Алфавитом называется конечное непустое множество. Его элементы называются символами (буквами).

Определение 1.1.3.Словом (цепочкой, строкой, string) в алфавите Σ называется конечная последовательность элементов Σ.

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

Определение 1.1.5. Слово, не содержащее ни одного символа (то есть последовательность длины 0), называется пустым словом и обозначается ξ .

Определение 1.1.6. Множество всех слов в алфавите Σ обозначается Σ*

Замечание 1.1.7. Множество Σ* счетно. В самом деле, в алфавите Σ множество всех слов данной длины конечно, следовательно, Σ* является объединением счетного числа конечных множеств.

Определение 1.1.8. Множество всех непустых слов в алфавите Σ обозначается .

Пример 1.1.9. Если

Определение 1.1.10. Если , то L называется языком (или формальным языком) над алфавитом Σ.

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

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

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

Определение 1.1.13. Если x и y - слова в алфавите Σ, то слово xy (результат приписывания слова y в конец слова x) называется конкатенацией, (катенацией, сцеплением) слов x и y.

Определение 1.1.14. Если x - слово и , то через xn обозначается слово . Положим (знак читается "равно по определению"). Всюду далее показатели над словами и символами, как правило, являются натуральными числами.

Пример 1.1.15. По принятым соглашениям ba^3 = baaa и (ba)^3 = bababa.

Пример 1.1.16. Множество является языком над алфавитом {a,b}. Этот язык содержит слова b, ba, aba, baa, abaa, baaa, aabaa, abaaa, baaaa и т. д.

Определение 1.1.17. Длина слова w, обозначаемая |w|, есть число символов в w, причем каждый символ считается столько раз, сколько раз он встречается в w.

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

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

Пример 1.1.20. Если

Характеризация праволинейных языков

Теорема 2.1.1. Каждый автоматный язык является праволинейным.

Без ограничения общности можно предположить, что исходный язык задан конечным автоматом

Пример 2.1.2. Язык, распознаваемый конечным автоматом из примера 2.1.2, порождается грамматикой

Теорема 2.1.3. Каждый праволинейный язык является автоматным.

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

Пример 2.4.4. Пусть . Рассмотрим грамматику

Она эквивалентна грамматике

Язык, порождаемый этими грамматиками, распознается конечным автоматом , где и

.

Нормальная форма праволинейных грамматик

Определение 3.1.1. Праволинейная грамматика в нормальной форме (автоматная грамматика, регулярная грамматика, finite-state grammar) - это праволинейная грамматика, в которой каждое правило имеет вид

Теорема 3.1.2. Каждая праволинейная грамматика эквивалентна некоторой праволинейной грамматике в нормальной форме.

Теорема 3.1.3. Если праволинейный язык не содержит пустого слова, то он порождается некоторой праволинейной грамматикой в нормальной форме без ξ -правил.

Упражнения

Упражнение 1. Перечислить слова языка

Упражнение 2. Пусть . Равны ли языки

Упражнение 3. Пусть

. Сколько слов содержит язык L1 - L2?

Упражнение 4. Найти праволинейную грамматику, порождающую язык

.

Упражнение 5. Существует ли такая праволинейная грамматика G, что язык не порождается ни одной праволинейной грамматикой с количеством правил n + 1, где n - количество правил в грамматике G?

Упражнение 6. Найти праволинейную грамматику, эквивалентную грамматике

Упражнение 7. Найти праволинейную грамматику в нормальной форме без ξ-правил, порождающую язык

Упражнение 8. Найти праволинейную грамматику в нормальной форме без ξ-правил, порождающую язык