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

1) возможного знака;

2) последовательности из нуля или более цифр;

3) десятичной точки;

4) последовательности из одной или более цифр;

5) возможной экспонентной части, содержащей

а) экспоненту (10),

б) возможный знак,

в) последовательность из одной или более цифр.

Регулярные выражения, конечно, эквивалентны грамматикам типа 3 (см. разд. 2.2). Например, грамматика типа 3, соответствующая регулярному выражению для вышеприведенного вещественного числа, имеет порождающие правила:

P->dF d

F->dF 10A d

N->dN d

где R - начальный символ.

Существует полное соответствие между регулярными выражениями (а поэтому и грамматиками типа 3) и конечными автоматами, которые определяются следующим образом.

Конечный автомат - это устройство для распознавания строк какого-либо языка. У него есть конечное множество состояний, отдельные из которых называются последними. По мере считывания каждой литеры строки контроль передается от состояния к состоянию в соответствии с заданным множеством переходов. Если после считывания последней литеры строки автомат будет находиться в одном из последних состояний, о строке говорят, что она принадлежит языку, принимаемому автоматом. В ином случае строка не принадлежит языку, принимаемому автоматом.

Формально конечный автомат определяется пятью характеристиками:

1) конечным множеством состояний К;

2) конечным входным алфавитом Z;

3) множеством переходов 5;

4) начальным состоянием S(SeK);

5) множеством последних состояний F(FK). Конечный автомат можно записать в виде пятерки

M = (A,Z, 5,S,F).

Рассмотрим следующий пример, где состояниями являются А и В, входным алфавитом - {0,1}, начальным состоянием - А, множеством последних состояний - {А}, а переходами

§ (A,0)=A, §(A,1)=В, §(В,0)=В, §(В,1)=A.

Эти переходы означают, что «при чтении 0 в состоянии А управление передается в состояние А» и т. д. При чтении строки

01001011

управление последовательно передается в следующем порядке через со стояния

A, А, В, В, В, А, А, В, А. Так как А есть последнее состояние, строка принимается конечным автоматом. Однако при чтении строки

00111

автомат проходит через состояния

А, А, А, В, А, В

в таком порядке, и поскольку В не является последним состоянием, эта строка не принимается, т. е. она не принадлежит языку, принимаемому этим автоматом. В связи с тем что нули не влияют на состояние автомата, а каждая единица изменяет его состояние с A на В и с В на A,и начальное состояние является тем же, что и последнее состояние, язык, принимаемый автоматом, состоитиз тех строк, которые содержат четное число единиц.

Переходы можно представить также с помощью таблицы (табл. 3.1) и схематически (рис. 3.1).

Таблица 3.1 Состояния A B

A B B A

Рис. 3.1

Такой автомат называют детерминированным, потому что в каждом элементе таблицы переходов содержится одно состояние. В недетерминированном конечном автомате это положение не выдерживается. Рассмотрим конечный автомат, определенный следующим образом:

M1=(K1,Z1,51,S1,F1),

где K1={A,B}, 1={0,/}, S1={A}, F1={B}, а переходы представлены в табл. 3.2 или схематически на рис. 3.2. М, принимает строку тогда и только тогда, когда она начинается с единицы. Эта же строка не может быть принята, так как при чтении 0 не осуществляется переход с А.

Таблица 3.2

A B

0 {B}

{A,B} {B}

Рис. 3.2

Строка 1 будет принята: здесь есть переход (в более общем случае последовательность переходов), ведущий к последнему состоянию при чтении строки. Имеется также переход к не последнему состоянию (от А к А), но это не влияет на приемлемость строки. Поэтому прежде чем прийти к выводу о том, что строка не может быть принята недетерминированным конечным автоматом, необходимо перепробовать все возможные последовательности переходов. С этой целью следует перебрать все возможности одну за другой или параллельно. Если в данный момент времени можно проходить только по одному пути (как обычно и бывает), то требуется возвратиться назад, т. е. необходимо перечитать всю строку или ее часть в процессе опробования другого пути. Очевидно, что эта процедура может оказаться весьма длительной. Существует детерминированный конечный автомат М2, соответствующий автомату М1, который принимает тот же язык,

M2=(K2,Z2,52,S2,F2)

где K2 = {A,B,C}, Z2={0, /}, S2 = {A},F2={B}, а переходы даны в табл. 3.3 и схематически на рис. 3.3.