Язык, понимаемый устройством

Рассмотрим программу, которую вы составили и ввели в ЭВМ. В каком случае можно считать, что ЭВМ понимает введённую программу?

Во-первых, тогда, когда программа проработала до конца и выдала какой-то результат. Этот результат может не совпадать с тем, который вы хотели получить, но это только означает, что вы написали программу, которая решает другую задачу.

 Во-вторых, если ЭВМ нашла в программе грамматические ошибки и сообщила о них.

В каждом из этих случаев ЭВМ в заключение вышла в одно из штатных состояний. Если рассматривать программу (или другой текст, который вводится в ЭВМ) как слово в некотором алфавите, то можно считать, что это слово является словом языка, который понимает ЭВМ, если в результате обработки этого слова ЭВМ выходит в одно из состояний, определённое как заключительное.

Можно рассматривать как некоторый частный случай язык программирования, например, ПАСКАЛЬ. Тогда заключительным можно определить состояние, соответствующее правильному решению задачи, а описание ЭВМ с программным обеспечением, предназначенным для решения задач на ПАСКАЛе, можно считать одним из способов задания этого формального языка.

Аналогично можно определить язык, понимаемый некоторым конечным автоматом S с начальным состоянием a0. Входной алфавит автомата определен как V, множество состояний как A и задано A*ÌA, которое назовем множеством допустимых заключительных состояний. Слово в алфавите V будем считать словом языка, если оно переводит автомат из состояния a0 в одно из состояний из множества A*. В этом случае автомат можно считать строгим описанием формального языка. Так как выходы автомата нас не интересуют, рассматривают автоматы без выходов, т.е. автомат описывается как S=( V, A, a0, A*, s), где s–функция переходов. Такой язык принято называть автоматным.

Автоматные языки

Установим связь между грамматикой автоматного языка и соответствующим ему автоматом. Терминальными символами языка являются символы входного алфавита языка, т.е. V=Z.

Примем за нетерминальные символы языка имена состояний автомата. Но в этом случае аксиомой языка необходимо назвать те нетерминальные символы, которые сопоставлены заключительным состояниям. Но заключительных состояний может быть несколько, а аксиома в грамматике единственна. Чтобы преодолеть это несогласование, в терминальный словарь вводят ещё один символ (обозначим его g), который называют пустым символом. Все заключительные состояния автомата в графе переходов связывают с одним заключительным дугами, помеченными входным сигналом g, и предполагают, что эти переходы происходят без подачи какого-либо сигнала на вход автомата. Тогда это единственное состояние и определяется как соответствующее аксиоме (или цели) языка.

Пример. Грамматика языка представлена автоматом на рис.5.1.

 

Состояния 6 и 4 заданы как заключительные (отмечены символом звёздочка), состояние 0 – начальное. В состояние 3 автомат приходит тогда, когда слово не является словом языка.

Как видно из графа, слова abb, abab, abaaa¼ab, accb, acccb, bc, bccc будут словами языка; слова, начинающиеся с c, bb, ba, aa, bcb, словами языка не являются.

Правила грамматики этого языка можно определить следующим образом. Вначале для каждого заключительного состояния сопоставим каждой заходящей в него дуге пару <исходящее состояние> <имя переменной>. Так, в состояние 6 из состояния 5 приходит дуга, отмеченная переменной b. Этому будет соответствовать правило

p1: 6 ::=5b
Трём заходящим в вершину 4 дугам будут соответствовать правила

p2: 4::=1c

p3: 4::=5c

p4: 4::=2c

Затем для каждого состояния, кроме начального и тупикового, запишем подобные правила для каждой заходящей в них дуги. Например, для состояния 5 это будут правила

p5: 5::= 1b

p6: 5::= 4c

p6: 5::= 5a

При этом, если дуга исходит из начальной вершины, имя её не указывается, т.е. правило приобретает вид как для вершин 1, 2, 3

p7: 1::= a

p8: 2::= b

p9: 3::= c

Таким образом, приходим к следующему утверждению.

Теорема. В автоматных грамматиках правила всегда имеют вид A::= Bc или A::= c, где строчными символами обозначены терминальные, а прописными – нетерминальные символы.

Пример. Построим автомат, проверяющий правильность расстановки скобок в формулах. Правило имеет вид: при построении формулы в любой момент число закрывающих скобок должно быть не больше числа скобок открывающих, в конце формулы их число должно быть одинаковым. Пусть глубина вложения скобок не больше четырёх. Граф переходов автомата имеет вид
как на рис. 5.2.

                                  Рис.5.2

Обозначим как a любой символ в формуле, кроме скобок. Начальная вершина обозначена как вершина 1, конечная вершина имеет имя к. Символом о обозначена вершина для неправильно построенной формулы (она имеет лишнюю закрывающую скобку). Дуга (5, 0) отмечает, что глубина вложения скобок больше допустимых четырёх. Здесь предполагается, что содержимое скобок может быть пустым. Символьное содержание текста не контролируется.

Этому автомату соответствует следующая грамматика.

Терминальный словарь содержит символы для построения формул, в том числе знаки операций и скобки.

Нетерминальный словарь может быть

N={<формула>, <непол_фор1>, <непол_фор2>, <ошибка>, <непол._фор3>, <непол._фор4>, <символ>, <слово>, }.

Здесь в качестве вспомогательных (нетерминальных) символов определены: <символ> – любой символ терминального словаря, <непол_форi> (i=1,2,3,4) определяет уровень вложенности. Формула просматривается сначала, при открывании очередной скобки уровень увеличивается на единицу, при закрывании – уменьшается на единицу. Уровень вложенности по условию задачи не может быть больше четырёх. Символ <ошибка> определяет, что произошла ошибка: или число закрывающих скобок в формуле оказалось больше числа открывающих или глубина вложенности больше четырёх. 

Целью является символ <слово>, который может быть или правильной формулой или ошибкой.

Правила имеют вид.

p1: <слово>::= <формула>½<ошибка >

p2: <формула>::= < >½<непол_фор1>) ½<формула><символ>

p3: <непол_фор1>::= (½<непол_фор1><символ>½<непол_фор2>)

p4: <непол_фор2>::= <непол_фор1>(½<непол_фор2><символ>½
<непол._фор3>)

p5: <непол._фор3>::= <непол_фор2>(½<непол._фор3><символ>½
<непол._фор4>)

p6: <непол._фор4>::= <непол._фор3>(½<непол._фор4><символ>

p7: <символ>::= a½b½c½d½¼½Z½1½2½¼½0½+½-½(½)½¼

p8: <ошибка> ::= <непол._фор4> (½формула) ½<ошибка> <символ>.

Здесь формулой может быть пустое слово или композиция символов, в которой число открывающих и закрывающих скобок совпадает. При этом внутри формулы нигде число отрывающих скобок не должно быть больше число закрывающих. На каждом уровне от первого до четвёртого, приход следующей открывающей скобки увеличивает на единицу глубину вложенности следующего текста (правила p3-p6). Закрывающая скобка этот уровень уменьшает (правила p2-p5).

К состоянию ошибки приходим (правило 8), если уровень вложенности превысил заданный (первый вариант правила 8) или число закрывающих скобок стало больше открывающих (второй вариант
правила 8). Последующий текст ошибку исправить не может (последний вариант в правиле 8).

 

Упражнения

Задан терминальный алфавит Vт ={a, b, c, d}, нетерминальный алфавит Vн={A,B,C}, аксиомой языка является символ C. Построить описание автомата для следующей грамматики.

Вариант 1.  P={ p1: С::=aB; p2: C::=aA; p3::B=dA; p4: A::=aB; p5: A::= a}. Вариант 2.  P={p1: С::=aB; p2: C::=bA ; p3::B::=bA; p4: A::= cB; p5: A::= a; p6: B::=d}. Вариант 3.  P={p1: С::=aB; p2: C::=bA ; p3: C::=aA; p3::B::=bA; p4: A::= cB; p5: A::= a; p6: B::=d}.

Вариант 4. P={p1: С: ::=aB; p2: C::=cB ; p3: C::=aA; p3::B::=aA; p4: B::= bB; p5: A::= dA; p6: A::=d. p7: B::=b}. Вариант 5.     P={ p1:С::=aB; p2: C::=bB ; p3: B::=aA; p3::B::=aB; p4: B::= bB; p5: A::= dA; p6: A::=d. p7: B::=b h8: A::=a}.

 

 

Библиографический список

1. Карпов Ю.Г. Теория автоматов / Ю.Г. Карпов СПб.: Изд.дом ПИТЕР, 2002.

2. Богомолов А.М. Алгебраические основы теории дискретных систем / А.М. Богомолов, В.Н. Салий.  М.: Наука, 1998.

3. Баранов С.И. Синтез микропрограммных автоматов / С.И. Баранов М.: Энергия, 1985.

4. Поспелов Д.А. Логические методы анализа и синтеза схем / Д.А. Поспелов М.: Энергия, 1974.

5. Мелихов А.Н. Ориентированные графы и конечные автоматы / А.Н. Мелихов М: Наука, 1971.

 

Учебное издание

 

Валерий Петрович Битюцкий,

Игорь Васильевич Хмелевский

 

ПРОЕКТИРОВАНИЕ АВТОМАТОВ

 

 

Редактор  Н.П.Кубыщенко

Компьютерная верстка Битюцкого В.П.

 

 

ИД №06263 от 12.11.2001 г.

Подписано в печать 24.01.2006                     Формат 60х84 1/16

Бумага типографская  Офсетная печать              Усл.печ.л 5,41

Уч.-изд.л. 5,8               Тираж            Заказ                Цена “С”

 

Редакционно-издательский отдел ГОУ ВПО УГТУ-УПИ

620002, Екатеринбург, Мира, 19

ООО «Издательство УМЦ УПИ, 620002, Екатеринбург, Мира, 17

 

 

⇐ Предыдущая78910111213141516

Поделиться: