Дискретная математика. Кулаков Ю.В - 47 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

13 Укажите множества гомеоморфных графов из предложенных графов:
14 Оцените толщину графа:
15 Выделите все запрещенные фигуры в графе и найдите все ребра графа, удаление любого из ко-
торых преобразует его в планарный граф:
10 РАЗРЕШИМЫЕ И НЕРАЗРЕШИМЫЕ ПРОБЛЕМЫ
Рассмотрим систему подстановок, задаваемую алфавитом M = {m
i
/ i = = 1, 2,
... , p} и базисными подстановками
α
i
→ β
i
,
где α
i
, β
i
– формулы (слова), быть может пустые, в алфавите M.
Элементы некоторого конечного множества отношений между формулами
называются правилами вывода.
Каждую подстановку будем понимать как правило вывода. Часто систему
подстановок называют полусистемами Туэ, в честь норвежского математика Акселя Туэ. Используя эти
полусистемы, Хомский сформулировал и развил аппарат формальных грамматик.
Определим понятие формальной грамматики, которую в дальнейшем будем
называть просто грамматикой. Рассмотрим конечный алфавит
M = {m
1
, m
2
, ..., m
n
}, элементы которого будем называть символами (буквами), а конечные последова-
тельности символов – словами.
Обозначим все множество слов, на длину которых не наложены никакие ог-
раничения, Я
0
. Будем говорить, что Я ⊂ Я
0
– язык в алфавите M.
а)
б)
в)
ж)
з)
и)
а)
б)
в)
а)
1
2
3
4 5 6
7
б)
1
2
3
4 5 6
7
; ; ;
; ; ;
г)
д)
е)
; ; .
;
;
.
; .

Страницы