Эквивалентные преобразования
Утверждение 7 (Эквивалентные регулярные выражения) Следующие регулярные выражения являются эквивалентными:
Доказательство этого утверждения хорошо известно из теории регулярных грамматик. Заметим, что перечисленные пары регулярных выражений далеко не исчерпывают полный список эквивалентных регулярных выражений.
Утверждение 8 (Эквивалентные преобразования структурных схем) Пусть S=( T,E,A,p,a,r) - структурная схема. Тогда любая схема, получаемая из данной путем замены регулярного выражения на эквивалентное приводит к схеме S'=( T,E,A,p',a,r) эквивалентной исходной схеме.
