Понятие формального языка

Лекция № 9. Иерархия формальных языков и грамматик

1. Понятие формального языка

2. Операции над языками

3. Порождающие грамматики

4. Иерархия языков по Хомскому

Определение 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 – слово, то через wⁿ (n=1, 2, …) обозначается слово:

(при n=0 полагается, что wⁿ=e), а через ÷ w÷_а – число вхождений буквы а в слово w.

Так как

,

а множество слов данной длины конечно, то множество А^* счетно.

Определение 9.1.6. Любое подмножество L множества А^* (LÍ А^*) называется формальным языком (языком) над алфавитом А.

Определение 9.1.7. Язык А^*– L называется дополнением языка L относительно алфавита А.

Так по определению любой формальный язык представляет собой множество, то над языками, заданными над одним и тем же алфавитом, можно обычным образом определить операции объединения, пересечения и разности.

Пример 9.1.1. Пусть над алфавитом А={a, b} заданы формальные языки L₁={(ab)ⁿ: n³0}Í А^* и L₂={a^mb^m: m³0} Í А^*. Тогда пересечением этих языков будет язык L₁ÇL₂={e, ab}Í А^*.

Задача 9.1.1. Пусть над алфавитом А={a, b} заданы формальные языки L₁={wÎ А^*:÷ w÷=3}Í А^* и L₂={wÎ А^*:÷ w÷_а =1} Í А^*. Сколько слов содержитязык L₁ – L₂.

Решение. Язык L₁ содержит 8 слов из трех букв: aaa, aab, aba, abb, baa, bab, bba, bbb. Буква а ровно один раз входит в 3 слова: abb, bab, bba. Таким образом, язык L₁ – L₂ содержит 5 слов_.