Конечные распознаватели и регулярные грамматики

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

Получение грамматики из конечного распознавателя

Пусть задан конечный распознаватель. Поставим в соответствие множеству входных символов распознавателя множество терминалов, а множеству состояний – множество нетерминалов. Дадим нетерминалу S_i, соответствующему состоянию s_i такую интерпретацию:

<цепочки, допускаемые состоянием s_i >

Если в распознавателе существует переход из состояния s_i в s_j под действием входного символа x , <цепочки, допускаемые состоянием s_i > могут начинаться символом (терминалом) x , за которым следуют <цепочки, допускаемые состоянием s_j >, т.е. получаем правило: S_i  x S_j .

Если же в распознавателе есть -переход из состояния s_i в s_j , то <цепочки, допускаемые состоянием s_i > представляют собой <цепочки, допускаемые состоянием s_j > , т.е. получаем правило S_i  S_j .

Если в распознавателе состояние s_i допускающее, то <цепочка, допускаемая состоянием s_i > может быть пустой, т.е. получаем правило: S_i   .

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

Алгоритм получения автоматной правосторонней грамматики из конечного распознавателя.

1. Множеством терминалов грамматики сделать множество входных символов распознавателя.

2. Множеством нетерминалов грамматики сделать множество состояний распознавателя, а начальным нетерминалом – его начальное состояние.

3. Если в распознавателе есть переход из состояния s_i в s_j под действием входного символа x , то в грамматику ввести правило: S_i  x S_j .

4. Если в распознавателе есть -переход из состояния s_i в s_j , то в грамматику нужно ввести правило S_i  S_j .

5. Если в распознавателе состояние s_i допускающее, то в грамматику ввести правило: S_i   .

6. Устранить цепные правила.

Если применять алгоритм к детерминированному или недетерминированному конечному распознавателю без -переходов, то п.4 и п.6 не выполняются.

Пример.

Граф конечного распознавателя.

ц

ц

ц . ц

+

- .

ц

.

Автоматная правосторонняя грамматика.

S₀  + S₁ S₁  ц S₂ S₃  ц S₄

S₀  - S₁ S₁  . S₃ S₄  ц S₄

S₀  ц S₂ S₂  ц S₂ S₄  

S₀  . S₃ S₂  . S₄

Нетерминалу S_i, соответствующему состоянию s_i , можно дать другую интерпретацию:

<цепочки, связывающие начальное состояние с состоянием s_i >

Если в распознавателе существует переход в состояние s_j из s_i под действием входного символа x , то <цепочки, связывающие начальное состояние с состоянием s_i > могут представлять собой <цепочки, связывающие начальное состояние с состоянием s_j >, к которым приписан символ (терминал) x , т.е. получаем правило: S_i  S_j x .

Если в распознавателе в состояние s_j существует -переход из s_i , то <цепочки, связывающие начальное состояние с состоянием s_i > представляют собой <цепочки, связывающие начальное состояние с состоянием s_j >, т.е. получаем правило: S_i  S_j .

Если в распознавателе состояние s_i начальное, то <цепочка, связывающая начальное состояние с состоянием s_i > представляет собой пустую цепочку, т.е. получаем правило: S_i   .

Если в распознавателе состояние s_i допускающее, то <цепочки, связывающие начальное состояние с состоянием s_i > представляют собой цепочки, допускаемые распознавателем, поэтому S_i - начальный нетерминал. Если же в распознавателе n>1 допускающих состояний, то каждому допускающему состоянию должен соответствовать свой начальный нетерминал, но так как в грамматике должен быть только один начальный нетерминал, то необходимо ввести новый начальный нетерминал S и n правил вида S  S_i для каждого допускающего состояния s_i .

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

Алгоритм получения автоматной левосторонней грамматики из конечного распознавателя.

1. Множеством терминалов грамматики сделать множество входных символов распознавателя.

2. Множеством нетерминалов грамматики сделать множество состояний распознавателя.

3. Если в распознавателе состояние s_i начальное, то в грамматику ввести правило: S_i   .

4. Если в распознавателе есть переход в состояние s_i из s_j под действием входного символа x , то в грамматику ввести правило: S_i  S_j х.

5. Если в распознавателе есть -переход в состояние s_i из s_j , то в грамматику ввести правило: S_i  S_j .

6. Если в распознавателе n1 допускающих состояний, то ввести новый начальный нетерминал S и n правил вида S  S_i для каждого допускающего состояния s_i .

7. Устранить цепные правила.

Если применять алгоритм к детерминированному или недетерминированному конечному распознавателю без -переходов и с одним допускающим состоянием, то п.5-7 не выполняются и в качестве начального нетерминала нужно принять нетерминал, соответствующий допускающему состоянию.

Пример.

Автоматная левосторонняя грамматика, полученная из распознавателя (см. пример выше).

S₄  S₄ ц S₃  S₀ . S₁  S₀ +

S₄  S₂ . S₂  S₀ ц S₁  S₀ -

S₄  S₃ ц S₂  S₁ ц S₀  

S₃  S₁ . S₂  S₂ ц