18.02.2003 №1 - Лекции по теории автоматов

Лекции по теории автоматов
скачать (26.7 kb.)

Доступные файлы (1):

Лекции.doc

104kb.

25.05.2003 02:32

скачать

содержание

Лекции.doc

18.02.2003 №1

Введение.

Теор-я ав-в(Т/А) заним-ся изучением абстрактных выч.уст-в или машин. В 30е гг ХХвека Тьюринг исследовал абстрактную машину, кот.по крацней мере в обл-ти выч-й обладала всеми возможностями совр.выч.машин. Целью исследования Тьюринга было определить границу м/у что м/т делать выч.маш-а и что не м/т. Пол-ые им рез-ты явл-ся фундаментальными и лежат в основе построения совр.прог.обеспечения и совр.комп-в.

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

В к.50гг ХХвека лингвист Хомский занялся изучением формальных грамматик. Не явл-сь машинными в точном смысле этого слова, гр-ки тесно связанны с абстрактными авт-ми и служат основой для построения ПО и в частности компиляторов.

В 1969г мат-к Кук развил рез-ты Тьюринга о выч-ти и о невыч-ти. Ему удалось разбить все задачи на те кот-е м.б. эффективно решенымаш-ой и на те, кот-е впринципе м.б.решены, но для своего решения требуют так много Маш-го времени, что компил-р оказывается бесполезным для решения всех экземпляров задач, за исключением небольших. Послед-е задачи наз-ся трудно-разрешимыми или NP-трудными. Даже при экспотенциальном росте быстродействие ЭВМ весьма вероятно, что задачи этого типа м.б.решены.

Все эти соображения получены в середине прошлого века актуальны и сегодня. Напр-р, конечные ав-ты и некоторые типы формальных гр-к эфф-но исп-ся и сегодня при разработке компонентов П.О. Модель Тьюринга помогает оценить принципиальные возможности П.О. Теория слож-ти вычислений позволяет ответить на вопрос : можем ли мы решить задачу влоб, составив прог-му, или н/о искать обходные пути,. Иногда отказываться от точного решения задачи, т/о для того чтобы решить ее с заданной точностью за приемлемое время.

В силу сказанного Т.А. и теория сложности выч-й явл-ся ядром инф-ки, в частности рез-ты этих теорий исп-ся при:

1) создании ПО, используемого для создания и проверки цифровых схем

2) В лексич-х анализ-рах стандар-го компилятора, т.е.в той части коп-ра, кот.отвечает за разбивку исходного текста на такие логические единицы как идентификаторы, ключевые слова, знаки пунктуации и т.д.

3) В ПО для сканирования таких больших текстовых массивов, как наборы Webстраниц, при поиске слов, фраз и др-х последовательностей символов.

4) В ПО для проверки различного рода симс-м, таких как протоколы связи или протоколы защищенного обмена инф-ей, кот-е м/т нах-ся в конечном числе различных состояний.

^ Конечный авт-т.

Сущ-т мн-во разл.сис-м и компонентов, кот-е м/о рассм-ть как наход-ся в каж.момент времени в определ-ом состоянии из заданного мн-ва состояний. Назначением каж-го состояния явл-ся запоминание опред-го момента истории сис-мы. Т.к.число состояний сис-мы конечно, а история м/т длиться достаточно долго, то заполнить всю историю невозможно и => сис-у н/о стороить так, чтобы запоминать т/о действ-но важную инф-ию и забывать несущ-ную. Необх-ть иметь конечное число состояний обусловлена тем, что сис-ма долна быть реализована либо виде прог-мы, либо виде схемы.

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

начало

нажатие

Состояния ав-та обозначены кружками а дуги, указывающие

нажатие

направления переходов помечены входными символами,

воздействующими на сис-у(нажатие). Одно из состояний явл-ся начальным, _ч что помечается входной стрелкой, в нашем сл-е это состояние выкл-но.

Часто выделяют одно или неск-ко заключительных или допускающих состояний., попав в одно из них из начального состояния, после совершения неск-ких переходов мы можем считать что в некотором смысле входная посл-ть была хорошей. Напр-р, для нашего авт-та состояние вкл-но м/о считать допускающим, т.к. попав в него вкл-ет какую-то дальнейшую сис-у и она будет работать. В дальнейшем допускающие состояния буд. Обозначать двойными кружками или прямлугольником.

Расс-м др.пр-р, кот.м.б.частью лексического анализ-ра. Пусть ав-т обнаруживает слово them.

t

h

e

m

начало
Это ав-т должен иметь 5разл.состояний,

каж-е из кот-х предс-т собой позицию

в слове them, эти позиции соответствуют

префиксам этого слова от пустой цепрочки (никакая позиция в слове еще не достигнута) до целого слова. Каж-е из 5 сост-й авт-ой модели обозначена частью слова, прочитанного на данном шаге. Входным сигналам этого ав-та соотв-ют буквы. М/о считать, что данный лексический анал-тор на каж-м шаге просматривает по одному символукомпилируемой программы. Состояние, обозначенное символом Them достигается, когда введено все это слово, т.к.задачей данного ав-та явл-ся распознование именно слова them, то последнее состояние явл-ся единственным допускающим состоянием.

Т.о., дисциплина ТА явл-ся той теорит-ой базлй, кот-я лежит в основепостроения дискретных уст-в любой слож-ти и любого назначения, а также проектирования ПО, в частности компиляторов, распознователей и т.д.

^ ФОРМАЛЬНЫЕ ЯЗЫКИ.

Понятие о языках. Синтаксический разбор.

Разв-е теории и ср-в искус.интелекта позволяет надеяться на то, что взаимод-е чел-ка и ком-ра в недалеком будущем буд/т осуществляться на языке, близком к естественному.

Но в наст.время, прог-ты в основном описывают задачи на формальных языках, на языках высокого уровня и иногда на ассемблере. Прог-мы, написанные на алгоритмических языках становятся доступными ком-ру, т/о после их трансляции, т.е.преобразования команд выс.ур/ня в машинные инструкции. Теория построения трансляторов базируется на теории формальнх языков, особенно в части синтакс. и семантического разбора. (семантика – смысл, синтаксис – грамматика).

До н.ХХвека под языком понимали т/о естес.язык и наука о языках(лингвистика) сводилась к изучению конкретных языков. Разв-е мат-ки, кот-я представляет особый мат.язык, логические и философские исслед-я языков, наблюдения за сред-ми коммуникации у животных, раз-е кибернетики сущес-но расширили представления о языках, под кот-ми в наст.время понимабт всякое ср-во общения состоящие из:

1)знаковой сис-мы,т.е.мн-ва допустимых послед-тей знаков

2)мн-во смыслов этой сис-мы

3)Соответствия м/у последлват-ми знаков и смыслами, что делает осмысленными допустимые последоват-ти знаков.

Инф-ция на ряду с материей и энергией яявл-ся первичным понятием нашего мира, и п/э-у в строгом смысле не м/т быть определена, но основные ее признаки(св-ва) м/о указать:

1)инф-ия приносит знания об окружающем мире, которых в рассмотренной точке до ее поступления не было

2)инф-ия не материальна, но проявл-ся в форме матер.носителей, именно: знаков, сигналов или в функции времени

3)инф-ия м.б.заключена как в знаках, так и в порядке их следования

4)знаки и сигналы несут инф-ию т/о для того получателя, кот.м/т их распознать. Расп-ие – это процесс отождествления знаков и сигналов с объектами и их отношениями в реальном мире.

Знаками явл-ся буквы алфавитов, мат.символы, звуки, дв-ия брачного танца у животных. Как уже отмечалось, знаковые сис-мы должны представлять собой мн-в о допустимых цепочек, напр-р, дв-ия морского сигнальщика не б/т понятны обык.чел-ку.

Наиболее изученными явл-ся знаковые сис-мы в кот-х символами явл-ся буквы алфавитов, а последоват-ми знаков – тексты. К таким знаковым сис-мам относ-ся естес.языки, языки программ-ия и язык науки. В рез-те раз-ия появилась наука – мат-ая лингвистика, кот-ая рассм-т языки как некоторые мн-ва осмысленных текстов. Правила, определяющие мн-ва текстов образ-тсиснтаксис языка, а описание мн-ва смыслов и соответствий м/у текстами и смыслами – семантику языка.

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

19.02.2003. №2

Расс-м пр-ры синт-го и семан-го разбора в ест-ом языке. В идеальном случае на любом языке предложение должно быть корректным, как семантически, так и синтаксически. Если в ест.языке допуск-ся некорректности в синтаксисе и м.б.понятен смысл предложения, то в формальных языках предложение в первую очередь должно быть правильным синтаксически.

Произведем синтаксич.разбор предложения

The man drives a car(чел-к управляет машиной)

the man – им.сущ-е

drives – гл-л

a car – им.сущ-е

м/о утвердить, что любое предложение с такой грамм-й структурой буд-т синтаксически корректным в англ.языке. Для описания подобных простых предложений часто испол-ся ф-ла Бэкуса-Наура(БНФ), кот.исп-ля для описания синтаксиса языков прогр-ия, она имеет форму нотаций и использует след-щие 4 символа:

::= присвоить
< - открыть
> - закрыть
| - или

Тогда рассм-ое предложение м/о представить виде:

<простое предложение>::=<подфраза сущ-го><глагол><подфраза сущ-го>;

<подфраза сущ-го>::=<артикль><имя сущ-ое>;

<имя сущ-ое>::= man,

<имя сущ-ое>::=car,

<артикль>::=the,

<артикль>::=a,

<глагол>::=drives

Связи, задаваемые ф-лой Б-Н м.б.представлены и графически в виде дерева-вывода:

простое предложение

подфраза сущ. подфраза гл-ла подфраза сущ.

артикль им.сущ. артикль им.сущ.

The man drives a car

м/о построить мн-во простых предложений, удовлетворяющих дан.структуре и синтаксически правильных, но не все они буд.им.смысл.( The car drives a man). Взависимости от синтаксического разбора одного итого же предложения м/о получить совершенно разные смыслы.

Рассм-м сл-ее предложение:

They are flying planes

they - местоимение

are – гл-л

flying planes – подфраза сущ-го, вкл-щая в себя причас-е flying и сущ-ое planes

При иаком грамм-м разборе смысл этого предложения: они есть летящие самолеты. Произведем др-й синт.разбор этого же предложения.

They – местоимение

are flying – сложная глагольная форма

planes – сущ-е.

Они управляют полетом самолетов(люди).

Т.О. в зависимости от СП-ба грамм-го разбора измен-ся смысл предложения. Этот пр-р показывает то, важное для формальных языков обстоят-во, что грам-й разбор исходного текста прогр-мы – важнейший этап ее компиляции.

^ Отношения и формальные сис-мы

Понятие форм-й сис-мы основано на понятии подстановки(редукции) на заданном мн-ве М объектов (символов, послед-тей сим-в, терминов).

//пр-р. это отн-ние рефлексивно, транзитивно и антисимметрично

= это отн-е эквивалентности, рефлексивно, транзитивно, симметрично.

Буд.рассм-ть т/о однородные бинарные отн-я R на мн-ве М, это мн-во пар (х,у) элементов хМ, уМ, кот-е нах-ся м/у собой в отн-нии R и явл-ся подмн-вом мн-ва ММ. Вместо бинарного отн-ия R на М м/о говорить об ориентированном графе (М,R), причем элементы М – это вершины графа, а пары из R это дуги графа. Любым 2м вершинам х и у из М соответствует не более1й стрелки (х,у), кот-я их связывает. Кроме того любой вершине х из М и дуге рR соотв-ет не более 1й вершины у, ведущей из вер-ны х, дуга в этом сл-е р=(х,у). Для конечных мн-в М отн-е R м.б.задано не т/о графически, но и в виде матриц, такие мат-цы наз-ся м-ми инцеденций.

a b c d a b c d a b c d

Замыкание

Рефлексивным замыкакнием (R^r) отн-ния R над мн-вом М н-ся пересечение всех рефлексивных отн-ний над М, содержащих R.

//пр-р R = {(0,1),(1,1),(1,2)}, M ={0,1,2}, тогда рефл-м замыканием явл-ся мн-во

R^r = {(0,0),(0,1),(1,1),(1,2),(2,2),(0,2)}

Транзитивным зам-ем (R⁺), бинарного отнош-ия R над мн-м М н-ся перечение всех транзитивный отн-й над М, содер-х R.

R⁺ = {(0,1),(0,2),(1,1),(1,2)}для нашего сл-я

Симметричное замыкание (R^s), R^s= R R^T, где R^T- обращение бинарного отношения R.

// для графического отображения – это просто перемена направления стрелок. Для нашего случая:

R^s = { (0,1), (1,0),(1,1),(1,2),(2,1)}

Транзитивно-рефлексивное зам-е (R^*) бинарного отн-ния R над М – это пересечение всех транзитивных и рефлексивных отн-й над М, кот-е содержат R

Симметрично-транзитивно-рефлексивное зам-е (R^□) это пересечение всех сим-х, транзитивных и рефлективных отн-й над М, кот-е содержат R.

Под конечным путем длины i (i≠0) от вершины х к вершине у в графе (М,→) понимают последовательность стрелок х=х₀→х₁, х₁→х₂,…,х_i_-1→x_i=y, здесь вершина х₀ – начало пути, вершина х – конец пути х_i есть вершина у. Видно, что (х,у)Rⁱ означает то, что в графе (М,R) сущ-т путь длины i от х к у. если последовательность стрелок бесконечна, то путь наз-т бесконечным. Отн-ние, а также ориентированный граф (М,→) наз-т НЕТЕРОВЫМ, если ни для какого х из М не сущ-т бесконечных путей исходящих из х. В нетеровом графе не м.б.циклов, т.е.путей длиной больше 1цы из некоторой вершины в нее же. Всякий путь в нетеровом графе явл-ся цепью, т.к.мн-во { х₀,х₁,…, x_i} упорядочено отношением → и х_μ≠х_η, μ≠η. Ориентированный граф тривиальным образом явл-ся нетеровым, если все пути в нем имеют ограниченную длину.

Редукция

Если сущ-т конечный путь из вер-ны х в вер-у у, что принято обозначать х→^*у, то говорят что х редуцируется к у. Элемент х из М наз-ся редуцируемым отн-но отношения (М,→), если сущ-т элемент у, т.ч.выполняется соотношение х→^*у. Путь длины i (i≠0) из х в у в графе (М,→) наз-ся тупиковым, если элемент у нередуцируемый. В нетеровом графе для каж-го х из М сущ-т покарайней мере 1н неруд-й элемент у, тогда алгоритм редукции на нетеровых отношениях м.б.описан сл.образом.

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

Строки

Строка – это конечная последовательность символов а₁, а₂,…,а_n, каж-й из кот-х принадлежит некоторому конечному алф-ту Σ, при этом символы в стороке могут повторяться.

Если строка содержит m символов, то говорят что она имеет длину m. Пустой строкой наз-т строку длины ноль, т.е.без единого символа и ее наз-т ε-строкой.(не путать с пробелом). |x|=m-длина строки.

Пусть Σ-некот-й алф-т, обозначим Σ^* мн-во опред-х над этим алф-м строк. Для Σ={0,1}; Σ^*= {ε,0,1,01,11,10,101,…} видно, что н-во Σ^* - предс-т собой бесконечное счетное мн-во элем-в, ε-строка всегда  Σ^*

Пусть сущ-т строка х Σ^* и |x|=m

Пусть сущ-т строка y Σ^* и |y|=n, тогда объединение строк ху им.длину |xy|=m+n – конкатенация.

Если х= а₁, а₂,…,а_m; у= b₁, b₂,…,b_n то |xy|= а₁а₂…а_mb₁b₂...b_n

Операция объединения строк – это ассциот-я операция, но не коммутативная. Для пустой строки справедливо εх=хε для люб.строки х.

Если некоторая срока z м.б.представлена как объединение строк х и у: z=ху, то строку х наз-т префиксом строки z, а строку у-суффиксом.

//z=00111

префиксы: ε,0,00,001,0011,00111

суффиксы: ε,1,11,111,0111,00111

если строка z т.ч.ее м/о представить как объединение 3х строк z=xwy, то строка w н-ся подстрокой строки z.

Формальным языком L над алф-ом Σ н-ся произвольное подмн-во мн-ва Σ^*.

25.02.2003 №3

если L₁ и L₂ это 2а формальных языка, то их объединение есть нов.форм.язык, т.ч.L= L₁L₂{xy| хL₁,уL₂ }

// L₁={0,01} и L₂={ε,0,10}

L= L₁L₂={0,01,00,010,010,0110}

Как и в сл-е объединения строк, операция объединения формальных языков ассициативна, но не коммутотивна. Еоммутотивность сохраняется только в случае объединения произв-го языка L с пустой строкой ε.

Объединение форм.языка L с самим собой: L²=L*L. В общем сл-е: L⁰= ε, L¹=L, L²=L*L.

^ Замыкание Клини форм.языка L н-ся

.Тогда

, тогда L^*=L⁺{ε}, анологично, можно записать замыкание Клини для мн-ва строк:

^ Введение а грам-ку.

Синтаксис языков программирования обычно описывают виде синтак-х диаграмм или форм Бекуса-наура. Рас-м принцип построения диаграмм на пр-ре понятия множитель.

л

юбой путь по этой диаг-ме проходит ч/з 1н или неск-ко узлов. Узел м.б.прямоугольным или круглым. Каж-у прям-му узлу соотв-ет своя синтакс.диаг-ма, п/э-у такой узел наз-ся нетерминальным. Круг.узел наз-ся терминальным(он больше не раскрывается). м/о записать эту синт.диаг-у в форме Бекуса Наура:

<множитель>::=<беззн.конст.>

|<перемен-я>

|<идентиф-р ф-ии>

^ Контексная гр-ка

Нетерм.сим-лы – пропис.буквы, термин. – строчные. Всякое дерево вывода начинается с корня S в соответствии с правилами вывода происходит дв-е по ветвям строющегося дерева до тех пор, пока все нетерм-е символы не буд.раскрыты ч/з терм-е. Мн-во терм-х симв-в образуют висящие вершины, если их прочесть слева направо, то получится строка.

Контексная гр-ка(К/Г) – это совокуп-ть 4х объектов: G=(N,T,P,S), где N-конеч.мн-во нетерм.симв-в, T-кон.мн-во терм.симв, P-кон.мн-во продук-й вида α→β, где α(NUT)⁺-без пустой строки, β(NUT)^*т.е.м/о получить и пуст.строку, S-начальный символ.

Если строка α(NUT)^* за 1н или неск-ко шагов выводится из начального сим-ла S, то такую строку наз-т сентенциальной формой К/Г-ки G.

Сентенцией гр-ки G наз-т произ-ю сентенциальную форму, составл-ю из симв-в мн-ва Т^*, т.е.произ.строку терм.сим-в, кот-я м.б.получена из нач-го сим-ла S. Тогда мн-во всех сентенций гр-ки G наз-т языком, пораждаемым гр-кой G и обоз-т L(G).

L(G)={x Т^*|S

_G^*х}.

Скачать файл (26.7 kb.)

Лекции по теории автоматов - файл Лекции.doc

Доступные файлы (1):

Лекции.doc