Языки и трансляции. Мартыненко Б.К. - 33 стр.

UptoLike

ВУЗ: 

СПбГУ | Санкт-Петербург

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

Рубрика: 

32
Пусть
xR
’
y. Так как отношение R
’
правоинвариантно, то для любого z∈Σ
*
имеет место xzR
’
yz и, таким образом, xz∈L точно тогда, когда yz∈L, т.е. xRy.
Следовательно,
R
’
⊆R, и потому [x]
R
’
⊆ [x]
R
. Это и значит, что любой класс
эквивалентности отношения эквивалентности
R
’
содержится в некотором
классе эквивалентности отношения эквивалентности
R.
Из этого следует, что индекс отношения эквивалентности
R не может быть
больше индекса отношения эквивалентности
R
’
. Индекс отношения эквива-
лентности
R
’
по предположению конечен. Следовательно, индекс отношения
эквивалентности
R тоже конечен.
3)
→ 1). Пусть xRy. Тогда для любых w, z∈Σ
*
цепочка xwz∈L в точности
тогда, когда цепочка
ywz∈ L. Следовательно, xw R yw, и потому R — право-
инвариантно.
Построим конечный автомат
M = (Q, Σ, δ, q
0
, F), где в качестве Q возьмем
конечное множество классов эквивалентности
R, т. е. Q = {[x]
R
| x∈Σ
*
}.
Определим δ([
x]
R
, a) = [xa]
R
. Это определение непротиворечиво, так как R
— правоинвариантно. Положим q
0
= [ε] и F = {[x]
R
| x∈L}.
Очевидно, что конечный автомат
M принимает язык L, поскольку δ(q
0
, x) =
= δ([
ε]
R
, x) = [x]
R
, и, таким образом, x ∈T(M) тогда и только тогда, когда [x]
R
∈F.
Теорема 3.3. Конечный автомат с минимальным числом состояний,
принимающий язык L, единствен с точностью до изоморфизма (т.е.
переименования состояний) и есть fa M из теоремы 3.2.
Доказательство. При доказательстве теоремы 3.2 мы установили, что
любой конечный автомат
M
’
= (Q
’
, Σ
’
, δ
’
, q
0
’, F
’
), принимающий язык L, инду-
цирует отношение эквивалентности
R
’
, индекс которого не меньше индекса
отношения эквивалентности
R, определённого при формулировке высказывания 3
предыдущей теоремы. Поэтому число состояний fa
M
’
больше или равно числу
состояний fa
M, построенного в третьей части доказательства теоремы 3.2.
Если
M
’
fa с минимальным числом состояний, то число его состояний
равно числу состояний fa
M, и между состояниями M
’
и M можно установить
взаимно-однозначное соответствие.
Действительно, пусть
q
’
∈Q
’
. Должна существовать некоторая цепочка x∈
Σ
*
, такая, что δ
’
(q
0
’, x) = q
’
, ибо в противном случае состояние q
’
без какого-
нибудь ущерба для языка, принимаемого этим автоматом, можно было бы
исключить из множества состояний
Q
’
как недостижимое. Отбросив такое
недостижимое состояние, мы получили бы автомат с меньшим числом
состояний, который принимал бы всё тот же язык. Но это противоречило бы
предположению, что
M
’
является
конечным автоматом с минимальным числом
состояний.

Страницы