Теория формальных языков, грамматик и автоматов. Ишакова Е.Н. - 10 стр.

UptoLike

ВУЗ: 

ОГУ | Оренбург

Составители: 

Рубрика: 

10
Шаг 5. Во множество
Z
′
ДКА
M
′
включить каждое множество, поме-
чающее столбец таблицы переходов
M
′
и содержащее
Z
q
∈
НКА
M
.
Шаг 6. Составить таблицу новых обозначений множеств состояний и оп-
ределить ДКА
M
′
в этих обозначениях.
Пример 2.1. Дана регулярная грамматика ),},,,{},,({
S
P
B
A
S
ba
=
с
правилами baA
A
abB
B
aAaB
S
P
|)3;|)2;|)1: →→→ . Построить по ре-
гулярной грамматике КА и преобразовать полученный автомат к детерминиро-
ванному виду.
Решение задачи включает следующую последовательность действий.
1 Построим по регулярной грамматике КА.
1.1 Пополним грамматику правилами b
N
A
→ и a
N
B
→ , где
N
- новый
нетерминал.
1.2 Начальное состояние конечного автомата
S
H
=
. Множество состоя-
ний автомата },,,{ NBASVQ
N
== , множество символов входного алфавита
},{ baVT
T
== .
1.3 Значения сформированной функции переходов даны в таблице 2.1.
Таблица 2.1 – Функция переходов автомата
M
F
S A B N
a
A, B
A N
∅
b
∅
N B
∅
1.4 Множество заключительных состояний }{
N
Z
=
.
1.5 Для начального символа грамматики ε-правила отсутствуют.
Конечный автомат М - недетерминированный, граф НКА представлен на
рисунке 2.1 слева.
Рисунок 2.1 - Граф НКА (слева) и ДКА (справа) для Р- грамматики
2 Построим по НКА
M
ДКА
M
′
.
2.1 Строим таблицу переходов для ДКА
M
′
(таблица 2.2).
b
a
a
b
a
a
a
b
b
a
b
b
a a
a
b
a
S B
N
A
D
S
CB A
N
E
      Шаг 5. Во множество Z ′ ДКА M ′ включить каждое множество, поме-
чающее столбец таблицы переходов M ′ и содержащее q ∈ Z НКА M .
      Шаг 6. Составить таблицу новых обозначений множеств состояний и оп-
ределить ДКА M ′ в этих обозначениях.
      Пример 2.1. Дана регулярная грамматика G = ({a, b}, {S , A, B}, P, S ) с
правилами P : 1) S → aB | aA; 2) B → bB | a; 3) A → aA | b . Построить по ре-
гулярной грамматике КА и преобразовать полученный автомат к детерминиро-
ванному виду.
      Решение задачи включает следующую последовательность действий.
      1 Построим по регулярной грамматике КА.
      1.1 Пополним грамматику правилами A → bN и B → aN , где N - новый
нетерминал.
      1.2 Начальное состояние конечного автомата H = S . Множество состоя-
ний автомата Q = VN = {S , A, B, N } , множество символов входного алфавита
T = VT = {a, b} .
      1.3 Значения сформированной функции переходов даны в таблице 2.1.
           Таблица 2.1 – Функция переходов автомата M
           F                S            A                   B                   N
           a                A, B         A                   N                   ∅
           b                ∅            N                   B                   ∅

     1.4 Множество заключительных состояний Z = {N } .
     1.5 Для начального символа грамматики ε-правила отсутствуют.
     Конечный автомат М - недетерминированный, граф НКА представлен на
рисунке 2.1 слева.


                                b                            S
                        a                            b                           a
                S           B                                    a
            a                   a                B           C               A
                                                         b
                                             a                   b       a
                A       b   N                                                a
                                                 N
                                                         a   E               D
                    a
                                                                     b
                                                                                 b


     Рисунок 2.1 - Граф НКА (слева) и ДКА (справа) для Р- грамматики

      2 Построим по НКА M ДКА M ′ .
      2.1 Строим таблицу переходов для ДКА M ′ (таблица 2.2).

10

Страницы