Составители:
43
Пример 3.5: Числа языка Паскаль. Пусть D = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}.
Тогда любое число языка Паскаль можно представить в виде следующего
регулярного выражения:
D
+
({.}D
+
∪ {ε}) ({e}({+, –} ∪ {ε}) D
+
∪ {ε}).
Здесь использован символ плюс Клини (
+
), определяемый следующими
равенствами:
Напомним, что звёздочка Клини (
*
), обозначающая замыкание, опреде-
ляется следующим равенством:
Члены {ε} обеспечивают необязательность дробной части и порядка
(минимальная цепочка, представляющая число на языке Паскаль, состоит из
одной цифры).
§ 3.6. Алгоритмически разрешимые проблемы,
касающиеся конечных автоматов
В этом параграфе мы покажем, что существуют алгоритмы, отвечающие на
многие вопросы, касающиеся конечных автоматов и языков типа 3.
Теорема 3.12. Множество цепочек, принимаемых конечным автоматом с
n состояниями,
1) не пусто тогда и только тогда, когда он принимает цепочку длиной,
меньше n;
2) бесконечно тогда и только тогда, когда он принимает цепочку длиной l,
n ≤ l <2n.
Доказательство.
Необходимость условия 1) вытекает из следующих рассуждений от
противного. Предположим, что множество T(M) ≠∅, но ни одной цепочки
длиной меньше n в этом множестве не существует.
Пусть x∈T(M), где M =(Q, Σ, δ, q
0
, F) — конечный автомат с n состо-
яниями, и | x|≥n. Пусть x — одна из самых коротких таких цепочек. Очевидно,
что существует такое состояние q∈Q, что x = x
1
x
2
x
3
, где x
2
≠ε, и δ(q
0
, x
1
) = q,
δ(q, x
2
) = q, δ(q, x
3
)∈ F. Но тогда x
1
x
3
∈T(M), поскольку δ(q
0
, x
1
x
3
) = δ(q
0
, x
1
x
2
x
3
)∈
F. В то же время |x
1
x
3
| < |x
1
x
2
x
3
| = | x|, но это противоречит предположению, что
x — одна из самых коротких цепочек, принимаемых fa M.
Достаточность условия 1) очевидна. Действительно, если конечный
автомат принимает цепочку с меньшей длиной, чем n, то множество T(M) уже
не пусто (какой бы длины цепочка ни была).
Докажем теперь утверждение 2).
Необходимость условия 2) доказывается способом от противного. Пусть fa
M принимает бесконечное множество цепочек, и ни одна из них не имеет
длину l, n ≤ l < 2n.
*
*
1
.
k
k
A
AA AA A
∞
+
=
===
∪
*
0
.
k
k
A
A
∞
=
=
∪
Страницы
- « первая
- ‹ предыдущая
- …
- 42
- 43
- 44
- 45
- 46
- …
- следующая ›
- последняя »
