Было доказано, что для каждого ДКА можно определить единственный минимальный (с точностью до наименований состояний) ДКА. В автомате некоторые состояния могут быть эквивалентными.
Состояние Si и Sj эквивалентны при выполнении двух условий:
- 1) оба конечные
- 2) оба не конечные, но для каждого входного символа они имеют переходы в эквивалентное состояние.
Алгоритм минимизации:
- 1) разбиваем множество состояний КА на два подмножества — финальное и не финальное.
- 2) последовательно разбиваем подмножества на более мелкие части, если есть состояния, имеющие переходы в разные группы.
Контекстно-свободные языки. Вывод. Дерево вывода
КСЯ можно разбирать на части. Паскаль имеет вложенную структуру. If E then S1 (оператор) else S2 (оператор). Здесь можно выделить синтаксические категории (S1) — нетерминалы и ключевые слова — терминалы (имеют законченный вид). Для описания синтаксиса ЯП используется БНФ (Форма Бэкуса-Наура). В ней даются определения нетерминалов через терминалы и нетерминалы. Для оператора if:
:= if then else. Далее каждый оператор также можно раскрыть.
Для каждой грамматики можно определить правило непосредственного вывода: если определены последовательности символов и такие, что V* и V* (конечное множество грамматических символов), и если задана продукция А>Р, то из последовательности символов, А можно получить .
Здесь > означает применение правила подстановки или непосредственного вывода.
Выводом называется последовательность постановок, она обозначается >*. Эта запись означает, что из выводится за 0 или более шагов. >+: из выводится за 1 или более шагов.
Каждая цепочка символов, встречающихся в выводе, называется промежуточной цепочкой. Если промежуточная цепочка выводима из начального символа, то она называется выводимой цепочкой (сентенциальной формой).
Вывод цепочки можно представить в виде дерева. Если на каждом шаге заменяется самый левый нетерминал, то вывод называется левосторонним, если самый правый, то правосторонний.
В общем случае грамматика может порождать несколько различных деревьев вывода для одной и тоже цепочки (неоднозначная). Однозначная — если каждой выводимой цепочке соответствует единственное дерево вывода.
