Синтез распознающего автомата - Программирование, компьютеры и кибернетика курсовая работа

Сведение недетерминированного конечного автомата к детерминированному. Построение минимального детерминированного автомата из праволинейной грамматики двумя различными способами: с помощью сетей Петри и с помощью таблиц. Описание контрольного примера.


посмотреть текст работы


скачать работу можно здесь


полная информация о работе


весь список подобных работ


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

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.


Федеральное агентство по образованию
ГОУ ВПО «Ижевский государственный технический университет»
факультет «Информатика и вычислительная техника»
«Теория языков программирования и методы трансляции»
на тему «Синтез распознающего автомата»
студент гр. 4-78-10 Протозанов Е.С.
Проектирование распознающего автомата и его программная реализация необходимы при построении узлов цифровых вычислительных машин, при создании компиляторов, лингвистических процессоров и лексических анализаторов в трансляторах.
Цель курсовой работы состоит в изучении и использовании различных способов задания языков грамматиками. В курсовой работе необходимо использовать построение распознающего автомата и сети Петри для задания языков. Построить модель конечного автомата, распознающего заданный язык, реализовать полученный автомат программно.
Конечный автомат -- это абстрактный автомат без выходного потока, число возможных состояний которого конечно. Результат работы автомата определяется по его конечному состоянию.
Построить модель распознающего автомата на основе индивидуального задания
Для этого необходимо на основе формальной грамматики получить праволинейную грамматику, построить ее граф. По праволинейной грамматики построить автоматную. Затем построить недетерминированный распознающий автомат, задать таблицу переходов для него и изобразить граф переходов. Перейти от недетерминированного к полностью определенному детерминированному автомату. Задать таблицу переходов и изобразить граф переходов для полученного автомата. Минимизировать этот автомат. Задать таблицу переходов и граф переходов для минимального автомата.
Получить граф переходов минимального автомата по праволинейной грамматике используя сети Петри. Сравнить полученную автоматную сеть с графом минимального автомата.
Входными данными для автомата является цепочка из терминальных символов. На выходе автомата появляется состояние, отвергающее или допускающее входную цепочку.
Где Vt = {C1, C2,…, C18} - терминальный словарь,
Vn = {S, A, B, C, D, E, F}- нетерминальный словарь,
S - начальный символ грамматики, S Vn,
Правила вывода имеют следующий вид:
F -> C12 C13 C14 C15; F -> C16 C13 C14 C15; F -> C17 C18 C15.
Индивидуальным заданием является грамматика G', порождаемая из заданной формальной грамматики G.
Где V't={x0, x1, … , x7} - новый терминальный словарь, получаемый из Vt заменой ci на xi в соответствии с таблицей 1.
R' - множество правил вывода, получаемых из множества R, путем замены символов алфавита Vt символами алфавита V't, в соответствии с таблицей 1. Таблица 1 заполняется следующим образом: во вторую строку таблицы 1 заносятся имя фамилия и отчество, с обязательными пробелами между ними.
Третья строка таблицы 1 заполняется в соответствии с таблицей 2.
В результате, множество правил вывода праволинейной грамматики G' имеет вид:
Построим граф грамматики G' (рис. 1).
Процедура перевода праволинейной грамматики в автоматную.
Для получения автоматной грамматики, необходимо заменить правила, у которых в правой части перед нетерминальным символом стоит более чем один терминальный, несколькими правилами.
В результате замены правил, были получены следующие правила
В итоге получаем следующую автоматную грамматику
Процедуру построения недетерминированного автомата по автоматной грамматике:
1) Входным множеством автомата будет терминальное множество грамматики;
2) Множеством состояний автомата будет нетерминальное множество грамматики, а в качестве начального состояния будет выступать начальный нетерминальный символ грамматики - S;
3) По правилам 6.2, 8.2, 10.2, 12.2, 14.2, 15.5, 16.5, 17.4 состояния A1, B1, C1, D1, E1, F4, F8, F11 будут допускающими;
4) Для всех правил грамматики по правилу A xB вводим в автомате переход из состояния A в состояние B по входу x;
5) Чтобы получить полностью определенный автомат, вводим состояние ошибки - Err, и во все оставшиеся клетки записываем переход в состояние ошибки.
Результатом такого построения является недетерминированный автомат с одним начальным состоянием и с одним допускающим состоянием. Таблицей переходов полученного автомата является таблица 3.
Таблица 3 Таблица переходов недетерминированного автомата
Построим граф переходов недетерминированного автомата (рис. 2). Для облегчения читаемости графа не отображено состояние ошибки и переходы из всех состояний недетерминированного автомата в состояние ошибки по оставшимся входным символам.
Граф переходов недетерминированного автомата S


Для каждого недетерминированного конечного распознавателя существует эквивалентный детерминированный автомат, который допускает те же цепочки, что и недетерминированный.
АД - эквивалентный ему, детерминированный автомат.
1. Пометить первую строку таблицы переходов для АД множеством начальных состояний автомата АН.
2. По данному множеству состояний B, помечающему строку таблицы переходов автомата АД, для которой переходы еще не выполнены, вычислить те состояния АН, которые могут быть достигнуты из B с помощью каждого входного символа и поместить полученное множество состояний в состояние ячейки для автомата АД.
3. Для каждого нового множества, порожденного на шаге 2, посмотреть: имеется ли уже в АД строка, помеченная этим множеством, если нет, то создать новую строку и пометить ее этим множеством. Если множество уже использовалось как метка, то никаких действий не надо.
4. Если в таблице АД есть строка, для которой еще не вычислены переходы, то вернуться назад и применить к этой строке шаг 2. Если все переходы вычислены, то переходим к шагу 5.
5. Пометить строку как допускающее состояние АД, тогда и только тогда, когда она содержит допускающее состояние АН, иначе пометить как отвергающее.
Добавим состояние ошибки R и во всех пустых клетках запишем переход в состояние ошибки. Получим детерминированный автомат таблицей переходов которого является таблица 4.
Таблица 4 Таблица переходов детерминированного автомата
Построим граф переходов детерминированного автомата (рис. 3). Для облегчения читаемости графа не отображено состояние ошибки и переходы из всех состояний детерминированного автомата в состояние ошибки по оставшимся входным символам.
детерминированный автомат праволинейный грамматика
Граф переходов детерминированного автомата


Для получения минимального автомата воспользуемся методом разбиения. Метод разбиения заключается в разбиении множества состояний на непересекающиеся подмножества (блоки), такие, что неэквивалентные состояния попадают в разные блоки.
- условие подобия: состояния S и T должны быть либо оба допускающими, либо оба отвергающими;
- условие преемственности: для всех входных символов состояния S и T должны переходить в эквивалентные состояния, т.е. их преемники эквивалентны.
Сначала состояния разбиваются на 2 блока. Один содержит только допускающие, другой - отвергающие. Очевидно, никакое из состояний 1-го блока не эквивалентно ни одному состоянию второго блока, что следует из условия подобия. Затем происходит разбиение этих блоков на более мелкие по следующему алгоритму:
1). Если под действием какого-либо входного символа какая-то часть состояний данного блока переходит в состояния из другого блока, что нарушает условие преемственности, то необходимо разбить данный блок на части так, чтобы не нарушалось в одном блоке условие преемственности.
2). Необходимо повторять шаг 1 до тех пор, пока дальнейшее разбиение невозможно.
3). За один раз можно разбить только один блок.
Поделим на группы допускающих, недопускающих состояний:
{{S, M, S2, S4, A, B, C, D, E, F, F1, F2, F3, F5, F6, F7, F9, F10, Err}, {A1, B1, C1, D1, E1, F4, F8, F11}}.
Разобьем {S, M, S2, S4, A, B, C, D, E, F, F1, F2, F3, F5, F6, F7, F9, F10, Err} по входу x4:
{{S, M, S2, S4, D, E, F, F1, F2, F3, F5, F6, F7, F9, F10, Err}, {A, B, C}, {A1, B1, C1, D1, E1, F4, F8, F11}}.
Разобьем блок {S, M, S2, S4, D, E, F, F1, F2, F3, F5, F6, F7, F9, F10, Err} по входу x5:
{{S, M, S2, S4, D, E, F, F1, F2, F5, F6, F9, Err}, {A, B, C}, {F3, F7, F10}, {A1, B1, C1, D1, E1, F4, F8, F11}}.
Разобьем блок {S, M, S2, S4, D, E, F, F1, F2, F5, F6, F9, Err} по входу x5:
{{S, M, S2, S4, F, F1, F2, F5, F6, F9, Err}, {A, B, C}, {F3, F7, F10},
{D, E}, {A1, B1, C1, D1, E1, F4, F8, F11}}.
Разобьем блок {S, M, S2, S4, F, F1, F2, F5, F6, F9, Err} по входу x7: {{S, M, F, F1, F2, F5, F6, F9, Err}, {A, B, C}, {F3, F7, F10}, {S2, S4}, {D, E}, {A1, B1, C1, D1, E1, F4, F8, F11}}.
Разобьем блок {S, M, S2, S4, F, F1, F2, F5, F6, F9, Err} по входу x7:
{{S, M, F, F1, F2, F5, F6, F9, Err}, {A, B, C}, {F3, F7, F10}, {S2, S4}, {D, E}, {A1, B1, C1, D1, E1, F4, F8, F11}}.
Разобьем блок {S, M, F, F1, F2, F5, F6, F9, Err} по входу x4:
{{S, M, F, F1, F5, F9, Err}, {A, B, C},{F2, F6}, {F3, F7, F10}, {S2, S4}, {D, E}, {A1, B1, C1, D1, E1, F4, F8, F11}}.
Разобьем блок {S, M, F, F1, F5, F9, Err} по входу x2:
{{S, M, F, F9, Err}, {A, B, C}, {F2, F6}, {F1, F5}, {F3, F7, F10}, {S2, S4}, {D, E}, {A1, B1, C1, D1, E1, F4, F8, F11}}.
Разобьем блок {S, M, F, F9, Err}, выделив начальное состояние и состояние ошибки:
{{S}, {M, F, F9}, {Err}, {A, B, C}, {F2, F6}, {F1, F5}, {F3, F7, F10}, {S2, S4}, {D, E}, {A1, B1, C1, D1, E1, F4, F8, F11}}.
Дальнейшее разбиение невозможно. Полученные блоки состояний можно использовать для построения нового автомата, который эквивалентен исходному, и не содержит эквивалентных состояний. Для построения нового автомата, произведем замену обозначений блоков:
{A1, B1, C1, D1, E1, F4, F8, F11} -> K
В соответствии с этими обозначениями мы получаем минимальный автомат, таблица переходов которого представлена таблицей 5.
Таблица 5 Таблица переходов минимального автомата
Граф переходов минимального автомата построен на рис. 4. Для облегчения читаемости, на рисунке не изображено состояние L и ведущие к нему переходы.


Построим для грамматики G' сеть Петри. Для этого, поставим в соответствие нетерминальным символам позиции (кружки) сети. А терминалам - переходы (планки) сети. Пометим позиции и переходы соответствующими нетерминалами и терминалами.
Позиции соединяются дугами только через переходы, а переходы - через позиции. Если в правой части некоторого правило вывода из R' имеет место конкатенация терминалов, то в сети Петри между переходами, помеченными терминалами, должны появляться дополнительные позиции, которые можно помечать символами левой части правил вывода с индексами 1, 2, … .
Таким образом, позиции могут иметь несколько входящих и исходящих дуг, но переходы - в точности по одной входящей и не более чем одной исходящей дуге (исходящая дуга может отсутствовать, если в правой части правила вывода отсутствует замыкающий нетерминал).
Выполнив эти действия, получаем сеть Петри (рис. 5).
Для полноты соответствия построенной сети Петри распознающему автомату Мура, введем не показанную на рис. 5 заключительную позицию Z, в которую направим дуги из всех переходов, ранее не имевших исходящих дуг. В результате получим новую сеть Петри (рис. 6).
Сеть Петри с заключительной позицией Z
Далее, необходимо минимизировать сеть Петри. Для этого определим в ней идентичные фрагменты. Итак, идентичными фрагментами являются позиции D и E c инцидентными им переходами x5 и x4. Также, позиции A, B и С с инцидентными им переходами x4 и x7. Позиции S1 и S3, F2 и F5, F3 и F6, F1 и F4, F6 и F8 можно склеить попарно. В результате получаем минимизированную недетерминированную сеть Петри (рис. 7).
Этот этап соответствует минимизации числа состояний автомата, но он выполнен для автомата, сохраняющего недетерминированность. Источником недетерминированности, очевидно, могут являться лишь позиции свободного выбора, исходящие дуги которых являются входящими дугами переходов, помеченных одинаковыми терминалами.
Недетерминированность устраняется склеиванием двух позиций Pl и Pk в одну (Pl, Pk). При этом позиции (Pl, Pk) инцидентны все исходящие дуги, являющиеся исходящими дугами позиций Pl и Pk.
В полученной сети Петри отсутствуют позиции свободного выбора, исходящие дуги которых являются входящими дугами переходов, помеченных одинаковыми терминалами. А значит, сеть Петри (рис. 7) уже детерминирована и минимизирована.
Теперь обозначим позиции сети Петри следующими буквами:
Уберем переходы из сети Петри, дуги подпишем терминалами переходов, тогда получим граф переходов (рис.8).
Граф переходов полученный из сети Петри


Сравнив полученный граф (рис.8) с графом минимального автомата (рис. 4) мы видим, что они идентичны. Значит, минимальный автомат построен правильно.
Программа используется для построения моделей машины Тьюринга
Программа предназначена для моделирования работы машины Тьюринга. Программа обрабатывает цепочку входных символов согласно правилам грамматики, записанным в виде таблицы переходов, и устанавливает состояние, позволяющее определить допустимость цепочки.
1. Операционная система семейства Windows, Linux или MacOS с графическим фреймворком Qt версии не менее 4.0
2. Оперативная память не менее 32 мегабайт
3. 10 мегабайт места на жестком диске
В настройках программы задается следующая информация:
1. Таблица переходов конечного автомата
На вход программе подается строка, символы которой входят в множество входных символов машины. Строка проверяется на корректность и вводит в программу только содержащиеся во входном множестве символы.
Для допуска строки вводится дополнительное состояние, не являющеся состоянием минимального автомата, но требуемое для окончания работы машины Тьюринга с допускающим результатом.
Контрольный пример необходим для тестирования программной реализации автомата - программы «turing».
Входная цепочка символов автомата. Цепочки символов состоят из символов входного алфавита автомата
Построим цепочки символов, для контрольного примера, исходя из праволинейной грамматики.
Для проверки правильности работы автомата нужно проверить его с помощью допустимых цепочек.
Что бы получить допустимую цепочку символов необходимо взять одно из правил, в левой части которого стоит начальный символ S.
Выписать все терминальные символы из этого правила и если в конце стоит нетерминал, то перейти к одному из правил, в левой части которого стоит этот нетерминал.
Выписать терминальные символы из этого правила и если в конце стоит нетериманл, то перейти к новому правилу и т.д., пока мы не дойдем до правила, правая часть которого кончается терминалом.
Итак, получаем допускающие цепочки:
1) S -> x5 x5 x4 B -> x4 - допустить
отсюда получаем цепочку: x5 x5 x4 x4;
2) S -> x3 C -> x7 E -> x5 - допустить
3) S -> x1 F -> x3 x0 x6 - допустить
Для полной проверки автомата получим несколько недопустимых цепочек. Их можно получить, если выписывать терминалы, не доходя до терминала, который стоит последним в правиле.
Или же если записать терминал, которого нету в правой части ни одного из правил, в левой части которых стоит необходимый нетерминал.
Результаты испытания программы представлены в таблице 6.
Таблица 6 Результат испытания программы
Результаты испытания программы совпали с ожидаемыми, что говорит о правильности построения минимального автомата и реализации программы.
Методические указания для самостоятельной работы студентов по дисциплине "Теория вычислительных процессов и структур". Ч1/ Ижевск. гос. техн. университет; Сост. Сенилов М.А. ИжГТУ, 2000.
ГОСТ 19.005 - 78. Общие требования к программным документам // Единая система программной документации. - М.: Издательство стандартов, 1980. - 2с.
1. Заголосочный файл mainwindow.cpp
class MainWindow : public QMainWindow
explicit MainWindow(QWidget *parent = 0);
bool isAllowedState(const QChar c);
QString getMeaningByState(const QChar c);
void on_ruleTable_cellPressed(int row, int column);
void on_comboWriteSymbol_currentIndexChanged(int index);
void on_comboMoveTo_currentIndexChanged(int index);
void on_comboSetState_currentIndexChanged(int index);
void on_comboSpaceSymbol_currentIndexChanged(int index);
void on_horizontalSlider_sliderMoved(int position);
void on_lineEndState_editingFinished();
void on_lineAllowedState_editingFinished();
2. Заголовочный файл visualization.h
class visualisation : public QWidget
explicit visualisation(QWidget *parent = 0);
void setResultText(const QString str);
MainWindow::MainWindow(QWidget *parent) :
ui->comboMoveTo->addItem(trUtf8("Влево"));
ui->comboMoveTo->addItem(trUtf8("Стоять"));
ui->comboMoveTo->addItem(trUtf8("Вправо"));
connect(this, SIGNAL(stateChanged()), ui->widget, SLOT(repaint()));
connect(&timer, SIGNAL(timeout()), this, SLOT(step()));
ui->widget->setRealPos(&ribbonPos);
ui->widget->setState(¤tState);
bool MainWindow::isStopState(const QChar c)
void MainWindow::writeSymbol(const QChar c)
if (ribbonPos == ribbon.count() - 1)
ribbon.append(ui->comboSpaceSymbol->itemText(ui->comboSpaceSymbol->currentIndex()).at(0));
ribbon.prepend(ui->comboSpaceSymbol->itemText(ui->comboSpaceSymbol->currentIndex()).at(0));
ui->widget->setResultText(QString(""));
if (!isStopState(currentState) && ready)
logString += trUtf8("Входной символ '");
in = ui->comboSpaceSymbol->itemText(ui->comboSpaceSymbol->currentIndex()).at(0);
logString += in + trUtf8("', устанавливается состояние '");
QString inSymbol = ui->ruleTable->horizontalHeaderItem(i)->text();
while(in != inSymbol && i < ui->ruleTable->columnCount())
inSymbol = ui->ruleTable->horizontalHeaderItem(i)->text();
QString state = ui->ruleTable->verticalHeaderItem(j)->text();
while(state != currentState && j < ui->ruleTable->rowCount())
state = ui->ruleTable->verticalHeaderItem(j)->text();
QChar asd = ui->ruleTable->item(j, i)->text().at(2);
logString += asd + trUtf8("', записывается символ '");
this->writeSymbol(ui->ruleTable->item(j, i)->text().at(0));
logString += ui->ruleTable->item(j, i)->text().at(0);
logString += trUtf8("', каретка ");
if (ui->ruleTable->item(j, i)->text().at(1) == QString("L").at(0))
logString += trUtf8("движется влево");
else if (ui->ruleTable->item(j, i)->text().at(1) == QString("R").at(0))
logString += trUtf8("движется вправо");
logString += trUtf8("стоит на месте");
ui->buttonStartStop->setText(trUtf8("Старт"));
ui->logWidget->addItem(QString(trUtf8("Достигли конечного состояния; остановка")));
ui->widget->setResultText(this->getMeaningByState(currentState));
ui->widget->setResultText(trUtf8("Состояние недопустимо"));
currentState = ui->comboBaseState->itemText(ui->comboBaseState->currentIndex()).at(0);
void MainWindow::on_buttonSetStates_clicked()
for (int i = 0; i < ui->lineStateSymbols->text().length(); i++)
stateSet += ui->lineStateSymbols->text().at(i);
for (int i = 0; i < ui->lineInputSymbols->text().length(); i++)
symbolsSet += ui->lineInputSymbols->text().at(i);
QList stateList = stateSet.toList();
QList symbolsList = symbolsSet.toList();
ui->ruleTable->setRowCount(stateSet.count());
ui->ruleTable->setColumnCount(symbolsSet.count());
ui->meaningsTable->setRowCount(stateSet.count());
ui->meaningsTable->setColumnCount(1);
ui->ruleTable->setItem(0,0, new QTableWidgetItem);
for (int i = 0; i < stateList.length(); i++)
ui->ruleTable->setVerticalHeaderItem(i, new QTableWidgetItem(QString(stateList.at(i))));
ui->meaningsTable->setVerticalHeaderItem(i, new QTableWidgetItem(QString(stateList.at(i))));
ui->comboSetState->addItem(stateList.at(i));
ui->comboBaseState->addItem(stateList.at(i));
ui->lineStateSymbols->setText(str);
for (int i = 0; i < symbolsList.length(); i++)
ui->ruleTable->setHorizontalHeaderItem(i, new QTableWidgetItem(QString(symbolsList.at(i))));
ui->comboWriteSymbol->addItem(symbolsList.at(i));
ui->comboSpaceSymbol->addItem(symbolsList.at(i));
ui->lineInputSymbols->setText(str);
for (int i = 0; i < ui->ruleTable->rowCount(); i++)
for (int j = 0; j < ui->ruleTable->columnCount(); j++)
ui->ruleTable->setItem(i,j, new QTableWidgetItem);
for (int i = 0; i < ui->ruleTable->rowCount(); i++)
for (int j = 0; j < ui->ruleTable->columnCount(); j++)
asd[0] = ui->ruleTable->horizontalHeaderItem(j)->text().at(0);
asd[2] = ui->ruleTable->verticalHeaderItem(i)->text().at(0);
ui->ruleTable->item(i, j)->setText(asd);
void MainWindow::on_load_triggered()
QString fileName = QFileDialog::getOpenFileName(this, trUtf8("Загрузить таблицу"),
if( !file.open( QIODevice::ReadOnly ) )
stream.setVersion( QDataStream::Qt_4_2 );
ui->ruleTable->setColumnCount(columns);
ui->ruleTable->setItem(i, j, new QTableWidgetItem);
ui->ruleTable->item(i, j)->setText(str);
ui->ruleTable->setHorizontalHeaderItem(j, new QTableWidgetItem(str));
ui->ruleTable->setVerticalHeaderItem(i, new QTableWidgetItem(str));
ui->meaningsTable->setRowCount(stateSet.count());
ui->meaningsTable->setColumnCount(1);
QList endStateList = endStateSet.toList();
QList allowedStateList = allowedStateSet.toList();
QList stateList = stateSet.toList();
for (int i = 0; i < endStateList.length(); i++)
for (int i = 0; i < allowedStateList.length(); i++)
ui->lineAllowedState->setText(str);
for (int i = 0; i < stateList.length(); i++)
ui->comboSetState->addItem(stateList.at(i));
ui->comboBaseState->addItem(stateList.at(i));
ui->meaningsTable->setVerticalHeaderItem(i, new
QTableWidgetItem(stateList.at(i)));
ui->meaningsTable->setItem(i, 0, new QTableWidgetItem);
ui->meaningsTable->item(i, 0)->setText(asd);
ui->comboBaseState->setCurrentIndex(posa);
ui->lineStateSymbols->setText(str);
QList symbolsList = symbolsSet.toList();
for (int i = 0; i < symbolsList.length(); i++)
ui->comboWriteSymbol->addItem(symbolsList.at(i));
ui->comboSpaceSymbol->addItem(symbolsList.at(i));
ui->comboSpaceSymbol->setCurrentIndex(posc);
ui->lineInputSymbols->setText(str);
void MainWindow::on_save_triggered()
QString fileName = QFileDialog::getSaveFileName(this,
if( !file.open( QIODevice::WriteOnly ) )
stream.setVersion( QDataStream::Qt_4_2 );
int rows = ui->ruleTable->rowCount();
int columns = ui->ruleTable->columnCount();
stream << ui->comboBaseState->currentIndex() << ui-
stream << endStateSet << allowedStateSet;
str = ui->ruleTable->item(i, j)->text();
str = ui->ruleTable->horizontalHeaderItem(j)->text();
str = ui->ruleTable->verticalHeaderItem(i)->text();
for (int i = 0; i < ui->meaningsTable->rowCount(); i++)
stream << ui->meaningsTable->item(i, 0)->text();
void MainWindow::on_buttonSetString_clicked()
for (int i = 0; i < ui->lineInputString->text().length(); i++)
if (symbolsSet.contains(ui->lineInputString->text().at(i)))
ribbon.append(ui->lineInputString->text().at(i));
ui->widget->setResultText(QString(""));
void MainWindow::on_ruleTable_cellPressed(int row, int column)
QString inSymbol = ui->ruleTable->horizontalHeaderItem(column)->text().at(0);
QString curState = ui->ruleTable->verticalHeaderItem(row)->text().at(0);
QChar ruleSym = ui->ruleTable->item(row, column)->text().at(0);
QChar ruleState = ui->ruleTable->item(row, column)->text().at(2);
ui->currentInputSymbol->setText(inSymbol);
ui->currentMachineState->setText(curState);
for (int i = 0; i < ui->comboWriteSymbol->count(); i++)
if (ruleSym == ui->comboWriteSymbol->itemText(i).at(0))
ui->comboWriteSymbol->setCurrentIndex(i);
for (int i = 0; i < ui->comboSetState->count(); i++)
if (ruleState == ui->comboSetState->itemText(i).at(0))
ui->comboSetState->setCurrentIndex(i);
if (ui->ruleTable->item(row, column)->text().at(1) == QString("L").at(0))
ui->comboMoveTo->setCurrentIndex(0);
if (ui->ruleTable->item(row, column)->text().at(1) == QString("R").at(0))
ui->comboMoveTo->setCurrentIndex(2);
ui->comboMoveTo->setCurrentIndex(1);
if (ui->comboWriteSymbol->count() != 0 && ui->comboSetState->count() != 0)
result[0] = ui->comboWriteSymbol->itemText(ui->comboWriteSymbol->currentIndex()).at(0);
result[2] = ui->comboSetState->itemText(ui->comboSetState->currentIndex()).at(0);
if (ui->comboMoveTo->currentIndex() == 0)
else if (ui->comboMoveTo->currentIndex() == 2)
ui->ruleTable->item(currentX, currentY)->setText(result);
void MainWindow::on_comboWriteSymbol_currentIndexChanged(int index)
void MainWindow::on_comboMoveTo_currentIndexChanged(int index)
void MainWindow::on_comboSetState_currentIndexChanged(int index)
void MainWindow::on_comboSpaceSymbol_currentIndexChanged(int index)
ui->widget->setSpaceSymbol(ui->comboSpaceSymbol->itemText(ui->comboSpaceSymbol->currentIndex()).at(0));
void MainWindow::on_buttonStep_clicked()
void MainWindow::on_buttonStartStop_clicked()
ui->buttonStartStop->setText(trUtf8("Старт"));
ui->buttonStartStop->setText(trUtf8("Стоп"));
void MainWindow::on_horizontalSlider_sliderMoved(int position)
void MainWindow::on_buttonReset_clicked()
ui->widget->setResultText(QString(""));
currentState = ui->comboBaseState->itemText(ui->comboBaseState->currentIndex()).at(0);
void MainWindow::on_lineEndState_editingFinished()
for (int i = 0; i < ui->lineEndState->text().length(); i++)
if (stateSet.contains(ui->lineEndState->text().at(i)))
endStateSet += ui->lineEndState->text().at(i);
str += ui->lineEndState->text().at(i);
bool MainWindow::isAllowedState(const QChar c)
return allowedStateSet.contains(c);
QString MainWindow::getMeaningByState(const QChar c)
for (int i = 0; i < ui->meaningsTable->rowCount(); i++)
if (ui->meaningsTable->verticalHeaderItem(i)->text().at(0) == c)
QString str = ui->meaningsTable->item(i, 0)->text();
void MainWindow::on_lineAllowedState_editingFinished()
for (int i = 0; i < ui->lineAllowedState->text().length(); i++)
if (stateSet.contains(ui->lineAllowedState->text().at(i)))
allowedStateSet += ui->lineAllowedState->text().at(i);
void MainWindow::on_pushButton_clicked()
void MainWindow::on_about_triggered()
QMessageBox *box = new QMessageBox;
box->setIconPixmap(QPixmap::fromImage(QImage(":/images/about.png")));
box->setText(QString(trUtf8("Автор: Протозанов Евгений\nИжГТУ 4-78-10 2012")));
box->setWindowTitle(QString(trUtf8("Машина Тьюринга")));
void MainWindow::on_about_Qt_triggered()
QMessageBox::aboutQt(this, trUtf8("О Qt"));
visualisation::visualisation(QWidget *parent) :
void visualisation::paintEvent(QPaintEvent *)
int spacerX = (this->width() - 620)/2;
int spacerY = (this->height() - 100)/2;
QPainter *painter = new QPainter();
painter->setRenderHint(QPainter::Antialiasing);
//=======================================
int real_mid = *realPos - (*fakePos - mid);
painter->setPen(QPen(QColor(Qt::black)));
painter->drawText(300 + x + spacerX, 60 + spacerY, 20, 20, Qt::AlignCenter, c);
painter->drawRect(300 + x + spacerX, 60 + spacerY, 20, 25);
painter->setBrush(QBrush(QColor(Qt::black)));
painter->drawPie(300 + 20*(*fakePos - mid) + spacerX, 80 + spacerY, 20, 20, 240 * 16, 60 * 16);
painter->drawText(0, 30 + spacerY, this->width(), 20, Qt::AlignCenter, resultText);
painter->drawRect(300 + spacerX, spacerY, 20, 25);
painter->setPen(QPen(QColor(Qt::white)));
painter->drawText(300 + spacerX, 2 + spacerY, 20, 20, Qt::AlignCenter, *state);
//=======================================
void visualisation::setRibbon(QList *r)
void visualisation::setSpaceSymbol(QChar c)
void visualisation::setFakePos(int *pos)
void visualisation::setRealPos(int *pos)
void visualisation::setState(QChar *c)
void visualisation::setResultText(const QString str)
Построение праволинейной грамматики, автоматной грамматики по полученным результатам. Построение недетерминированного конечного автомата. Сведение недетерминированного конечного автомата к детерминированному. Описание программы и контрольного примера. курсовая работа [674,9 K], добавлен 13.06.2012
Специфика построения и минимизации детерминированного автомата методом разбиения. Построение детерминированной сети Петри, моделирующей работу распознающего автомата. Особенности программной реализации праволинейной грамматики, построение ее графа. курсовая работа [615,1 K], добавлен 19.06.2012
Изучение методов построения конечного автомата, распознающего заданный язык, и принципы его программной реализации. Проектирование комбинационной и принципиальной схем распознающего конечного автомата с использованием библиотеки интегральных микросхем. дипломная работа [1,8 M], добавлен 18.08.2013
Составление формальной грамматики, недетерминированный конечный автомат. Построение конечного автомата, программное моделирование работы конечного автомата. Граф детерминированного автомата, Синтаксическая диаграмма. Блок-схемы, примеры разбора строк. курсовая работа [486,2 K], добавлен 19.11.2010
Важный частный случай недетерминированного конечного автомата. Проверка нечетности числа единиц в произвольной цепочке, состоящей из нулей и единиц. Составление формальной грамматики, блок-схемы и программы, моделирующей работу конечного автомата. курсовая работа [210,8 K], добавлен 05.12.2013
Синтез автомата для преобразования двоично-десятичного кода. Кодировка алфавитов и состояний. Построение булевых функций, минимизация. Разметка вход-выходных слов для автомата Мили и автомата Мура. Реализация на элементах малой степени интеграции. контрольная работа [141,5 K], добавлен 14.10.2012
Устройство управления и синхронизации в структуре микропроцессора. Порядок синтеза конечного автомата (КА) для устройства управления ЭВМ. Алгоритм функционирования КА, заданный с помощью графа, функции переходов. Состояние триггеров в микросхеме. методичка [1019,0 K], добавлен 28.04.2009
Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д. PPT, PPTX и PDF-файлы представлены только в архивах. Рекомендуем скачать работу .

© 2000 — 2021



Синтез распознающего автомата курсовая работа. Программирование, компьютеры и кибернетика.
Курсовая работа: Огляд технології сервлетів
Решебник По Математике Контрольная Работа 6
Реферат: Adrienne Rich Online Interviews Essay Research Paper
Курсовая работа по теме Планирование и реализация инновационных проектов
Контрольная Работа По Алгебре 10 Класс Колмогоров
Конкурирующие Инвестиции Реферат
Курсовая работа: Налогообложение современного предприятия. Скачать бесплатно и без регистрации
Дипломная работа: Особенности воспитания единственного ребенка в семье
Плюсы И Минусы Спорта Сочинение
Реферат: Альфа банк. Скачать бесплатно и без регистрации
Тема Итоговое Сочинение В Декабре 2022 Года
Реферат: Расчет факторов риска при страховании автомобиля
Контрольная работа по теме Внебюджетные фонды Российской Федерации
Реферат: Резервы и пути повышения рентабельности предприятия
Курсовая работа по теме Реклама как возможная маркетинговая стратегия предприятия
Реферат по теме Навязчивости
Доклад по теме Мартиника
Реферат по теме Педагогическая деятельность и взгляды Н.И.Пирогова
Курсовая работа по теме Коммерческий подкуп
Курсовая Работа На Тему Взаимодействие Православия, Католицизма И Протестантизма В Условиях Современного Мира
Восприятие советско-югославского конфликта западными странами - Международные отношения и мировая экономика курсовая работа
Содержание теорий происхождения государства - Государство и право курсовая работа
Система мотивации в профессиональной сфере - Менеджмент и трудовые отношения дипломная работа