Файл: Методические указания к решению задач по дисциплине Теория автоматов и алгоритмические языки.pdf

9
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев кроме того, они имеют представление
x
b


  
и
y
c


  
, где
, ,
A
  


,
,
b c
A

и
( )
( )
A
A
c
b

N
N
, то, в этом случае, слово
y
«старше» слова x .
Упражнение 2.1. Доказать, что в формальном позитивном A -языке A

количество слов длиной
n


равно |
|
n
A
.►
Замечание 2.1. Из результатов упражнения 1.1 следует, что в универсальном A -языке количество слов, длина которых не превышает число
n


, конечно и равно числу
0 1
|
|
|
|
... |
|
n
A
A
A

 
. Поэтому количество слов в универсальном A -языке, которые, согласно лексикографическому A -порядку, «младше» некоторого фиксированного слова, конечно. Кроме того, за этим фиксированным словом непосредственно следует единственное слово, которое «старше» его в лексикографическом A -порядке. Следуя такому лексикографическому «старшинству», за конечное число шагов можно
«добраться» до любого A -слова. Таким образом, согласно лексикографическому A - порядку, все слова формального языка A

можно расположить в натуральном A -словаре
(
)
A
A

Dc
, согласно их «старщинству» (пустое слово – начальное слово этого словаря).►
Пример 2.1. Пусть задан алфавит
,
B
a b

. Тогда начало натурального B -словаря
(
)
B
B


10
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
Теорема 2.1. Для слова
1
m
x
b
b
A

  

, где
1
,...,
m
b
b
A

, его номер
( )
A
A
x

N
в натуральном A -словаре
( )
A
L
Dc
вычисляется согласно формуле:
1 2
1 1
2
( )
( )
( )
(
)
(
)
m
m
A
A
A
A
A
m
m
A
x
b
k
b
k
b
k
b







 
 

N
N
N
N
N
,
(1) где
|
| |
|
A
A
k


.►
Следствие 2.1. Номер
( )
A
A
y

N
непустого слова
y
A


в словаре
(
)
A
A

Dc
вычисляется согласно формуле
( )
( ) 1
A
A
A
A
y
y




N
N
.►
Пример 2.2. Если
,
B
a b

– алфавит из примера 1.1, то, согласно теореме 1.1, номера
( )
B
B
y

N
слова y
bbb
B



равен числу:
3 1 3 2 2
( )
( ) 2
( ) 2
( )
2 2 2 2 2 14
B
B
B
B
B
y
b
b
b








     
N
N
N
N
, что соответствует словарю примера 2.1.►
Замечание 2.2. Если какому-либо символу
x
присваивается значение другого символа
y
, то для этого используется обозначение
:
x
y

, где :

– знак операции присваивания
значения символа, стоящего справа от этого знака, символу, стоящему слева от этого знака. В частности, в этом случае возможно выражение
:
1
x
x
 
, если символу
x
уже присвоено некоторое значение.►
Пример 2.3. Приведѐм алгоритм вычисления слова в натуральном словаре позитивного языка по его номеру в этом словаре.
Пусть
( )
A
A
n
x


N
– номер слова x
A


в натуральном словаре
(
)
A
A

Dc
, вычисленный согласно формуле (1). Тогда для определения этого слова x используется алгоритм, имеющий вид:
(1-ый шаг)
:
y
n

;
(2-ой шаг)
: 1
m

;
(3-ий шаг)
x

;
(4-ый шаг) если
0
y

, перейти к 14-ому шагу;
(5-ый шаг)
:
z
y
k

rest
(остаток от деления числа
y
на число
k
);

11
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
(6-ой шаг) если
0
z

перейти к 10-ому шагу;
(6-ой шаг)
: (
)
y
y
z
k


div
(частное от деления числа
(
)
y
z

на число
k
);
(7-ой шаг)
x
a
x
 
, где
a
A

и
( )
A
a
z

N
;
(8-ой шаг)
:
1
m
m
 
;
(9-ый шаг) перейти к 4-ому шагу;
(10-ый шаг)
: (
)
y
y
k
k


div
;
(11-ый шаг)
k
x
a
x


;
(12-ый шаг)
:
1
m
m
 
;
(13-ый шаг) если
0
z

перейти к 4-ому шагу;
(14-ый шаг) вывод слова
x
A


и завершение алгоритма.►
Пример 2.4. Если
,
B
a b

– алфавит из примера 2.2 и
( ) 14
B
B
y


N
– номер слова
y
B


, то, согласно алгоритму примера 2.3, получаем: y bbb

, что соответствует примеру 1.2.►
Упражнение 2.2. Пусть
,
B

0 1
– алфавит размера
2 , где
0
и
1 – специальные
«жирные» знаки, отличные от натуральных чисел нуля 0 и единицы 1. Для слова формального языка
{
:
}
L
x x
B

 

1
написать формулу вычисления номера этого слова в натуральном словаре
( )
B
L
Dc
, используя номера букв алфавита B , составляющих это слово ( L – язык двоичного представлении натуральных чисел из совокупности
).
Создать алгоритм вычисления слова по его номеру в натуральном словаре
( )
B
L
Dc
.►
Упражнение
2.3.
Для заданного слова формального
A -языка
1
{
:
,
,
}
L
a
x a
A a
a x
A

 



написать формулу вычисления номера этого слова в натуральном словаре
( )
A
L
Dc
, используя номера букв алфавита A , составляющих это слово ( L – язык
k
-ичного представлении натуральных чисел из совокупности
). Затем, создать алгоритм вычисления слова по его номеру в натуральном словаре
( )
A
L
Dc
.►

12
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
Упражнение 2.4. Пусть в алфавите
A
заданы два непустых слов x и y , имеющие номера
m и n , соответственно, в натуральном словаре
(
)
A
A

Dc
. Используя длины
| |
x
и
| |
y этих слов, найти номер слова x
y

в натуральном словаре
(
)
A
A

Dc
.►
Упражнение 2.5. Пусть
, , /
B

– алфавит для языка рациональных дробей
/
{ / :
,
}
m n m
n



, где
( )




и



. Для заданной неотрицательной (отрицательной) рациональной дроби
/
/
x
m n


вычислить еѐ номер
/
( )
B
x
N
в натуральном словаре
/
(
)
B
Dc
.►
Определение 2.1. Два натуральных числа
m
и
n
, одно из которых ненулевое, называются
взаимно простыми, если их наибольший общий делитель
( , ) 1
m n

НОД
. Ненулевое натуральное число называется простым, если оно не является единицей и делится нацело только на себя само и единицу.►
Пример 2.5. Алгоритм Евклида для вычисления наибольшего общего делителя
( , )
k n
НОД
двух натуральных чисел
k
и
n
, одно из которых ненулевое, имеет следующий последовательно пошаговый вид:
(1-ый шаг)
1
:
( , )
x
k n

min
(вычисление минимального из двух чисел);
(2-ой шаг)
2
:
( , )
x
k n

max
(вычисление максимального из двух чисел);
(3-ий шаг)
3
:
( , )
x
k n

min
;
(4-ый шаг) если
1 0
x

, то переходим к 9-ому шагу;
(5-ый шаг)
1 2
3 3
:
(
,
)
min
x
x
x x


;
(6-ой шаг)
2 2
3 3
:
(
,
)
max
x
x
x x


;
(7-ой шаг)
3 1
:
x
x

;
(8-ой шаг) переход к 4-ому шагу;
(9-ый шаг) вывод "
( , ) "
k n

НОД
2
x и завершение алгоритма.►
Упражнение 2.6. Используя алгоритм Евклида найти
(90,36)
НОД
.►
Замечание 2.3.

13
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
а) Согласно результату упражнения 2.5, язык рациональных дробей допускает построение его в виде словаря
/
(
)
B
Dc
. Однако, этот словарь не является словарѐм рациональных чисел, поскольку каждое рациональное число представляется бесконечным словарѐм рациональных дробей, в частности, словарь дробей 0 / :
n n

определяет одно рациональное число («нулевое»). Для того чтобы избежать такой неоднозначности в представлении рациональных чисел, в качестве единственного представителя рационального числа следует выбирать только несократимые рациональные дроби. В этом случае совокупность рациональных чисел представима в виде совокупности
/
{ /
:
( , ) 1
}
m n
m n



НОД
, где каждое рациональное число представлено единственной несократимой дробью. Алгоритм Евклида, приведѐнный в примере 2.5, позволяет выделить из натурального словаря
/
(
)
B
Dc
натуральный словарь
( )
B
Dc
рациональных чисел. При таком выделении необходимо при развѐртывании словаря
/
(
)
B
Dc
в словарь
( )
B
Dc
отбирать только несократимые рациональные дроби. Таким образом, для языка рациональных чисел возможно построение его словаря.
б) В математике рациональноѐ число
/1
m

отождествляется с целым числом
m

. В частности, при таком отождествлении 0 /1 0
 
. Таким образом, справедливо высказывание

.►
Для непустого формального A -языка L
A


могут создаваться словари, не обязательно являющиеся натуральными. В этом случае для такого словаря, как правило, может использоваться обозначение
( )
L
Dc
или
( )
n
L
Dc
, где n

. Кроме того, для номера слова x L

в таком словаре будет использоваться символ
( )
( )
L
x
Dc
N
Пусть ,
k m

,
1
,...,
k
U
u
u

и
1
,...,
m
V
v
v

– два словаря формальных языков.
Введѐм два словаря
1
( )
L
Dc
и
2
( )
L
Dc
для формального языка
{
:
,
}
L U V
u
v u U v V
  


прямого произведения языков U и V . Для этого каждому слову
i
j
x
u
v
L


, где
1,...,
i
k

и
1,...,
j
m

, в словаре
1
( )
L
Dc
присвоим одномерный номер
1
( )
( )
(
1)
L
x
i
m
j
   
Dc
N
(2).
В словаре
2
( )
L
Dc
этому слову x
L

присвоим одномерный номер
2
( )
( )
(
1)
L
x
j
m i
   
Dc
N
(3).

14
Элементы теории автоматов и формальных языков В.А. Кутыркин, А.Ю. Бушуев
Если для слова
i
j
x
u
v
L


ввести символ
i
j
c , то вместо словарей
1
( )
L
Dc
и
2
( )
L
Dc
для перечисления без повторов слов языка L можно использовать представление языка L в виде матрицы
C
из
k
строк и m столбцов:
1 1
1 1
(
)
m
i k
m
j
k
k
m
c
c
C
c
c
c












,
(4) где для так называемых немых индексов i и j указаны их пробеги (
1,...,
i
k

и
1,...,
j
m

) и ( , )
i j – двумерный номер слова
i
j
x
u
v
L


, согласно матрице
C
. В этом случае формула (2) отражает перечисление одномерных номеров компонент матрицы (4) по строкам, когда после последней компоненты строки матрицы счѐт продолжается с начальной компоненты следующей строки, если таковая имеется. Формула (3) отражает аналогичный счѐт одномерных номеров компонент матрицы (4) по столбцам.
Формула (2) может использоваться и в том случае, когда, как и ранее, словарь
1
,...,
k
U
u
u

конечен, но словарь
:
j
V
v
j


бесконечен. Аналогично, формула (3) может использоваться, когда словарь
:
i
U
u i


бесконечен, но словарь
1
,...,
m
V
v
v

конечен.
Упражнение 2.7. Пусть задан номер
1
( )
(
)
L
n
u
v

Dc
N
(
2
( )
(
)
L
n
u
v

Dc
N
) неизвестного слова
u
v
L

в словаре
1
( )
L
Dc
(
2
( )
L
Dc
) формального языка
L
U V
 
Предполагается, что этот номер вычислен согласно формуле (2) ((3)). Также предполагается, что словари
1
,...,
k
U
u
u

и
:
j
V
v
j


(
:
i
U
u i


и
1
,...,
m
V
v
v

) заданы. Требуется написать алгоритм для вычисления номеров слов u и v в словарях
U
и
V
, соответственно.►
Пусть
:
n
X
x
n


– словарь для непустого формального языка X
A


Рассмотрим формальный язык
2
: ,
i
j
L
X
X
X
x
x
i j

 



. Если для ,i j

вести обозначения
i
i
j
j
x
x
c

, то для перечисления без повторов слов языка L можно использовать представление языка L в виде матрицы
C
из бесконечного числа строк и столбцов: