41.Деревья разбора. Определения. Свойства. Примеры.

Дерево разбора – это дерево, показывающее сущность порождения. Внутрение узлы отмечены переменными, листья – терминалами или ε. Для каждого внутренего узла должна существовать продукция , голова которой является отметкой узла, а отметки сыновей узла, прочитанные слева направо, образуют её тело.

Терминальная цепочка принадлежит языку граматики т. И т.т, когда она является кроной, по крайней мере одного дерева разбора. таким образом существование левых и правых порождений и деревьев разбора является равносильным условием того, что все они определяют в точности цепочки языка КС- граматики. Для некоторых граматик можно найти терминальную цепочку с несколькими деревьями разбора, или (что равносильно) с несколькими левыми или правыми порождениями. Такая граматика называется неоднозначной.

Свойства:

Любой узел дерева отмечен переменными из множества …. 2) любой лист дерева отмечен… либо терминалом, либо пустым символом

Пример P*=>0||0

P

0 p 0

|

1 P 1

|

Σ

E*=>Q* (Q+b00)

E

|

E * E

| |

(..E )

|

E + E

| |

I I

|

a I 0

I 0

|

b

Особый интерес представляют деревья со следущими св-ми

1. крона которых является терминальной цепью

2. крона деревьев отмечены стартовым символом

42.Связь ксг с конечными автоматами. Нормальная форма Хомского.

По любой заданой КСГ можно наблюдать одну КСГ которая порождает тот же язык что и исходная за искл. Цепочки эпсилон, и при этом новая граматика находиться в нормальной форме Хомского т.е не содержит бесполезных символов и тела каждой продукчии состоит либо из 2–х переменных либо из одного терминала

1. удалить бесполезные символы

переменнные можно удалить из граматики если она не порождает не одной терминальной цепочки, или не встречает в чепочках выводимых из стартового символа

2) удаляются цепные и и эпсилон продукции

43. Принцип микропрограммного управления. Теорема Глушкова. Понятия операционного и управляющих автоматов.

Функциональная и структурная организация выч. Устройств

1. любая операция релизуемая устройством, которая расссматривает как элементарные действия операций. Передача информации из одного устройства в другое

2. для управления используются логические условия зависисмости от результата, могут принимать значения либо истины (1) либо лжи(0)

3. процес выполнения операций в устройстве описывается в форме алгоритма который представляется в терминах микроопераций и логических условий и называется микропрограммой. Она определяет порядок следования операций и необходима для получения результата

4. используется как форма представления функций устройства на основе которой определяется порядок функционирования устройства во врепени

академиком глушковым было показано что в любом устройстве обработки информации, операционный автомат это:

хранение слов информации

выполнение микроопераций

выпонение логических условий

Значение логических условий в операционном автомате задаются множеством осведомительных сигналов.

Управляющий автомат генерирует последовательность управляющих сигналов предписаную микропрограммой и соответственым значение логических условий

Операционый автомат задается 5 множествами

1. мн-во вх слов Д

2. мн-во выходных слов R

3. мн-во внутрених слов S

4. мн-во микроопераций У (преобразование вхю слов в выходные)

5. лог. Условие х