Составители:
Рубрика:
36
Восстанавливая булеву функцию по найденным коэффициентам, получим
две минимальные формы
f(x,y,z)=xz + y+ xz, f(x,y,z)=xz + xy + xz,
ч совпадает с соотношениями (17), полученными по методу Кванта-
Петрика.
Глава 3. Формальные языки и автоматы.
§ 3.1 Основные понятия и определения теории формальных языков.
Синтез систем автоматического проектирования, гибкого
автоматизированного производства, интеллектуальных систем знаний
невозможен без переработки и преобразования дискретной информации, основу
которых составляет теория формальных языков и автоматов. Формальные
языки, широко используемые в современной технике, выступают в качестве
средства “общения” автоматического устройства с окружающими его
объектами. Отвлекаясь от излишней строгости, дадим “рабочее” определение
формального языка, которое позволяет решать ряд прикладных задач и, в
частности, понять основные принципы функционирования дискретных
автоматических устройств.
Под формальным языком
Я будем понимать математический объект,
который включает в себя:
1. Так называемые, состояния языка {S
0
, S
1
, S
2
, ..., S
n
}, причем, S
0
-
предавляет собой начальное, нейтральное состояние.
2. Алфавит языка {m
1
, m
2
, ...,
}, состоящий из некоторого набора символов
(букв); чаще всего в качестве алфавита на практике используют двоичные
символы {1,0}.
3. Правила грамматики, которые задают процесс образования слов языка,
состоящ из символов алфавита.
Эти правила имеют вид соотношений
S
l
::=S
k
m
i
(23)
i=0,, 2, ... , p; l, k=0, 1, 2, . , n.
Равенство (23) означает, что при переходе языка из состояния S
k
, в S
l
является буква образуемого слова m
i
. При этом значению i=0 соответствует
символ m
0
, который не входит в алфавит языка, а представляет собой знак
пробела или, что то же самое, некоторый интервал между словами.
Образование каждого слова в языке начинается из начального состояния S
0
и,
следовательно, им же и заканчивается.
Совокупность состояний языка S
i
принято называть множеством
нетерминальных символов языка M
N
={S
0
, S
1
, S
2
... , S
N
}, а совокупность
символов алфавита m
i
- множеством терминальных символов языка
M
T
={ m
1
, m
2
, ... , m
p
}.
Отметим, что структура определения формального языка очень
напоминает процесс образования слов в разговорной речи, в котором
состоянию S
i
соответствуют те или иные состояния органов речи. При переходе
Страницы
- « первая
- ‹ предыдущая
- …
- 34
- 35
- 36
- 37
- 38
- …
- следующая ›
- последняя »
