Пред.
След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике ДЛЯ СТУДЕНТОВ И ШКОЛЬНИКОВ ЕСТЬ
ZADANIA.TO
9.5. Выбор типа языка5.1.1. В соответствии с обсуждениями разд. 9.2 и сделанными выше оговорками в качестве языка, которым будет пользоваться наш говорящий/слушающий, мы примем язык конечных состояний. Языки этого типа хорошо известны, поэтому их описание будет кратким. 5.1.2. Грамматика Словарь нетерминальных символов состоит из синтаксических переменных, или состояний. Они будут обозначаться числами 5.1.3. Продукции (правила) в
Продукцию (9.5.1) следует читать как «состояние 5.1.4. Как и в гл. 8 второго тома, мы будем предполагать, что грамматика сведена к детерминированной форме, так что любые две продукции в
должны совпадать, т.е.
В (9.5.3) мы разложили предложение на последовательные продукции 5.1.5. Множество Пользуясь той же процедурой построения цепочек, но не требуя, чтобы
Они не обязательно принадлежат языку, но могут иметь то или иное лингвистическое значение. 5.2. Эквивалентно язык может быть представлен конечным автоматом, который мы будем часто изображать в виде диаграммы. Чтобы уточнить обозначения, рассмотрим конечный автомат, диаграмма конструкции которого представлена на рис. 9.5.1. Словари соответствующей грамматики - это
а продукции перечислены в табл. 9.5.1. Грамматика, очевидно, является детерминированной. Она порождает, например, предложения, которые можно представить следующим образом:
или фразы вида
5.3. Еще один эквивалентный способ представления языков конечных состояний (или автоматных языков) это через регулярные выражения формальной логики. Такие выражения строятся при помощи конкатенации, конечного повторения (обозначаемого звездочкой), объединения и скобок, указывающих порядок «выполнения». Язык, порождаемый диаграммой автомата на рис. 9.5.1, можно, например, представить в следующем виде:
Очевидно, что
Рис. 9.5.1 Таблица 9.5.1 (см. скан) 5.4.1. Для последующего крайне важно то обстоятельство, что языки конечных состояний, так же как и многие другие формальные языки, можно рассматривать как регулярные комбинаторные структуры (см. Тогда образующие будут представлены продукциями из В этом случае правило идентификации будет отождествлять две регулярные конфигурации (правильно построенные фразы), если они состоят из одной и той же цепочки терминальных символов и имеют одинаковые показатели внешних входных связей и внешних выходных связей. Вспомним, что конечный автомат здесь предполагается детерминированным, поэтому каждое изображение состоит из единственной конфигурации. 5.4.2. Строго говоря, такая алгебра изображений представляет не только
|
1 |
Оглавление
|