Построение модели многоленточной машины Тьюринга для алфавита русского языка

10

Введение

Тема моей курсовой работы «Построение модели многоленточной машины Тьюринга для алфавита русского языка». Для разработки программы применяется среда программирования Visual C++6.0. Тип системы является пакет прикладных программ.

Данная модель осуществляет морфологический разбор слова.

Морфологический разбор: анализ слов в предложении на принадлежность их к той или иной части речи.

Морфология слов русского языка определяется по аффиксу - окончанию и суффиксу слова. Назовем это правило правилом морфологического разбора. Однако есть слова, которые имеют окончание, подходящее для некоторой формы слова, но являются совершенно другой формой. Например, «-ать» говорит, что слово есть глагол (прыгать, бежать). Но есть слово «кровать», которое есть существительное. Значит, из правила морфологического разбора есть исключения. Так же есть слова, которые не изменяют свою форму. Например, предлоги, «не», наречия, «столь» и т.д. Значит, есть дополнения к правилу морфологического разбора. Эти дополнения можно представить как исключения из правила. Таким образом, мы пришли к определенному логическому описанию морфологического разбора слов.

1. Общие сведения

Turing

ИВГУ.Э.001.ТЗ.17.1.1.М

01.09.2009 - 21.12.2009

Программа предназначена для разбора предложения с помощью многоленточной машины Тьюринга.

1. Решение задач связанных с морфологическим разбором предложения.

2. Решение задач связанных с синтаксическим разбором предложения.

3. Решение задач связанных с семантическим разбором предложения.

3.1 Краткие сведения об объекте автоматизации

Объектом автоматизации является процесс разбора предложения.

3.2 Сведения об условиях эксплуатации объекта автоматизации и характеристика окружающей среды

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

На рисунке 1 изображена диаграмма прецедентов, описывающая основные варианты использования системы.

Рисунок 1. Диаграмма прецедентов

На рисунке 2 изображена диаграмма деятельности системы.

Рисунок 2. Диаграмма деятельности

На рисунках 3 и 4 изображены контекстные IDEF0 диаграмма и IDEF0 нулевого уровня.

Рисунок 3. IDEF0 диаграмма основной функции

Рисунок 4. IDEF0 диаграмма нулевого уровня

На рисунке 5 изображена контекстная DFD диаграмма

Рисунок 5. DFD диаграмма нулевого уровня

- Отказ в работе не должен приводить к потере информации.

- Ошибка ввода информации не должна влиять на дальнейшую работу программы.

- При отказе программа не должна приводить к зависанию системы.

Должны быть предусмотрены средства повышающие надёжность функционирования и сохранность информации, например, дублирование программы на носителях.

Для защиты информации от несанкционированного доступа рекомендуется хранение информации в зашифрованном виде и наличие каскадов паролей для доступа к определённому виду информации.

Для сохранности информации необходимо в двух копиях хранить инсталляционный вариант. А текущую информацию копировать с периодом один раз в неделю.

- В базе данных должна содержаться достаточно полная и точная информация.

- В базе данных должна храниться только необходимая информация.

- Информация, хранимая в базе данных должна быть защищённой.

Подсистема анализа предложения должна осуществлять разбор предложения с достаточной степенью точности и правильности.

Интерфейс пользователя должен быть:

- Удобным.

- Простым.

- Понятным.

4.3 Требования к видам обеспечения

Требования для программного обеспечения:

- На компьютере должна быть установлена операционная система Microsoft Windows.

Требования для информационного обеспечения:

- Целостность.

- Полнота.

- Точность.

- Достоверность.

Требования к техническому обеспечению:

- Состав технических средств стандартный: монитор, мышка, клавиатура и внешние устройства. Смотри рисунок 6, на котором изображена диаграмма развёртывания.

- Объём оперативной памяти не менее 256 Мбайт.

Рисунок 6. Диаграмма развёртывания

Требования к математическому обеспечению:

- Программа реализует алгоритм машины Тьюринга.

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

- Используются математические преобразования для дополнения семантических сетей за счет других семантических сетей.

- При приобретении знаний используются только известные математические соотношения.

- Используются математические отношения для распознавания словосочетаний.

Требования к лингвистическому обеспечению:

- В программе может использоваться только русский язык.

5. Состав и содержание работ по содержанию системы

5.1 Перечень этапов работ по созданию системы

Этапы по созданию системы следующие:

1. Техническое задание.

2. Технический проект.

3. Рабочий проект.

5.2 Перечень организационно-исполнительных работ

Исполнитель: Тонкова Н.С. студент 4-го курса, 3 группа.

6. Технический проект на систему

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

Алан Тьюринг (1912-1954) - английский математик. Он дал определение алгоритма через построение, названное машиной Тьюринга. В 1936 году Тьюринг предложил определение вычислимости, которое основано на анализе осуществления алгоритма человеком, располагающим ручкой для письма и бумагой. Он рассматривает это как последовательность очень простых действий следующего вида:

(a) - запись или стирание одного символа;

(b) - перенесение внимания с одного участка бумаги на другой.

На каждом шаге алгоритм определяет действие, которое будет совершено на следующем шаге. Это зависит только от (i) символа на участке бумаги, который обозревается в данный момент глазом (или другим рецептором) и (ii) текущим состоянием (мысли) человека. Чтобы обеспечить возможность реализации алгоритма, мы предполагаем, что это состояние полностью определяется самим алгоритмом и предысторией его работы. Оно может включать частичную запись того, что произошло до сих пор, но не зависит от настроения или сообразительности исполнителя алгоритма или от его самочувствия. Кроме того, существует только конечное число различимых состояний, в которых может находиться исполнитель, так как он конечен в рассматриваемых аспектах. Состояние исполнителя может, конечно, изменяться в результате действия, предпринятого на этом шаге.

Тьюринг изобрёл конечные машины, которые выполняют алгоритмы, представленные таким способом. Для каждого алгоритма существует своя, хотя и не единственная, машина. Рассмотрим кратко эти машины.

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

В состав Машины Тьюринга входит бесконечная в обе стороны лента, разделённая на ячейки (лента представляет собой бумагу, которая требуется исполнителю для осуществления алгоритма; каждый квадрат представляет собой порцию ленты, обозреваемую в данный момент) и управляющее устройство, способное находится в одном из множества состояний. Число возможных состояний управляющего устройства конечно и точно задано. В каждой ячейке может быть записан некоторый символ из фиксированного (для данной машины) конечного множества, называемого алфавитом данной машины. Один из символов алфавита выделен и называется «пробелом» (s0) предполагается, что изначально вся лента пуста, то есть, заполнена пробелами.

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

Таким образом, чтобы задать машину Тьюринга, надо указать следующие объекты:

· произвольное конечное множество A (алфавит); его элементы называются символами;

· некоторый выделенный символ a0 A (пробел, или пустой символ);

· конечное множество S, называемое множеством состояний;

· некоторое выделенное состояние s0 S, называемое начальным;

· таблицу переходов, которая определяет поведение машины в зависимости от состояния и текущего символа;

· некоторое подмножество F S, элементы которого называются заключительными состояниями (попав в такое состояние, машина останавливается).

Таблица переходов устроена следующим образом: для каждой пары (текущее состояние, текущий символ) указана тройка (новое состояние, новый символ, сдвиг) Здесь сдвиг одно из чисел -1 (влево), 0 (на месте) и 1 (направо). Таким образом, таблица переходов есть функция типа:

S x A > S x A x {-1,0,1},

определенная на тех парах, в которых состояние не является заключительным.

Остается описать поведение машины Тьюринга. В каждый момент имеется некоторая конфигурация, складывающаяся из содержимого ленты (формально говоря, содержимое ленты есть произвольное отображение Z > A), текущей позиции головки (некоторое целое число) и текущего состояния машины (элемент S). Преобразование конфигурации в следующую происходит по естественным правилам: мы смотрим в таблице, что надо делать для данного состояния и для данного символа, то есть, выясняем новое состояние машины, меняем символ на указанный и после этого сдвигаем головку влево, вправо или оставляем на месте. При этом если новое состояние является одним из заключительных, работа машины заканчивается. Остается договориться, как мы подаем информацию на вход машины и, что считается результатом ее работы. Будем считать, что алфавит машины, помимо пробела, содержит символы 0 и 1 (а также, возможно, еще какие-то символы). Входом и выходом машины будут конечные последовательности нулей и единиц (двоичные слова). Входное слово записывается на пустой ленте, головка машины ставится в его первую клетку, машина приводится в начальное состояние и запускается. Если машина останавливается, результатом считается двоичное слово, которое можно прочесть, начиная с позиции головки и двигаясь направо (пока не появится символ, отличный от 0 и 1).

Страницы: 1, 2