ВУЗ:
Составители:
Рубрика:
66
12. РАЗРЕШИМЫЕ И НЕРАЗРЕШИМЫЕ ПРОБЛЕМЫ
Рассмотрим систему подстановок, задаваемую алфавитом M = {m
i
/ i =
= 1, 2, ..., p} и базисными подстановками
α
i
→ β
i
,
где α
i
, β
i
– формулы (слова), быть может пустые, в алфавите M.
Элементы некоторого конечного множества отношений между фор-
мулами называются правилами вывода.
Каждую подстановку будем понимать как правило вывода. Часто
систему подстановок называют полусистемами Туэ, по имени норвеж-
ского математика Акселя Туэ (1863 − 1922). Используя эти полусистемы,
американский лингвист Ноам Хомский (р. 1928) сформулировал и развил
аппарат формальных грамматик.
Определим понятие формальной грамматики, которую в дальней-
шем будем называть просто грамматикой. Рассмотрим конечный алфа-
вит M = {m
1
, m
2
, ..., m
n
}, элементы которого будем называть символами
(буквами), а конечные последовательности символов – словами.
Обозначим всё множество слов, на длину которых не наложены ни-
какие ограничения, через Я
0
. Если множество слов Я ⊂ Я
0
, то будем гово-
рить, что Я – это язык в алфавите M.
а)
2
1
3
4
5
6
б)
2
1
3
4
5
6
в)
2
1
3
4
5
6
г)
2
1
3
4
5
6
Страницы
- « первая
- ‹ предыдущая
- …
- 64
- 65
- 66
- 67
- 68
- …
- следующая ›
- последняя »
