Археология об основании Рима: Новые раскопки проясняют и такой острый дискуссионный вопрос, как дата самого возникновения Рима...
Опора деревянной одностоечной и способы укрепление угловых опор: Опоры ВЛ - конструкции, предназначенные для поддерживания проводов на необходимой высоте над землей, водой...
Топ:
Характеристика АТП и сварочно-жестяницкого участка: Транспорт в настоящее время является одной из важнейших отраслей народного хозяйства...
Комплексной системы оценки состояния охраны труда на производственном объекте (КСОТ-П): Цели и задачи Комплексной системы оценки состояния охраны труда и определению факторов рисков по охране труда...
Интересное:
Аура как энергетическое поле: многослойную ауру человека можно представить себе подобным...
Средства для ингаляционного наркоза: Наркоз наступает в результате вдыхания (ингаляции) средств, которое осуществляют или с помощью маски...
Что нужно делать при лейкемии: Прежде всего, необходимо выяснить, не страдаете ли вы каким-либо душевным недугом...
Дисциплины:
2020-04-01 | 116 |
5.00
из
|
Заказать работу |
РЕФЕРАТ
Курсовая работа по дисциплине «Основы дискретной математики» на тему: «Программа – конструктор для построения МП – транслятора по его параметрам с последующей проверкой задаваемых пользователем цепочек»
В работе рассмотрен вопрос построения автоматов-трансляторов с магазинной памятью, проверкой задаваемых цепочек. Программу можно использовать в учебных целях, для построения автоматов с последующим использованием созданных файлов в других приложениях, создаваемых с помощью среды программирования Delphi.
Работа посвящена изучению такого раздела дискретной математики, как автоматы-трансляторы с магазинной памятью. На основе полученных знаний разработан программный продукт, реализующий построение МП-транслятора путем задания управляющей таблицы.
При работе приложение позволяет пользователю построить транслятор. Затем пользователь может выполнить проверку цепочки. Если пользователь изучит теоретический материал, то работа не вызовет большого затруднения. Теоретический материал излагается ниже в записке, а также в реализованной справочной службы программы. Работа программного продукта реализована достаточно наглядно, что делает его пригодным для использования его в целях более качественного обучения студентов по указанному выше разделу дискретной математики.
Ключевые слова:
дискретная математика, МП-транслятор, управляющая таблица, входная цепочка, выходная цепочка.
Введение
В настоящее время компьютеры все чаще используются не только для обработки данных и уточнения параметров моделей, но и для постановки компьютерного эксперимента, во многих случаях призванного заменить дорогостоящий натурный эксперимент. Поэтому дальнейшее развитие математического моделирования связано с применением современных средств компьютерной математики как инструмента подготовки высококвалифицированных специалистов, построения содержательных моделей, накопления и хранения информации, полученной в результате исследования этих моделей, т.е. с разработкой новых информационных технологий для образования и научных исследований.
Развитие научно-технического прогресса ведет к росту потребности в технических, математических и иных расчетах, в соответствующих программных продуктах. Не последнее место в научных исследованиях занимает математическое моделирование с применением информационных технологий. В электротехнике и электронике широко используют MathCAD для проектирования всевозможные процессов, импульсов, сигналов.
Также математическое моделирование используется в металлургических направлениях. В частности в ДГМА производится математическое моделирование горячей и холодной прокатки на языке PASCAL. Производится математическое моделирование процесса переворачивания сталеразливочных ковшей, расчет механических свойств разных металлов и сплавов в условиях холодной деформации, анализ влияния выходных параметров процесса холодной прокатки на величину основных энергосиловых параметров.
В связи с широким распространением быстродействующих электронно-вычислительных машин главной задачей математического моделирования стала задача обеспечения интерактивности взаимодействия исследователя с моделируемым объектом, в том числе, в реальном времени. В научных исследованиях это сводится к определению архитектуры и состава программно аппаратных средств интерфейса пользователя, предварительной обработке исходных данных с учетом их амплитуды, частотных и временных характеристик, идентификации, прогнозированию и управлению, исследуемым объектом. Научные достижения включают методики разработки инструментальных средств и ряд алгоритмов для обеспечения человеко-машинного интерфейса, предварительной обработки данных и идентификации нелинейных динамических систем, визуализации полученных результатов.
Реферат
Дискретная математика – раздел математики, занимающийся изучением свойств объектов конечного характера.
Дискретная математика включает в себя такие разделы как множества, алгебра высказываний, теория конечных автоматов, теория графов.
В этой курсовой работе будет предпринята попытка раскрыть как можно шире понятие автоматов-трансляторов с магазинной памятью.
Delphi является одним из наиболее быстрых средств для реализации поставленной задачи (написание кода программы и визуальное создание вида программы занимают очень короткий промежуток времени по сравнению с другими языками).
Однако основная ценность приложения – алгоритмическая поддержка. С одной стороны разработка качественного интерфейса заметно облегчается при использовании сред визуального программирования, а с другой стороны для разработки завершенных корректных приложений необходима теоретическая база.
При разработке программного продукта использовалась интегрированная среда Delphi 6.
Теория конечных автоматов
Конечный автомат(в дальнейшем КА) - абстрактное вычислительное устройство с фиксированным и конечным объемом памяти, которое на входе читает цепочки(последовательности символов некоторого алфавита), а на выходе сообщает об их принадлежности к некоторому множеству, для распознания которого он построен.
По сути КА работает как фильтр, который пропускает "правильные" цепочки. Другая трактовка КА - компактный алгоритм распознания регулярных, в том числе и бесконечных множеств, который строит программист перед началом кодирования (реализацией алгоритма на конкретном языке).
Далеко не для всех регулярных множеств можно построить
КА-распознаватель, так как КА не имеет возможности сосчитать и запомнить количество символов обрабатываемой цепочки. Для этой цели используется специальное устройство - магазин, в который можно помещать символы или удалять их, запоминая или сравнивая количество символов входной цепочки. Такой автомат называется автоматом распознавателем с магазинной памятью (сокращенно – МП-распознавателем).
Но в ряде случаев при обработке регулярного множества необходимо его преобразование в другое множество. Такие действия может выполнять МП-транслятор, на выходе которого будет формироваться выходная цепочка.
МП-транслятор задается:
1.Конечным множеством входных символов (включая символ конца цепочки "¶").
2.Конечным множеством выходных символов.
3.Конечным множеством магазинных символов (включая маркер дна магазина - '¤').
4.Конечным множеством состояний.
5.Упpавляющей таблицей, котоpая каждой комбинации трех параметров: входной символ, магазинный символ(верхний символ магазина), состояние - ставит в соответствие четыре параметра: действие с магазином, входным символом, состоянием и выходным символом.
5.Hачальной конфигурацией (начальное состояние и начальное содеpжимое магазина).
6.Множеством допускающих конфигураций (комбинаций - состояние МП-транслятора и верхний символ магазина в момент, когда приходит символ "конец цепочки").
Допускаемые операции над входом:
1.Держать входной символ (Д).
2.Перейти к очередному символу (П).
Примечание: запрещено запрашивать входной символ после прихода символа "¶"("конец цепочки").
Допускаемые операции над магазином
1.Втолкнуть в магазин магазинный символ, к примеру А (Вт.А).
2.Вытолкнуть из магазина верхний символ, к примеру А (Выт.А).
3.Оставить магазин без изменений (О).
Ряд ячеек управляющей таблицы может без деления на поля заполняться символом Е (состояние ошибки). Если МП-транслятор попал в такое состояние, то обработка цепочки прекращается и такая цепочка отвергается.
Результатом работы для МП-транслятора будет сообщение "допустить" или "отвергнуть" и цепочка получаемая на выходе. Входная цепочка допускается МП-транслятором, если под воздействием этой цепочки автомат, начавший работу в начальной конфигурации (в начальном состоянии и с начальным содержимым магазина) приходит к допускающей конфигурации после поступления символа "конец цепочки", иначе цепочка отвергается.
Рассмотрим строение ячейки в таблице переходов МП-транслятора.
Рис. 1 – вид ячейки МП-транслятора
Построение МП-транслятора для распознания заданного множества цепочек - процесс творческий и неоднозначный. Теоретически для распознания одного и того же множества цепочек можно построить бесконечное множество КА. Описанный выше принцип распознания применим далеко не ко всякому регулярному множеству.
Рис. 3 – Функциональная схема программного продукта
Иерархия экранных форм
Главное окно
Для создания нового МП-транслятора необходимо выбрать из меню файл Новый. Добавить символы, состояния, магазинные символы с помощью кнопки Добавить.
В результате этих действий получим заготовку управляющей таблицы. Потом следует заполнить ячейки, для этого необходимо щелкнуть левой кнопкой мыши по ячейке. После этого появится окно редактирования ячейки.
Окно редактирования ячейки
Заполнив таблицу, пользователь может проверить цепочку на принадлежность данному множеству для которого построен МП- транслятор. Для этого нужно щелкнуть на кнопке РАЗБОР ЦЕПОЧКИ и в окно РАЗБОР ввести разбираемую цепочку. Вводимая цепочка должна содержать символы, используемые при построении транслятора, иначе будет выведено сообщение
Если не возникнет ошибка вводимых данных, будет получен результ:
цепочка допущена или нет и цепочка на выход.
Требования к аппаратным средствам
Для эффективной работы спроектированного программного комплекса необходимо выполнение следующих требований к аппаратному и программному обеспечению:
· CPU не ниже Pentium-133
· 8 Mb оперативной памяти (желательно 32 Mb)
· минимум 1Mb свободного дискового пространства
· 1 Mb видеопамяти
· операционная система Windows 95/98/2000/NT.
· Манипулятор мышь.
Приложение было тестировано на следующих конфигурациях:
· Intel Celeron 400, 32 Mb RAM, Windows 98
· Intel Pentium || Celeron 266, 64 Mb RAM, Windows 98
· AMD K6 || 333, 64 Mb RAM, Windows NT 4.0
· Intel Pentium 166, 16 Mb RAM, Windows 95
Вывод
В ходе разработки курсового проекта я ближе ознакомился с теорией МП- трансляторов, научился писать программы - конструкторы для построения МП – транслятора по его параметрам с последующей проверкой задаваемых цепочек, закрепил знания по системному программированию. Разрабатывая программу, я научился применять знания дискретной математике, что облегчает работу программиста.
В дальнейшем хотелось бы улучшить программный продукт -улучшить интерфейс.
Листинг программы:
unit DmKurs;
interface
uses
Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,
MPunit, ComCtrls, ToolWin, Menus, StdCtrls, ExtCtrls, Grids,Addun,
ActnList, ImgList, ExtDlgs, Buttons, ButtonComps, RunText;
type
TMainPr = class(TForm)
StatusBar1: TStatusBar;
MainMenu1: TMainMenu;
pc1: TPageControl;
File1: TMenuItem;
Help1: TMenuItem;
New1: TMenuItem;
Save1: TMenuItem;
Load1: TMenuItem;
N1: TMenuItem;
Exit1: TMenuItem;
tsEdit: TTabSheet;
ActionList1: TActionList;
alCreateNew: TAction;
ImageList1: TImageList;
tsCheck: TTabSheet;
dgMP: TDrawGrid;
alRepaint: TAction;
ToolBar1: TToolBar;
tbNew: TToolButton;
alSave: TAction;
sd1: TSaveDialog;
ToolButton1: TToolButton;
ToolButton2: TToolButton;
alLoad: TAction;
od1: TOpenDialog;
pm: TPopupMenu;
New2: TMenuItem;
Save2: TMenuItem;
Load2: TMenuItem;
N2: TMenuItem;
Exit2: TMenuItem;
spd1: TSavePictureDialog;
tsAdd: TTabSheet;
alExit: TAction;
tlSavePicture: TToolButton;
N3: TMenuItem;
N4: TMenuItem;
N5: TMenuItem;
alHelp: TAction;
ToolButton3: TToolButton;
N6: TMenuItem;
N7: TMenuItem;
GroupBox2: TGroupBox;
buSymbAdd: TButton;
buDelSymb: TButton;
buClear: TButton;
Panel6: TPanel;
Label15: TLabel;
buNextStep: TButton;
lbStep: TListBox;
rgCheck: TRadioGroup;
buCheck: TButton;
plStData: TPanel;
buStopTrace: TBitBtn;
Panel1: TPanel;
lbResult: TLabel;
plChain: TEdit;
GroupBox1: TGroupBox;
mmNotes: TMemo;
Panel3: TPanel;
Label9: TLabel;
sgStartMag: TStringGrid;
buStartAdd: TButton;
buStartDel: TButton;
Panel4: TPanel;
Label10: TLabel;
cbStartingSt: TComboBox;
Panel5: TPanel;
Label11: TLabel;
Label12: TLabel;
Label13: TLabel;
Label14: TLabel;
cbStEd: TComboBox;
cbMagStEd: TComboBox;
cbSymbEd: TComboBox;
buCellEdit: TButton;
Panel2: TPanel;
Panel7: TPanel;
Label1: TLabel;
Label4: TLabel;
Label6: TLabel;
Label8: TLabel;
lbStNum: TLabel;
lbFirstSt: TLabel;
Label7: TLabel;
sgMagList: TStringGrid;
sgSymbList: TStringGrid;
sgMagStart: TStringGrid;
Panel8: TPanel;
sgGood: TStringGrid;
Label5: TLabel;
rgWhatAdd: TRadioGroup;
Panel9: TPanel;
Button1: TButton;
procedure FormClose(Sender: TObject; var Action: TCloseAction);
procedure tsAddShow(Sender: TObject);
procedure tsEditShow(Sender: TObject);
procedure buStartAddClick(Sender: TObject);
procedure buStartDelClick(Sender: TObject);
procedure alCreateNewExecute(Sender: TObject);
procedure cbStartingStChange(Sender: TObject);
procedure buCellEditClick(Sender: TObject);
procedure sgGoodSelectCell(Sender: TObject; ACol, ARow: Integer;
var CanSelect: Boolean);
procedure buSymbAddClick(Sender: TObject);
procedure buDelSymbClick(Sender: TObject);
procedure buClearClick(Sender: TObject);
procedure buCheckClick(Sender: TObject);
procedure PaintMP;
procedure ChangeGood(i,j:integer);
procedure dgMPDrawCell(Sender: TObject; ACol, ARow: Integer;
Rect: TRect; State: TGridDrawState);
procedure alRepaintExecute(Sender: TObject);
procedure dgMPTopLeftChanged(Sender: TObject);
procedure dgMPSelectCell(Sender: TObject; ACol, ARow: Integer;
var CanSelect: Boolean);
procedure alSaveExecute(Sender: TObject);
procedure alLoadExecute(Sender: TObject);
procedure FormCreate(Sender: TObject);
procedure buStopTraceClick(Sender: TObject);
procedure FormResize(Sender: TObject);
procedure Step;
procedure SetTrace;
procedure buNextStepClick(Sender: TObject);
procedure alExitExecute(Sender: TObject);
procedure alHelpExecute(Sender: TObject);
procedure N5Click(Sender: TObject);
procedure Button1Click(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;
var
MainPr: TMainPr;
MP:TMPRasp;
Color1:Integer=clRed;
Color2:Integer=clWhite;
Color3:Integer=clYellow;
Color4:Integer=clFuchsia;
implementation
uses EditUn, AboutUn;
const CellSize=60;
LineEnd='¶';
drx=4;
dry=4;
Ready:boolean=false;
StepOver:boolean=false;
Num1=4;
TracePar:array [1..Num1] of String=
('Номер символа в строке: ',
'Символ: ',
'Текущее состояние: ',
'Верхний символ магазина: ');
SaveDir='Save';
PicturesDir='Pictures';
var DrawSt,DrawMg,DrawSmb:boolean;
tmp:TBitmap;
TempParams:TSaveMP;
initialdir:string;
St,tt,ss:word;
TraceResult:boolean;
SymbI:integer;
Chain:string;
{$R *.DFM}
procedure TMainPr.FormClose(Sender: TObject; var Action: TCloseAction);
var MDR:integer;
begin
if Ready then begin
MDR:=MessageDlg('Сохранить текущий МП-транслятор?',mtConfirmation,[mbYes,mbNo,mbCancel],0);
if MDR<>MrCancel then begin
if MDR=mrYes then alSaveExecute(Sender);
Mp.Del;
Mp.Free;
TMP.free;
Ready:=false;
end
else Action:=caNone;
end;
end;
procedure TMainPr.tsAddShow(Sender: TObject);
var i,j:byte;
begin
if Ready then begin
with mp.params do begin
sgGood.ColCount:=MagSymbNum+1;
sgGood.RowCount:=StateNum+1;
for j:=1 to StateNum do
sgGood.cells[0,j]:='S'+inttostr(j);
for i:=1 to MagSymbNum do begin
sgGood.cells[i,0]:=MagSymbols[i];
for j:=1 to StateNum do begin
if MP.Good[j,i] then
sgGood.Cells[i,j]:='Доп.'
else
sgGood.Cells[i,j]:='Отв.'
end;
end;
end;
lbStNum.caption:=inttostr(Mp.Params.StateNum);
lbFirstSt.caption:=inttostr(Mp.Params.StartingState);
sgMagList.colcount:=mp.Params.MagSymbNum;
sgSymbList.colcount:=mp.Params.SymbNum+1;
sgMagStart.ColCount:=length(mp.params.StartingMagState);
for i:=1 to mp.Params.MagSymbNum do begin
sgMagList.Cells[i-1,0]:=mp.Params.MagSymbols[i];
end;
if Mp.Params.SymbNum=0 then sgSymbList.Cells[0,0]:=LineEnd
else
for i:=1 to mp.Params.SymbNum do begin
sgSymbList.Cells[i,0]:=mp.Params.Symbols[i];
end;
for i:=1 to Length(mp.Params.StartingMagState) do begin
sgMagStart.Cells[i-1,0]:=mp.Params.StartingMagState[i];
end;
end;
end;
procedure TMainPr.tsEditShow(Sender: TObject);
var i:byte;
begin
if Ready then begin
With MP.Params do begin
sgStartMag.ColCount:=length(StartingMagState);
for i:=1 to Length(StartingMagState) do begin
sgStartMag.Cells[i-1,0]:=StartingMagState[i];
end;
if DrawSt then begin
cbStartingSt.items.clear;
for i:=1 to StateNum do begin
cbStartingst.items.add('S'+inttostr(i));
end;
cbStEd.items.clear;
cbStartingst.ItemIndex:=StartingState-1;
cbStartingst.text:=cbStartingst.items[cbStartingst.ItemIndex];
for i:=1 to StateNum do begin
cbStEd.items.add('S'+inttostr(i));
end;
cbStEd.ItemIndex:=StartingState-1;
cbStEd.text:=cbStEd.items[cbStEd.ItemIndex];
end;
if DrawMg then begin
cbMagStEd.items.clear;
for i:=1 to MagSymbNum do begin
cbMagStEd.items.add(MagSymbols[i]);
end;
cbMagStEd.text:=cbMagStEd.items[0];
end;
if DrawSmb then begin
cbSymbEd.items.clear;
for i:=1 to SymbNum do begin
cbSymbEd.items.add(Symbols[i]);
end;
cbSymbEd.text:=cbSymbEd.items[0];
end;
end;
DrawSt:=false;
DrawMg:=false;
DrawSmb:=false;
end;
end;
procedure TMainPr.buStartAddClick(Sender: TObject);
var MR:word;
begin
if ready then begin
WhatAdd:=MgA;
Send:=copy(Mp.Params.MagSymbols,2,Length(Mp.Params.MagSymbols));
MR:=Adding.ShowModal;
if MR=100 then begin
MP.Params.StartingMagState:=Mp.Params.StartingMagState+res;
end;
tsEdit.Hide;
tsEdit.Show;
end;
end;
procedure TMainPr.buStartDelClick(Sender: TObject);
begin
if ready then begin
if length(Mp.Params.StartingMagState)>1 then begin
Mp.Params.StartingMagState:=
copy(Mp.Params.StartingMagState,1,Length(Mp.Params.StartingMagState)-1);
end;
tsEdit.Hide;
tsEdit.Show;
end;
end;
procedure TMainPr.alCreateNewExecute(Sender: TObject);
label 1;
var c:word;
begin
if not ready then begin
Ready:=true;
1: MP:=TMPRasp.Create;
lbResult.Caption:='';
mmNotes.Clear;
Mp.Init;
tsAdd.Hide;
tsAdd.show;
DrawSt:=true;
DrawMg:=true;
DrawSmb:=true;
TMP:=TBitmap.create;
mmNotes.text:='';
plChain.Text:='';
dgMP.DefaultColWidth:=CellSize;
dgMP.DefaultRowHeight:=CellSize;
paintMP;
end
else begin
c:=MessageDlg('Сохранить файл?',mtConfirmation,[mbYes,mbNo,mbCancel],0);
case c of
mrYes: begin
alSaveExecute(Sender);
goto 1;
end;
mrNo: begin
goto 1;
end;
mrCancel: begin
;
end;
end;
end;
end;
procedure TMainPr.cbStartingStChange(Sender: TObject);
begin
if ready then begin
if cbStartingSt.ItemIndex<>-1 then
Mp.Params.StartingState:=cbStartingSt.ItemIndex+1;
end;
end;
procedure TMainPr.buCellEditClick(Sender: TObject);
var MR:integer;
begin
if ready then begin
ii:=cbStEd.ItemIndex+1;
if length(trim(cbMagStEd.text))=1 then
jj:=mp.MagSymbPos(cbMagStEd.text[1]);
if length(trim(cbSymbEd.text))=1 then
kk:=mp.SymbPos(cbSymbEd.text[1]);
if (ii>0) and (jj>0) and (kk>0) then begin
Mr:=Editing.ShowModal;
if mr=111 then begin
PaintMP;
mp.cell[ii,jj,kk]:=temp;
end;
end
else
MessageDlg('Неверно определена ячейка!'
,mtWarning,[mbOk],0);
end;
end;
procedure TMainPr.sgGoodSelectCell(Sender: TObject; ACol, ARow: Integer;
var CanSelect: Boolean);
begin
ChangeGood(ARow,ACol);
sgGood.Hide;
sgGood.Show;
end;
procedure TMainPr.buSymbAddClick(Sender: TObject);
var MR:Integer;
begin
if ready then begin
WhatAdd:=SmbA;
Send:=copy(Mp.Params.Symbols,1,Length(Mp.Params.Symbols));
MR:=Adding.ShowModal;
if MR=100 then begin
plChain.Text:=plChain.Text+res;
lbResult.Caption:='';
end;
tsCheck.Hide;
tsCheck.Show;
end;
end;
procedure TMainPr.buDelSymbClick(Sender: TObject);
begin
plChain.Text:=copy(plChain.Text,1,Length(plChain.Text)-1);
lbResult.Caption:='';
end;
procedure TMainPr.buClearClick(Sender: TObject);
begin
plChain.Text:='';
lbResult.Caption:='';
end;
procedure TMainPr.buCheckClick(Sender: TObject);
var s:string;
i:integer;
ok:boolean;
begin
if Ready then begin
s:=plChain.Text;
if Length(s)=0 then begin
MessageDlg('Не введена цепочка',mtWarning,[mbOk],0);
plChain.SetFocus;
end
else begin
ok:=true;
for i:=1 to length(s) do begin
if pos(s[i],MP.Params.Symbols)=0 then ok:=false;
end;
if ok then begin
case rgCheck.ItemIndex of
0: begin
if Mp.CheckChain(s) then
s:='ДОПУСК '
else
s:='НЕТ ДОПУСКА';
MessageDlg(s+' цепочки',mtinformation,[mbOk],0);
lbResult.Caption:=S;
end;
1: begin
if plChain.Text<>'' then begin
tsEdit.enabled:=false;
bucheck.Enabled:=false;
buSymbAdd.Enabled:=false;
buDelSymb.Enabled:=false;
buClear.Enabled:=false;
buNextStep.Enabled:=True;
buStopTrace.Enabled:=True;
plChain.enabled:=false;
StepOver:=True;
plStData.Caption:='';
TempParams.Params:=Mp.Params;
TempParams.Good:=Mp.Good;
TempParams.cell:=Mp.Cell;
lbStep.Items.Clear;
With MP do begin
SymbI:=1;
TraceResult:=false;
State:=Params.StartingState;
Chain:=plChain.Text;
Stack.Init(Params.StartingMagState);
Ss:=SymbPos(Chain[SymbI]);
tt:=MagSymbPos(Stack.Top);
St:=State;
end;
SetTrace;
PaintMP;
end;
end;
end;
end
else begin
MessageDlg('Некоторые символы строки не соответствуют алфавиту',mtWarning,[mbOk],0);
plChain.SetFocus;
end;
end;
end;
end;
procedure TMainPr.PaintMP;
begin
if Ready then
with MP.Params do begin
dgMP.ColCount:=SymbNum+3;
dgMp.RowCount:=StateNum*MagSymbNum+1;
dgMP.hide;
dgMP.Show;
end;
end;
procedure TMainPr.dgMPDrawCell(Sender: TObject; ACol, ARow: Integer;
Rect: TRect; State: TGridDrawState);
var a:trect;
x,y,y1,y2:word;
s,D:string;
TC:TMPCell;
begin
if ready then begin
a.Left:=1;
a.Top:=1;
a.Right:=CellSize;
a.Bottom:=CellSize;
tmp.Height:=Cellsize;
tmp.width:=Cellsize;
x:=Acol-1;
y:=ARow;
with mp.params do begin
if y mod MagSymbNum = 0 then
y1:=y div MagSymbNum
else y1:=(y div MagSymbNum)+1;
if y mod MagSymbNum = 0 then
y2:=MagSymbNum
else y2:=y mod MagSymbNum;
with tmp.canvas do begin
if (Acol<2) or (Arow=0) then
Brush.Color:=Color1
else
if (x=Symbnum+1) then
Brush.Color:=Color4
else
Brush.Color:=Color2;
Rectangle(a);
if StepOver and (((y1=st) and (y2=tt) and (x=ss) and (x>0))
or ((y1=st) and (y2=tt) and (ss=0) and (x=Length(Symbols)+1)))
then begin
Brush.Color:=Color3;
Rectangle(a);
end;
if (Arow=0) and (acol>1) then begin
if (x<=SymbNum) then
TextOut((tmp.Width-TextWidth(Symbols[x])) div 2,
(tmp.Height-TextHeight(Symbols[x])) div 2,Symbols[x])
else TextOut((tmp.Width-TextWidth(LineEnd)) div 2,
(tmp.Height-TextHeight(LineEnd)) div 2, LineEnd);
end;
if (Acol=0) and (arow>0) then begin
TextOut((tmp.Width-TextWidth('S'+inttostr(y1))) div 2,
(tmp.Height-TextHeight('S')) div 2,'S'+inttostr(y1));
end;
if (Acol=1) and (arow>0) then begin
TextOut((tmp.Width-TextWidth(MagSymbols[y2])) div 2,
(tmp.Height-TextHeight(MagSymbols[y2])) div 2,MagSymbols[y2]);
end;
if (Acol>1) and (arow>0) then begin
if (x>SymbNum) then begin
if MP.Good[y1,y2] then s:='Доп.'
else s:='Отв.';
TextOut((tmp.Width-TextWidth(s)) div 2,
(tmp.Height-TextHeight(s)) div 2,s);
end
else begin
TC:=MP.Cell[y1,y2,x];
if tc.NextState=Err then begin
s:='Ошибка';
TextOut((tmp.Width-TextWidth(s)) div 2,
(tmp.Height-TextHeight(s)) div 2,s);
end
else begin
MoveTo(0,tmp.height div 3);
Lineto(tmp.width div 2,2*tmp.height div 3);
LineTo(tmp.width,tmp.height div 3);
Moveto(tmp.width div 2,2*tmp.height div 3);
Lineto(tmp.width div 2,tmp.height-14);
Moveto(0,tmp.height-14);
Lineto(tmp.width,tmp.height-14);
if MP.Cell[y1,y2,x].WithSymb then s:='П'
else s:='Д';
TextOut(tmp.Width-(TextWidth(s)+drx),
tmp.Height-(TextHeight(s)+dry)-14,s);
s:='S'+inttostr(TC.NextState);
TextOut(drx,tmp.Height-(TextHeight(s)+dry)-12,s);
s:=editing.cbWhatDo.Items[tc.mag];
if length(s)>1 then s:=copy(editing.cbWhatDo.Items[tc.mag],1,3)+'.';
TextOut((tmp.Width-(TextWidth(s)))div 2,dry+TextHeight(s),s);
s:=tc.Pushing;
TextOut((tmp.Width-(TextWidth(s)))div 2,dry,s);
D:=tc.Vihod;
TextOut((tmp.Width-TextWidth(D)) div 2,tmp.Height-14,D);
end;
end;
end;
end;
end;
dgMp.canvas.CopyRect(Rect,tmp.canvas,a);
end;
end;
procedure TMainPr.alRepaintExecute(Sender: TObject);
begin
if ready then begin
dgMP.Hide;
dgMp.Show;
end;
end;
procedure TMainPr.dgMPTopLeftChanged(Sender: TObject);
begin
PaintMP;
end;
procedure TMainPr.dgMPSelectCell(Sender: TObject; ACol, ARow: Integer;
var CanSelect: Boolean);
var x,y,y1,y2:word;
Mr:integer;
begin
if not StepOver and Ready then begin
x:=Acol-1;
y:=ARow;
with mp.params do begin
if y mod MagSymbNum = 0 then
y1:=y div MagSymbNum
else y1:=(y div MagSymbNum)+1;
if y mod MagSymbNum = 0 then
y2:=MagSymbNum
else y2:=y mod MagSymbNum;
if (x>0) and (x<=SymbNum) and (Arow>0) then begin
ii:=y1;
jj:=y2;
kk:=x;
cbStEd.ItemIndex:=y1;
cbMagStEd.ItemIndex:=y2;
cbSymbEd.ItemIndex:=x;
cbStEd.text:=cbStEd.items[y1];
cbMagStEd.text:=cbMagStEd.items[y2];
cbSymbEd.text:=cbSymbEd.items[x];
Mr:=Editing.ShowModal;
if mr=111 then begin
mp.cell[ii,jj,kk]:=Result;
PaintMP;
end;
end
else
if (y>0) and (x=SymbNum+1) then begin
changeGood(y1,y2);
if pc1.ActivePageIndex=0 then begin
tsAdd.Hide;
tsAdd.Show;
end;
end;
end;
end;
end;
procedure TMainPr.ChangeGood(i, j: integer);
begin
if MessageDlg('Выдействительно хотите изменить состояние ячейки',mtConfirmation,[mbOk,mbCancel],0)=mrOk
then mp.SetGood(i,j);
PaintMP;
end;
procedure TMainPr.alSaveExecute(Sender: TObject);
var tmp:Shortstring;
begin
if ready then begin
TMP:= mmNotes.text;
sd1.initialdir:=initialdir+SaveDir;
if sd1.execute then begin
mp.savetofile(tmp,sd1.filename);
end;
end;
end;
procedure TMainPr.alLoadExecute(Sender: TObject);
label 1;
var c:integer;
note:string;
begin
od1.initialdir:=initialdir+savedir;
if ready then begin
c:=MessageDlg('Сохранить текущий МП-транслятор?',mtConfirmation,[mbYes,mbNo,mbCancel],0);
case c of
mrYes: begin
alSaveExecute(Sender);
end;
mrNo: begin
;
end;
mrCancel: begin
goto 1;
end;
end;
end;
if od1.Execute then begin
pc1.Enabled:=true;
Ready:=true;
MP:=TMPRasp.Create;
MP.LoadFromFile(od1.FileName,note);
mmNotes.text:=note;
plChain.Text:='';
tsAdd.Hide;
tsAdd.show;
tsEdit.Hide;
tsEdit.show;
tsCheck.hide;
tsCheck.show;
DrawSt:=true;
DrawMg:=true;
DrawSmb:=true;
TMP:=TBitmap.create;
dgMP.DefaultColWidth:=CellSize;
dgMP.DefaultRowHeight:=CellSize;
paintMP;
end;
1: end;
procedure TMainPr.FormCreate(Sender: TObject);
var s:string;
i:integer;
begin
Application.Title:='ОДМ. МП-транслятор';
s:=paramstr(0);
i:=length(s);
while s[i]<>'\' do
i:=i-1;
initialdir:=copy(s,1,i);
end;
procedure TMainPr.buStopTraceClick(Sender: TObject);
begin
if ready then begin
tsEdit.enabled:=true;
bucheck.Enabled:=true;
buSymbAdd.Enabled:=true;
buDelSymb.Enabled:=true;
buClear.Enabled:=true;
buNextStep.Enabled:=False;
buStopTrace.Enabled:=False;
plChain.enabled:=true;
StepOver:=False;
MP.Params:=TempParams.Params;
MP.Good:=TempParams.Good;
MP.cell:=TempParams.Cell;
if TraceResult then lbResult.caption:='ДОПУСК'
else lbResult.caption:='НЕТ ДОПУСКА';
PaintMP;
end;
end;
procedure TMainPr.FormResize(Sender: TObject);
begin
PaintMp;
end;
procedure TMainPr.SetTrace;
var i:integer;
s:string;
begin
plStData.caption:=MP.Stack.Data;
lbStep.Items.clear;
for i:=1 to Num1 do begin
case i of
1: begin
s:=inttostr(SymbI);
end;
2: begin
if SymbI>Length(Chain) then s:=LineEnd
else s:=Mp.Params.Symbols[ss];
end;
3: begin
s:='S'+inttostr(St);
end;
4: begin
s:=MP.Stack.Top;
end;
end;
lbStep.Items.Add(TracePar[i]+s);
end;
end;
procedure TMainPr.Step;
begin
With mp do begin
if (State<>Err) and (SymbI<=Length(Chain)) then begin
Ss:=SymbPos(Chain[SymbI]);
if Ss>0 then begin
tt:=MagSymbPos(Stack.Top);
St:=State;
With Cell[St,Tt,Ss] do begin
SetMag(Mag,Pushing);
State:=NextState;
if WithSymb then SymbI:=SymbI+1;
end;
Ss:=SymbPos(Chain[SymbI]);
tt:=MagSymbPos(Stack.Top);
St:=State;
end
Else State:=Err;
end;
If (State<>Err) and (SymbI=Length(Chain)+1) then begin
tt:=MagSymbPos(Stack.Top);
TraceResult:=Good[State,tt];
buNextStep.Enabled:=False;
end
else if State=Err then begin
lbResult.caption:='НЕТ ДОПУСКА';
buNextStep.Enabled:=False;
end;
end;
end;
procedure TMainPr.buNextStepClick(Sender: TObject);
var s:string;
begin
Step;
SetTrace;
PaintMp;
if buNextStep.Enabled=False then begin
if TraceResult then
s:='ДОПУСК '
else
s:='НЕТ ДОПУСКА';
MessageDlg(s+' цепочки',mtinformation,[mbOk],0);
lbResult.Caption:=S;
end;
end;
procedure TMainPr.alExitExecute(Sender: TObject);
begin
MainPr.Close;
end;
procedure TMainPr.alHelpExecute(Sender: TObject);
begin
Application.HelpCommand(HELP_finder,0);
end;
procedure TMainPr.N5Click(Sender: TObject);
begin
About.ShowModal;
end;
procedure TMainPr.Button1Click(Sender: TObject);
var MR:word;
begin
if ready then begin
with rgWhatAdd do begin
case ItemIndex of
0: begin WhatAdd:=St; Send:=''; end;
1: begin WhatAdd:=MgS; Send:=Mp.Params.MagSymbols; end;
2: begin WhatAdd:=Smb; Send:=Mp.Params.Symbols; end;
end;
end;
MR:=Adding.ShowModal;
if MR=100 then begin
with rgWhatAdd do begin
case ItemIndex of
0: begin
if not mp.AddState
then MessageDlg('Невозможно добавить новое состояние!'
,mtWarning,[mbOk],0);
DrawSt:=True;
end;
1: begin
if not mp.AddMagState(res)
then MessageDlg('Невозможно добавить новый магазинный символ!'
,mtWarning,[mbOk],0);
DrawMg:=True;
end;
2: begin
if not mp.AddSymb(res)
then MessageDlg('Невозможно добавить новый символ!'
,mtWarning,[mbOk],0);
DrawSmb:=True;
end;
end;
PaintMp;
end;
end;
tsEdit.Hide;
tsEdit.Show;
end;
end;
end.
РЕФЕРАТ
Курсовая работа по дисциплине «Основы дискретной математики» на тему: «Программа – конструктор для построения МП – транслятора по его параметрам с последующей проверкой задаваемых пользователем цепочек»
В работе рассмотрен вопрос построения автоматов-трансляторов с магазинной памятью, проверкой задаваемых цепочек. Программу можно использовать в учебных целях, для построения автоматов с последующим использованием созданных файлов в других приложениях, создаваемых с помощью среды программирования Delphi.
Работа посвящена изучению такого раздела дискретной математики, как автоматы-трансляторы с магазинной памятью. На основе полученных знаний разработан программный продукт, реализующий построение МП-транслятора путем задания управляющей таблицы.
При работе приложение позволяет пользователю построить транслятор. Затем пользователь может выполнить проверку цепочки. Если пользователь изучит теоретический материал, то работа не вызовет большого затруднения. Теоретический материал излагается ниже в записке, а также в реализованной справочной службы программы. Работа программного продукта реализована достаточно наглядно, что делает его пригодным для использования его в целях более качественного обучения студентов по указанному выше разделу дискретной математики.
Ключевые слова:
дискретная математика, МП-транслятор, управляющая таблица, входная цепочка, выходная цепочка.
Введение
В настоящее время компьютеры все чаще используются не только для обработки данных и уточнения параметров моделей, но и для постановки компьютерного эксперимента, во многих случаях призванного заменить дорогостоящий натурный эксперимент. Поэтому дальнейшее развитие математического моделирования связано с применением современных средств компьютерной математики как инструмента подготовки высококвалифицированных специалистов, построения содержательных моделей, накопления и хранения информации, полученной в результате исследования этих моделей, т.е. с разработкой новых информационных технологий для образования и научных исследований.
Развитие научно-технического прогресса ведет к росту потребности в технических, математических и иных расчетах, в соответствующих программных продуктах. Не последнее место в научных исследованиях занимает математическое моделирование с применением информационных технологий. В электротехнике и электронике широко используют MathCAD для проектирования всевозможные процессов, импульсов, сигналов.
Также математическое моделирование используется в металлургических направлениях. В частности в ДГМА производится математическое моделирование горячей и холодной прокатки на языке PASCAL. Производится математическое моделирование процесса переворачивания сталеразливочных ковшей, расчет механических свойств разных металлов и сплавов в условиях холодной деформации, анализ влияния выходных параметров процесса холодной прокатки на величину основных энергосиловых параметров.
В связи с широким распространением быстродействующих электронно-вычислительных машин главной задачей математического моделирования стала задача обеспечения интерактивности взаимодействия исследователя с моделируемым объектом, в том числе, в реальном времени. В научных исследованиях это сводится к определению архитектуры и состава программно аппаратных средств интерфейса пользователя, предварительной обработке исходных данных с учетом их амплитуды, частотных и временных характеристик, идентификации, прогнозированию и управлению, исследуемым объектом. Научные достижения включают методики разработки инструментальных средств и ряд алгоритмов для обеспечения человеко-машинного интерфейса, предварительной обработки данных и идентификации нелинейных динамических систем, визуализации полученных результатов.
Реферат
Дискретная математика – раздел математики, занимающийся изучением свойств объектов конечного характера.
Дискретная математика включает в себя такие разделы как множества, алгебра высказываний, теория конечных автоматов, теория графов.
В этой курсовой работе будет предпринята попытка раскрыть как можно шире понятие автоматов-трансляторов с магазинной памятью.
Delphi является одним из наиболее быстрых средств для реализации поставленной задачи (написание кода программы и визуальное создание вида программы занимают очень короткий промежуток времени по сравнению с другими языками).
Однако основная ценность приложения – алгоритмическая поддержка. С одной стороны разработка качественного интерфейса заметно облегчается при использовании сред визуального программирования, а с другой стороны для разработки завершенных корректных приложений необходима теоретическая база.
При разработке программного продукта использовалась интегрированная среда Delphi 6.
Теоретические и практические основы разрабатываемой темы
Теория конечных автоматов
Конечный автомат(в дальнейшем КА) - абстрактное вычислительное устройство с фиксированным и конечным объемом памяти, которое на входе читает цепочки(последовательности символов некоторого алфавита), а на выходе сообщает об их принадлежности к некоторому множеству, для распознания которого он построен.
По сути КА работает как фильтр, который пропускает "правильные" цепочки. Другая трактовка КА - компактный алгоритм распознания регулярных, в том числе и бесконечных множеств, который строит программист перед началом кодирования (реализацией алгоритма на конкретном языке).
Далеко не для всех регулярных множеств можно построить
КА-распознаватель, так как КА не имеет возможности сосчитать и запомнить количество символов обрабатываемой цепочки. Для этой цели используется специальное устройство - магазин, в который можно помещать символы или удалять их, запоминая или сравнивая количество символов входной цепочки. Такой автомат называется автоматом распознавателем с магазинной памятью (сокращенно – МП-распознавателем).
Но в ряде случаев при обработке регулярного множества необходимо его преобразование в другое множество. Такие действия может выполнять МП-транслятор, на выходе которого будет формироваться выходная цепочка.
МП-транслятор задается:
1.Конечным множеством входных символов (включая символ конца цепочки "¶").
2.Конечным множеством выходных символов.
3.Конечным множеством магазинных символов (включая маркер дна магазина - '¤').
4.Конечным множеством состояний.
5.Упpавляющей таблицей, котоpая каждой комбинации трех параметров: входной символ, магазинный символ(верхний символ магазина), состояние - ставит в соответствие четыре параметра: действие с магазином, входным символом, состоянием и выходным символом.
5.Hачальной конфигурацией (начальное состояние и начальное содеpжимое магазина).
6.Множеством допускающих конфигураций (комбинаций - состояние МП-транслятора и верхний символ магазина в момент, когда приходит символ "конец цепочки").
Допускаемые операции над входом:
1.Держать входной символ (Д).
2.Перейти к очередному символу (П).
Примечание: запрещено запрашивать входной символ после прихода символа "¶"("конец цепочки").
Допускаемые операции над магазином
1.Втолкнуть в магазин магазинный символ, к примеру А (Вт.А).
2.Вытолкнуть из магазина верхний символ, к примеру А (Выт.А).
3.Оставить магазин без изменений (О).
Ряд ячеек управляющей таблицы может без деления на поля заполняться символом Е (состояние ошибки). Если МП-транслятор попал в такое состояние, то обработка цепочки прекращается и такая цепочка отвергается.
Результатом работы для МП-транслятора будет сообщение "допустить" или "отвергнуть" и цепочка получаемая на выходе. Входная цепочка допускается МП-транслятором, если под воздействием этой цепочки автомат, начавший работу в начальной конфигурации (в начальном состоянии и с начальным содержимым магазина) приходит к допускающей конфигурации после поступления символа "конец цепочки", иначе цепочка отвергается.
Рассмотрим строение ячейки в таблице переходов МП-транслятора.
Рис. 1 – вид ячейки МП-транслятора
Построение МП-транслятора для распознания заданного множества цепочек - процесс творческий и неоднозначный. Теоретически для распознания одного и того же множества цепочек можно построить бесконечное множество КА. Описанный выше принцип распознания применим далеко не ко всякому регулярному множеству.
Эмиссия газов от очистных сооружений канализации: В последние годы внимание мирового сообщества сосредоточено на экологических проблемах...
Механическое удерживание земляных масс: Механическое удерживание земляных масс на склоне обеспечивают контрфорсными сооружениями различных конструкций...
История развития пистолетов-пулеметов: Предпосылкой для возникновения пистолетов-пулеметов послужила давняя тенденция тяготения винтовок...
Кормораздатчик мобильный электрифицированный: схема и процесс работы устройства...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!