Эквивалентность конечных детерминированных распознавателей
Конечные распознаватели А и А’ эквивалентны, если равны допускаемые ими языки L(A)=L(A’). Множество цепочек, допускаемых состоянием s0 , образует язык L(s0). Естественно, что L(A)=L(s0), если s0 – начальное состояние распознавателя А и L(A’)=L(s0’), если s0’ - начальное состояние распознавателя А’ . Следовательно, для проверки истинности равенства L(A)=L(A’), т.е. проверки эквивалентности распознавателей А и А’, достаточно проверить истинность равенства L(s0)=L(s0’), т.е. проверить эквивалентность начальных состояний распознавателей А и А’. Таким образом, проверка эквивалентности конечных распознавателей сводится к проверки эквивалентности состояний. При выполнении алгоритма проверки эквивалентности состояний различных распознавателей нужно учитывать то, что в дереве проверки не может быть конечных вершин – вершин, содержащих одинаковые состояния.
Пример 1.
Граф конечного распознавателя А.
ц
ц
ц . ц
+
- .
ц
.
Граф конечного детерминированного распознавателя А’.
ц .
.
+ ц ц
. ц ц
- . ц
ц ц . ц
Дерево проверки эквивалентности распознавателей А и А’.
ц + _ .
ц . ц . ц . ц
ц . ц ц
ц
В дереве проверки эквивалентности нет различающих вершин, следовательно эквивалентны начальные состояния проверяемых на эквива-лентность распознавателей А и А’ и эквивалентны распознаватели А и А’.
Пример 2.
Граф конечного распознавателя А.
ц
ц
ц . ц
+
- .
ц
.
Граф конечного распознавателя А’.
ц
ц
ц ц
+ .
- .
ц
.
Дерево проверки эквивалентности распознавателей А и А’.
1
ц + _ .
2
3 4 5
ц .
6 7
В вершине 7 состояние s4 распознавателя А –допускающее, а состояние s3 распознавателя А’ – отвергающее, следовательно распознаватели А и А’ – неэквивалентны, цепочка ц. является различающей, она допускается распознавателем А и отвергается распознавателем А’.