Дискретная математика: графы и автоматы. Альпин Ю.А - 60 стр.

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

Глава 4
Теория автоматов
§ 1. Буквы, слова, языки, автоматы.
Алфавитом называется любое конечное непустое множество X.
Его элементы называются буквами. Конечные последовательности
букв называются словами. Например,
а) X = {0, 1}, слова — двоичные последовательности 0, 1, 00,
1101, . . . ;
б) X = {а, б, в, . . . , я} — русский алфавит, слово – при нашем
определении – любая последовательность букв;
в) X = {·, −} — алфавит азбуки Морзе.
В примерах мы обычно пользуемся алфавитом, составленным из
первых букв латинского алфавита:
г) X = {a, b}.
Длина |p| слова p равна количеству его букв, причем каждая бук-
ва считается столько раз, сколько она встречается в слове, так что,
например, длина слова 00100 равна 5. Пустое слово обозначаем бук-
вой e. Его длина равна 0. Множество всех слов в алфавите X обозна-
чается через X
∗
.
Если p = x
1
. . . x
k
, q = y
1
. . . y
m
, то то конкатенацией слов p и q
называется слово pq = x
1
. . . x
k
y
1
. . . y
m
. Для пустого слова e и любого
слова p полагаем ep = pe = p. Докажите в виде упражнения
Предложение 1. Конкатенация — ассоциативная операция с
нейтральным элементом (единицей), равным e.
Таким образом, множество X
∗
относительно операции конкатена-
ции образует моноид, то есть, полугруппу с единицей.
Языком над алфавитом X называется любое множество слов
L ⊆ X
∗
. Например,
L
1
= {e, ab, a
2
b
2
};
L
2
= {a
k
b
l
: k, l = 1, 2, . . . }
(используются обозначения p
k
= pp . . . p
| {z }
k раз
, p
0
= e);
L
3
= {a
k
b
k
: k = 1 , 2, . . . };
L
4
= {a
k
2
: k = 1 , 2, . . . }.
                                 Глава 4
                        Теория автоматов


              § 1. Буквы, слова, языки, автоматы.

    Алфавитом называется любое конечное непустое множество X.
Его элементы называются буквами. Конечные последовательности
букв называются словами. Например,
    а) X = {0, 1}, слова — двоичные последовательности 0, 1, 00,
1101, . . . ;
    б) X = {а, б, в, . . . , я} — русский алфавит, слово – при нашем
определении – любая последовательность букв;
    в) X = {·, −} — алфавит азбуки Морзе.
    В примерах мы обычно пользуемся алфавитом, составленным из
первых букв латинского алфавита:
    г) X = {a, b}.
    Длина |p| слова p равна количеству его букв, причем каждая бук-
ва считается столько раз, сколько она встречается в слове, так что,
например, длина слова 00100 равна 5. Пустое слово обозначаем бук-
вой e. Его длина равна 0. Множество всех слов в алфавите X обозна-
чается через X ∗ .
    Если p = x1 . . . xk , q = y1 . . . ym , то то конкатенацией слов p и q
называется слово pq = x1 . . . xk y1 . . . ym . Для пустого слова e и любого
слова p полагаем ep = pe = p. Докажите в виде упражнения
   Предложение 1. Конкатенация — ассоциативная операция с
нейтральным элементом (единицей), равным e.
   Таким образом, множество X ∗ относительно операции конкатена-
ции образует моноид, то есть, полугруппу с единицей.
   Языком над алфавитом X называется любое множество слов
L ⊆ X ∗ . Например,
   L1 = {e, ab, a2 b2 };
   L2 = {ak bl : k, l = 1, 2, . . . }
   (используются обозначения pk = pp . . . p, p0 = e);
                                      | {z }
                                          k раз
            k k
    L3 = {a b : k = 1, 2, . . . };
            2
    L4 = {ak : k = 1, 2, . . . }.

Страницы