Размещено на http://www.allbest.ru/

Министерство образования и науки Российской Федерации

Федеральное государственное бюджетное образовательное

учреждение высшего профессионального образования

Кубанский государственный технологический университет

(ФГБОУ ВПО КубГТУ)

Кафедра Информационных систем и программирования

Институт Компьютерных систем и информационной безопасности

КУРСОВАЯ РАБОТА

По дисциплине Теория конечных автоматов и формальных языков

На тему Конечные автоматы. Автоматизированный практикум

Выполнил студент группы 12-КБ-ПР1

Марков Владислав Сергеевич

Краснодар

2014



Министерство образования и науки Российской Федерации

Федеральное государственное бюджетное образовательное

учреждение высшего профессионального образования

Кубанский государственный технологический университет

(ФГБОУ ВПО КубГТУ)

Кафедра Информационных систем и программирования

Институт Компьютерных систем и информационной безопасности

УТВЕРЖДАЮ

Зав. Кафедрой ИСП

профессор, д.т.н._____Л.А.Видовский

«____» _______________2014 г.

ЗАДАНИЕ

на курсовую работу

Студенту Маркову Владиславу Сергеевичу группы 12- КБ- ПР1 3 курса института компьютерных систем и информационной безопасности

направления 231000 - Программная инженерия

Тема работы: Конечные автоматы. Автоматизированный практикум

Содержание задания: Изучить тему «Конечные автоматы», разработать программу, демонстрирующую работы конечного автомата, разработать различные алгоритмы обработки конечных автоматов

Объём курсовой работы:

а) пояснительная записка 20 стр. .

Рекомендуемая литература Ключко, Власенко, Кушнир «Теория

автоматов и формальных языков . Учебное пособие».

Срок выполнения работы: с 3 сентября 2014г. по 20 декабря 2014г.

Дата защиты: 10 ноября 2014г.

Дата выдачи задания: 3 сентября 2014 г.

Дата сдачи работы на кафедру: 1 ноября 2014г. по 20 декабря 2014г.

Руководитель работы __________________________________________

(подпись)

Задание принял студент ________________________________________

(подпись)



РЕФЕРАТ

Стр. 20, рис. 10, библ. 3.

КОНЕЧНЫЙ АВТОМАТ, ЭКВИВАЛЕНТНЫЕ СОСТОЯНИЯ,

НЕДОСТИЖИМЫЕ СОСТОЯНИЯ, КОДИРОВАНИЕ, ПЕРЕХОДНЫЕ

СОСТОЯНИЯ

В данной работе были рассмотрены вопросы кодирования и представления конечного автомата. А также вопросы обработки и минимизации конечного автомата, что позволило написать программу на языке C#, которая демонстрирует все алгоритмы обработки конечных автоматов.

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



Содержание

Введение

1. Конечный автомат

1.1 Детерменированный конечный автомат

1.2 Недетерменированный конечный автомат

1.3 Минимизация конечных автоматов

2. Алгоритм расчёта

3. Руководство пользователя

Заключение

Список используемых источников

Приложение А



Введение

В современное время очень заметен информационный рывок. Нас стал окружать огромный объем информации. Информация для человека играет немаловажную роль, поэтому основной из задач человечества является передача информации.

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



1. Конечный автомат

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

Программисты очень часто сталкиваются с проблемой разделения строк на некоторые осмысленные части, проверки правильности ввода значений и т.д. В принципе, так как очень часто пользователем является человек, то самым естественным для него путем передачи информации будет человеческая речь. Тем не менее, задача выделения смысла из человеческой речи до сих пор не решена, поэтому для подобных случаев используется формальные описания некоторых структур - формальные грамматики. Конечные автоматы применяются для простейших грамматик. Обычно КА применятся для того, что называется лексическим анализом, т.е. для разбиения исходной строки на набор некоторых лексических единиц (например, выделение из текста слов и чисел). Простейший детерминированый КА работает следующим образом: в нем находится внутренний регистр для хранения текущего состояния и таблица правил вида "символ-состояние => состояние" позволяющая по текущему символу на ленте и текущему состоянию перейти в другое состояние (со сдвигом по ленте). Цепочка символов допустима, если КА завершил свою работу в одном из "разрешенных" состояний и не допустима в обратном случае.

1.1 Детерменированный конечный автомат

Детерминированным конечным автоматом (ДКА) называется машина, распознающая цепочки символов, в которой для каждой последовательности входных символов существует лишь одно состояние, в которое автомат может перейти из текущего.Она имеет входную ленту, разбитую на клетки, головку на входной ленте (входную головку) и управляющее устройство с конечным числом состояний. Конечный автомат М можно представить в виде множество (S, L, a, s, F), где

1) S - множество состояний управляющего устройства

2) L - входной алфавит (каждая клетка входной ленты содержит символ из I),

3) a - отображение SxL в S (если a( s ,a1 ) = s`, то всякий раз, когда М находится в состоянии s , а входная головка обозревает символ a1 , М сдвигает входную головку вправо и переходит в состояние s`),

4) s- выделенное состояние в S, называемое начальным

5) F - подмножество в S, называемое множеством допускающих (или заключительных ) состояний.

Пример ДКА изображен на рис 1

Рис.1 Пример ДКА

ДКА выполняет шаги, определяемые текущим состоянием его блока управления и входным символом, обозреваемым входной головкой. Каждый шаг состоит из перехода в новое состояние и сдвига входной головки на одну клетку вправо. Что язык представим регулярным выражением тогда и только тогда, когда он допускается некоторым конечным автоматом.

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

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

Конечный автомат можно описать с помощью диаграмм состояний и таблиц переходов.

Диаграмма состояний (или иногда граф переходов) -- графическое представление множества состояний и функции переходов. Представляет собой нагруженный однонаправленный граф, вершины которого -- состояния КА, ребра -- переходы из одного состояния в другое, а нагрузка -- символы, при которых осуществляется данный переход. Если переход из состояния а1 в а2 может быть осуществлен при появлении одного из нескольких символов, то над дугой диаграммы (ветвью графа) должны быть надписаны все они.

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

Рис. 2 Таблица переходов



1.2 Недетерменированный конечный автомат

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

Любой недетерминированный конечный автомат может быть преобразован в детерминированный так, чтобы их языки совпадали и такие атоматы называются эквивалентными. Однако, поскольку количество состояний в эквивалентном ДКА в худшем случае растёт экспоненциально с ростом количества состояний исходного НКА, на практике подобная детерминизация не всегда возможна. Кроме того, конечные автоматы с выходом в общем случае не поддаются детерминизации.

Для каждого состояния и каждого входного символа НКА имеет ноль или более вариантов выбора следующего шага. Он может также выбирать, сдвигать ему входную головку при изменении состояния или нет. Пример НКА приведет на рисунке 3. Приведем определение недетерминированного конечного автомата.



Рис.3. Пример НКА с пустыми переходами

Недетерминированным конечным автоматом называется множество (S, L, a , s, F), где

1) S - конечное множество состояний устройства управления;

2) L - алфавит входных символов;

3) a- функция переходов, отображающая S x (I U {i}) в множество подмножеств множества S;

4) s - начальное состояние устройства управления;

5) F - множество заключительных (допускающих) состояний.

Рис.4 НКА из одного состояния выходит несколько переходов, помеченных одним символом

С каждым НКА связан ориентированный граф, естественным образом представляющий функцию переходов этого автомата.

Приведем определение для графа ( или диаграммы) переходов автомата М = (S, I, a, s , F). Графом переходов автомата М называют ориентированный граф G = (S, E) с помеченными ребрами.

Существует дополнительный результат или возможность сопоставить какому-либо взятому НКА эквивалентную "детерминированную" машину. Однако детерминированный конечный автомат, эквивалентный данному НКА с n состояниями, может иметь вплоть до 2 в n степени состояний. Поэтому переход от НКА к детерминированному автомату не всегда дает эффективный способ моделирования недетерминированного конечного автомата.

1.3 Минимизация конечных автоматов

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

Минимизация конечных автоматов означает решение следующей задачи: как данному детерминированному, полному КА найти эквивалентный ему с наименьшим возможным количеством состояний. Из двух детерминированных автоматов допускающих один и тот же язык меньше памяти при реализации занимает тот автомат, у которого меньше состояний.

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

Автоматы упрощаются/минимизируются:

1. Удалив недостижимые состояния;

2. Удалив непродуктивные состояния;

3. Выявив эквивалентные состояния.

Для описания процесса нахождения наименьшего КА введем следующие определения:

Состояние qQ называется недостижимым, если под воздействием любого слова xУ* автомат не переходит в состояние q. То есть не существует слово x, для которого есть переход в состояние q.

В КА на рисунке 5 состояние q3 - недостижимое.

Рис. 5 Пример автомата с недостежимым состоянием

Непродуктивным называется то состояние qQ для которого не существует xУ* для которого (q0, x)(q, x1)(qf,) (нет вывода до финального состояния).

В КА на рисунке 6 состояние q3 - непродуктивное.



Рис. 6 Автомат с непродуктивным состоянием

Известно уже что два автомата называются эквивалентными, если они распознают один и тот же язык над алфавитом .

Учитывая, что можно определять эквивалентные автоматы, хотелось бы научиться находить наименьший среди них.

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

Говорят, что слово x различает состояния q1, q2 (q1, q2Q), если одно из этих состояний финальное, а другое не является заключительным.

Состояния q1 и q2 конечного автомата называются различными (неэквивалентны), если существует слово (цепочка) x, которое различает эти два состояния (из одного состояния достижимо заключительное состояние, а из другого -- нет).

Минимизация КА это уменьшение количества состояний. При изменении КА, минимизируя его, получается эквивалентный КА. Их языки должны совпасть.

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

Описание алгоритма минимизации конечного автомата:

1. Находим и удаляем в начальном КА все недостижимые и непродуктивные состояния.

2. Затем необходимо найти такое разбиение множества всех оставшиехся состояний автомата, чтобы каждое подмножество содержало неразличимые состояния. То есть множества состояний автомата разделяются на классы эквивалентности:

a) В I-й класс относим все конечные/финальные состояния (то есть состояния из множества F);

b) Во II-й класс относим все остальные состояния (то есть Q\F).

Назовем эти состояния 0-эквивалентными.

3. Строим новое одно-эквивалентное разбиение, выделив те состояния, которые по одинаковым символам переходят в 0-эквивалентные состояния.

4. Повторяется шаг 3, последовательно создавая (n+1)-эквивалентные состояния по n-эквивалентным, увеличивая так число классов эквивалентности.

5. Алгоритм заканчивается, когда (n+1)-эквивалентные состояния совпадают с n-эквивалентными.

Каждый полученный класс эквивалентности будет новым состоянием в новом минимизированном автомате.

В множество F' автомата внесём те состояния, которые содержат хотя бы одно финальное состояние из начального.

Полученный, минимизированный КА должен быть эквивалентен начальному КА.



2. Алгоритм расчёта

2.1 Задаваемые для расчёта параметры

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

N - количество состояний;

Матрица переходов состояний;

Матрица переходов выходных сигналов.

2.2 Описание алгоритма

конечный автомат программа алгоритм

Для кодирования конечного автомата применён следующий алгоритм:

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

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

3. Для нахождения потенциально эквивалентных состояний мы обрабатывали матрица переходов, где искали пары состояний с одинаковым выходных сигналом, заносили их в список.

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



3. Руководство пользователя

Запуск программы сопровождается открытием окна:

Рисунок 7 - Загрузка КА

В первой вкладе окна можно выбрать файл, из которого и будет формироваться конечный автомат. Во второй вкладе осуществляется кодирование КА. Пользователь вводит номер начального состояния и совокупность входных сигналов a.



Рисунок 8 - Кодирование КА

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

Рисунок 9 - Нахождение ПЭС

И в последней вкладке пользователь может найти все недостижимые состояния.

Рисунок 10 - Недостижимые состояния.



Заключение

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

Данная работа позволила нам более подробно рассмотреть такой объект, как конечный автомат. Основным моментом проведённого исследования является создания автоматизированного комплекса в виде приложения, которые позволяет наглядно продемонстрировать все возможности конечных автоматов.



Список используемых источников

1. Ключко В.И., Власенко А.В., Кушнир Н.В. Теория автоматов и формальных языков: учеб. пособие/Кубан. гос. технол. ун-т.- Краснодар: Изд. ФГБОУ ВПО «КубГТУ», 2012.- 151 с.

2. Теория автоматов и формальных языков. Методические указания к курсовому проекту для студентов всех форм обучения направлений 23100062 - Программная инженерия, 23070062 - Прикладная информатика / Сост.: А.В.Власенко, В.И.Ключко, Н.В.Кушнир; Кубан. гос. технол. ун-т. Каф. вычислительной техники и АСУ. - Краснодар: Изд. КубГТУ, 2012. - 23 с.

3. Теория автоматов и формальных языков: метод. указания по выполнению лабораторных работ для студентов всех форм обучения по направлениям 231000.62 Программная инженерия, 230700.62 Прикладная информатика / Сост.: В.И. Ключко, А.В. Власенко, Н.В. Кушнир; Кубан. гос. технол. ун-т. Каф. вычислительной техники и АСУ. - Краснодар.: Изд. ФГБОУ ВПО «КубГТУ», 2012. - 44 с.



Приложение А

Код программы:

Класс State()

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

namespace KR

{

public class State

{

int q;

public State[] a;

public State(int k)

{

this.q = k;

this.a = new State[2];

}

public State Next(int n)

{

return (a[n]);

}

public int Trans()

{

return (q);

}

}

}

Класс Form1()

using System;

using System.Collections.Generic;

using System.ComponentModel;

using System.Data;

using System.Drawing;

using System.Linq;

using System.Text;

using System.Windows.Forms;

using System.IO;

namespace KR

{

public partial class Form1 : Form

{

FileInfo fileinf;

public Form1()

{

InitializeComponent();

}

public bool check_exists(string fname)

{

if (File.Exists(fname))

{

return true;

}

else

{

MessageBox.Show("Анализируемый файл был перемещён или удалён");

return false;

}

}

public void update_fname_info(string fname)

{

string tmp_fname = fileinf.Name;

if (tmp_fname.Length > 25)

{

tmp_fname = tmp_fname.Substring(0, 25);

}

}

private void button1_Click(object sender, EventArgs e)

{

if (openFileDialog1.ShowDialog() == DialogResult.OK)

{

fileinf = new FileInfo(openFileDialog1.FileName);

update_fname_info(fileinf.Name);

}

}

private void button2_Click(object sender, EventArgs e)

{

string seporator = " ";

string[] S = textBox4.Text.Split(' ');

int[] z = new int[S.Length];

for (int i = 0; i < S.Length; i++)

{

z[i] = Convert.ToInt32(S[i]);

}

int w = Convert.ToInt32(textBox1.Text);

int[] Q = new int[S.Length];

TextReader fs = new StreamReader(fileinf.OpenRead());

string line = fs.ReadLine();

int N = Convert.ToInt32(line);

string[] Line = new string[N];

string[] Line1 = new string[N];

int[] V = new int[S.Length];

int u = 1;

Line[0] = fs.ReadLine();

int[,] k = new int[N, 2];

int[,] v = new int[N, 2];

while (u != 4 && Line[u] != "w")

{

Line[u] = fs.ReadLine();

u++;

}

fs.ReadLine();

for (int i = 0; i < N; i++)

{

Line1[i] = fs.ReadLine();

}

for (int i = 0; i < N; i++)

{

for (int j = 0; j < 2; j++)

{

string y = Convert.ToString(Line1[i][j]);

v[i, j] = Convert.ToInt32(y);

}

}

for (int i = 0; i < N; i++)

{

for (int j = 0; j < 2; j++)

{

string y = Convert.ToString(Line[i][j]);

k[i, j] = Convert.ToInt32(y);

}

}

State[] q = new State[N];

for (int i = 0; i < N; i++)

{

q[i] = new State(i);

}

for (int i = 0; i < N; i++)

{

for (int j = 0; j < 2; j++)

{

q[i].a[j] = q[k[i, j]];

}

}

State r = q[w];

for (int i = 0; i < S.Length; i++)

{

r = r.Next(z[i]);

Q[i] = r.Trans();

}

for (int i = 0; i < S.Length; i++)

{

textBox2.Text += Q[i].ToString() + (i < q.Length - 1 ? seporator :

string.Empty);

}

V[0] = v[w, z[0]];

for (int i = 1; i < S.Length; i++)

{

V[i] = v[Q[i - 1], z[i]];

}

for (int i = 0; i < S.Length; i++)

{

textBox3.Text += V[i].ToString() + (i < q.Length - 1 ? seporator :

string.Empty);

}

}

private void button3_Click(object sender, EventArgs e)

{

string seporator = " ";

TextReader fs = new StreamReader(fileinf.OpenRead());

string line = fs.ReadLine();

int N = Convert.ToInt32(line);

string[] Line = new string[N];

string[] Line1 = new string[N];

int u = 1;

Line[0] = fs.ReadLine();

int[,] k = new int[N, 2];

int[,] v = new int[N, 2];

while (u != 4 && Line[u] != "w")

{

Line[u] = fs.ReadLine();

u++;

}

fs.ReadLine();

for (int i = 0; i < N; i++)

{

Line1[i] = fs.ReadLine();

}

for (int i = 0; i < N; i++)

{

for (int j = 0; j < 2; j++)

{

string y = Convert.ToString(Line1[i][j]);

v[i, j] = Convert.ToInt32(y);

}

}

for (int i = 0; i < N; i++)

{

for (int j = 0; j < 2; j++)

{

string y = Convert.ToString(Line[i][j]);

k[i, j] = Convert.ToInt32(y);

}

}

int x = 0;

int[] anss = new int[2];

List<int[]> ans = new List<int[]>();

while (x != N)

{

for (int i = x + 1; i < 4; i++)

{

if (x != i)

{

if (Line1[x] == Line1[i])

{

anss[0] = x;

anss[1] = i;

ans.Add(anss);

}

else

continue;

}

}

x++;

}

foreach(int[] s in ans)

for (int i = 0; i < s.Length; i++)

{

textBox5.Text += s[i].ToString() + (i < s.Length - 1 ? seporator :

string.Empty);

}

}

private void button4_Click(object sender, EventArgs e)

{

string seporator = " ";

TextReader fs = new StreamReader(fileinf.OpenRead());

string line = fs.ReadLine();

int N = Convert.ToInt32(line);

string[] Line = new string[N];

int u = 1;

Line[0] = fs.ReadLine();

int[,] k = new int[N, 2];

while (u != 4 && Line[u] != "w")

{

Line[u] = fs.ReadLine();

u++;

}

for (int i = 0; i < N; i++)

{

for (int j = 0; j < 2; j++)

{

string y = Convert.ToString(Line[i][j]);

k[i, j] = Convert.ToInt32(y);

}

}

int[] ans = new int[N];

List<int> h = new List<int>();

for (int i = 0; i < N; i++)

{

ans[i] = i;

}

for (int m = 0; m < ans.Length; m++)

{

int S = 0;

for (int i = 0; i < N; i++)

{

for (int j = 0; j < 2; j++)

{

if (k[i, j] == ans[m])

S++;

else

continue;

}

}

if (S == 0)

h.Add(m);

else

continue;

}

foreach (int s in h)

textBox6.Text += s;

}

}

}

Размещено на Allbest.ru