2015-02-18
784
Определение 9.1.1. Конечное непустое множество называется алфавитом, его элементы называются символами (буквами).
Определение 9.1.2. Конечная последовательность символов алфавита A называется словом в алфавите A.
Пример 9.1.1. Пусть A= { а, б, в }. Тогда баба, ваб, ббб – слова в алфавите A, при этом осмысленность слов не предполагается.
Определение 9.1.3. Слово, не содержащее ни одного символа, называется пустым и обозначается e.
Множество всех слов в алфавите А будем обозначать А*, а через А+ – множество всех непустых слов.
Определение 9.1.4. Число символов в слове w называется длиной слова w и обозначается ÷ w ÷. Длина пустого слова по определению равна нулю.
Определение 9.1.5. Конкатенацией слов x и y называется слово, обозначаемое как xy (или x×y) и получающееся в результате приписывания слова y в конец слова x.
Если w – слово, то через wn (n=1, 2, …) обозначается слово:
(при n=0 полагается, что wn= e), а через ÷ w ÷а – число вхождений буквы а в слово w.
Так как
,
а множество слов данной длины конечно, то множество А* счетно.
|
|
|
Определение 9.1.6. Любое подмножество L множества А* (LÍ А*) называется формальным языком (языком) над алфавитом А.
Определение 9.1.7. Язык А* – L называется дополнением языка L относительно алфавита А.
Так по определению любой формальный язык представляет собой множество, то над языками, заданными над одним и тем же алфавитом, можно обычным образом определить операции объединения, пересечения и разности.
Пример 9.1.1. Пусть над алфавитом А= { a, b } заданы формальные языки L 1={(ab)n: n³0 } Í А* и L 2={ ambm: m³0 } Í А*. Тогда пересечением этих языков будет язык L 1Ç L 2={e, ab } Í А*.
Задача 9.1.1. Пусть над алфавитом А= { a, b } заданы формальные языки L 1={ w Î А*:÷ w ÷=3} Í А* и L 2={ w Î А*:÷ w ÷а = 1} Í А*. Сколько слов содержитязык L 1 – L 2.
Решение. Язык L 1 содержит 8 слов из трех букв: aaa, aab, aba, abb, baa, bab, bba, bbb. Буква а ровно один раз входит в 3 слова: abb, bab, bba. Таким образом, язык L 1 – L 2 содержит 5 слов.
