Регулярное выражение конечного автомата

1.

2.

Заявление —
Пусть P и Q два регулярных выражения.
Если P не содержит нулевую строку,
то R = Q + RP имеет единственное решение:
R = QP *

3.

R = Q + (Q + RP) P [После помещения значения R = Q + RP]
= Q + QP + RPP
Когда мы снова и снова ставим значение R рекурсивно,
мы получаем следующее уравнение:
R = Q + QP + QP 2 + QP 3 … ..
R = Q (ε + P + P 2 + P 3 +….)
R = QP * [Как P * представляет (ε + P + P2 + P3 +….)]

4.

1.
Диаграмма переходов не должна иметь переходов
NULL
2.
Должно быть только одно начальное состояние

5.

Шаг 1 — Создайте уравнения в виде следующей формы для всех
состояний DFA, имеющих n состояний с начальным состоянием q 1 .
q 1 = q 1 R 11 + q 2 R 21 +… + q n R n1 + ε
q 2 = q 1 R 12 + q 2 R 22 +… + q n R n2
qi
…………………………
…………………………
…………………………
…………………………
q n = q 1 R 1n + q 2 R 2n +… + q n R nn
R ij представляет множество меток ребер от q i до q j , если такого
ребра не существует, то R ij = ∅
Шаг 2 — Решите эти уравнения, чтобы получить уравнение для
конечного состояния в терминах R ij
qj

6.

ПОСТРОИТЬ РЕГУЛЯРНОЕ ВЫРАЖЕНИЕ,
СООТВЕТСТВУЮЩЕЕ АВТОМАТАМ, ПРИВЕДЕННЫМ НИЖЕ
—
Здесь начальное состояние и конечное состояние q 1 .
Уравнения для трех состояний
q1, q2 и q3 следующие:
q1=q1a+q3a+ε
(перемещение ε происходит
потому, что q1 является
начальным состоянием )
q2=q1b+q2b+q3b
q3=q2a

7.

1
q1=q1a+q3a+ε
q2=q1b+q2b+q3b
q3=q2a
q2=q1b+q2b+q3b
= q 1 b + q 2 b + (q 2 a) b (подставляя
значение q 3 )
= q 1 b + q 2 (b + ab)
= q 1 b (b + ab) * (применение теоремы
Ардена)
2
q1=q1a+q3a+ε
= q 1 a + q 2 aa + ε (Подставляя значение q 3 )
= q 1 a + q 1 b (b + ab *) aa +ε
(Подставляя значение q 2 )
= q 1 (a + b (b + ab) * aa) + ε
= ε (a + b (b + ab) * aa) *
= (a + b (b + ab) * aa) *

8.

ПОСТРОИТЬ РЕГУЛЯРНОЕ ВЫРАЖЕНИЕ,
СООТВЕТСТВУЮЩЕЕ АВТОМАТАМ, ПРИВЕДЕННЫМ НИЖЕ
Начальное состояние q 1,
конечное состояние q 2.
Запишем уравнения —
q1=q10+ε
q2=q11+q20
q3=q21+q30+q31
2
q 1 = ε0 * [As, εR = R]
Итак, q 1 = 0 *
q2=0*1+q20
Итак, q 2 = 0 * 1 (0) * [по теореме
Ардена]
Следовательно, регулярное
выражение 0 * 10 *.

9.