Главная Обратная связь

Дисциплины:






Минимизация детерминированного конечного автомата.



Было доказано, что для каждого ДКА можно определить единственный минимальный (с точностью до наименований состояний) ДКА.

В автомате некоторые состояния могут быть эквивалентными.

Состояние Si и Sj эквивалентны при выполнении двух условий:

1) оба конечные

2) оба не конечные, но для каждого входного символа они имеют переходы в эквивалентное состояние.

Алгоритм минимизации:

1) разбиваем множество состояний КА на два подмножества – финальное и не финальное.

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

При минимизации конечного автомата все состояния делятся на две группы: финальные и нефинальные. Затем выполняется следующая процедура. Рассматриваем группу {S1, S2, …, Sk} и некоторый входной символ а. Если по этому входному символу есть переходы в разные группы, то исходную группу разбивают на части. Принадлежность Si к той или иной части зависит от того, в какую группу существует переход из состояния Si по входному символу а. Эта процедура продолжается до тех пор, пока не останется ни одной группы, которую можно было бы разбить по какому-либо входному сигналу.

 

Контекстно-свободные языки. Вывод. Дерево вывода.

КСЯ можно разбирать на части. Паскаль имеет вложенную структуру. If E then S1 (оператор) else S2 (оператор). Здесь можно выделить синтаксические категории (S1) – нетерминалы и ключевые слова – терминалы (имеют законченный вид). Для описания синтаксиса ЯП используется БНФ. В ней даются определения нетерминалов через терминалы и нетерминалы. Для оператора if:

<оператор>::= if <выражение> then <оператор> else <оператор>. Далее каждый оператор также можно раскрыть.

Для каждой грамматики можно определить правило непосредственного вывода: если определены последовательности символов a и b такие, что aÎ V* и bÎ V* (конечное множество грамматических символов), и если задана продукция А→gÎР, то из последовательности символов aАb можно получить agb.

Здесь → означает применение правила подстановки или непосредственного вывода.

Допустим, если есть последовательность аАВС, то используя грамматику, применив правило 5 только к В, получим:

аАВС→аАвВС

Выводомназывается последовательность постановок, она обозначается a→*b. Эта запись означает, что из a выводится b за 0 или более шагов.a →+b: из a выводится b за 1 или более шагов.

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

Вывод цепочки можно представить в виде дерева. Если на каждом шаге заменяется самый левый нетерминал, то вывод называется левосторонним, если самый правый, то правосторонний.

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





sdamzavas.net - 2018 год. Все права принадлежат их авторам! В случае нарушение авторского права, обращайтесь по форме обратной связи...