Утверждение: Для любого регулярного выражения существует конечный автомат представляющий (распознающий, порождающий) язык, задаваемый этим выражением.
Доказательство: Очевидно, что в соответствии с теоремой 3.3. язык задаваемый регулярным выраже¬нием можно представить регулярной грамматикой. В соответствии с теоремой о регулярной грам¬матике и конечном автомате (2.?) мы знаем, что для каждой регулярной грамматики существует ко¬нечный автомат представляющий ее, следовательно, эта теорема справедлива.
Источники
Для описания произвольного множества строк в некотором алфавите можно использовать графы , ребра, которого помечены знаками этого алфавита. Такие графы называются источниками.
Источником называется ориентированный граф, в котором выделены начальные и заключительные (состояния) вершины, причем начальные помечаются стрелочкой из неоткуда
, а заключительные квадратом . Ребра помечаются знаками некоторого алфавита V, вершины нумеруются. Ребро может быть помечено пустым знаком e.
Пример