Теория вычислительных процессов

гр. ПСз-1-09, факультет Управления и информационных технологий

Э.К. Насыров

Челябинск

2013

Практические задачи

Задачи должны быть выполнены в Delphi. Решение задачи должно начинаться с построения математической модели. После чего должен быть представлен листинг программы и спецификация. Каждая задача должна сопровождаться необходимым количеством комментариев и содержать результаты выполнения программы. По каждой задаче должны быть составлены стандартные схемы программы и построена сеть Петри.

Вариант 3.

1. Постройте одноленточный автомат над алфавитом {a, b, c}, допускающий следующие множества слов: {anbbb | n 0}, {ancbm | n 1, m 1}.

Математическая модель:

A=({a,b,c},-алфавит терминальных символов;

{q0,q1,q2,q3,q4,q5,q6},-множество состояний;

{q0a>q1 | q0b>q2 | q1a>q1 | q1b>q2 | q1c>q3 | q2b>q4 | q3b>q5 | q4b>q6 | q5b>q5 | q5#>q6},-множество переходов;

q0,-начальное состояние;

q6}-конечное состояние.

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

Сеть Петри.

программа символ сеть петри

В роли "полочек" или устройства выбирающего направление - выступает оператор.

Программа написана на Delphi 6, как приложение консоль.

1. program Project1;

2.

3. {$APPTYPE CONSOLE}

4.

5. uses

6. SysUtils;

7. var

8. State:integer;

9. CurrentABC:string;

10. CurrentJob:string;

11. CurrentTerm:char;

12.

13. {Рекурсивная процедура преобразования строки}

14. function str2line(a:string):string;

15. begin{str2line}

16. if length(a)>1{условие выхода из рекурсии}

17. then result:=a[1]+','+str2line(copy(a,2,length(a))){вставляем запятую после каждой буквы}

18. else result:=a[1];{единственная буква - копируем}

19. end;{str2line}

20.

21. {вводим терминальный символ допустимого алфавита}

22. function LoadTerm(term_ABC:string;c:integer):char;

23. var

24. d:string;

25. begin{LoadTerm}

26. repeat

27. {выводим сообщение о состоянии и допустимых терминальных символах}

28. write('State ',c,'. Please enter the characters(',str2line(term_ABC),'):');

29. {вводи терминальный символ}

30. readln(d);

31. if pos(d[1],term_ABC)=0 then writeln('Error! Expected characters: ',str2line(term_ABC)){сообщение об ошибке ввода}

32. until pos(d[1],term_ABC)>0;{выходим если введенный символ есть в допустимом алфавите алфавите}

33. result:=d[1];{сохраняем результат работы}

34. end;{LoadTerm}

35.

36. begin

37. {начальная установка параметров}

38. State:=0;{начальное состояние автомата}

39. CurrentABC:='ab';{допустимый алфавит}

40. CurrentJob:='';{результат работы автомата}

41. {начало работы конечного автомата}

42. repeat

43. CurrentTerm:=LoadTerm(CurrentABC,State);{вводим терминальный символ}

44. CurrentJob:=CurrentJob+CurrentTerm;{добавляем его в результат работы}

45. {конечный автомат-контроль и изменение состояний}

46. case State of

47. 0:case CurrentTerm of

48. 'a':begin

49. State:=1;{переводим автомат в состояние 1}

50. CurrentABC:='abc';{изменяем допустимый алфавит}

51. end;

52. 'b':begin

53. State:=2;{переводим автомат в состояние2}

54. CurrentABC:='b';{изменяем допустимый алфавит}

55. end;

56. end;{case CurrentTerm of}

57. {state=0}

58. 1:case CurrentTerm of

59. 'b':begin

60. State:=2;{перводим автомат в состояние 2}

61. CurrentABC:='b';{изменяем допустимый алфавит}

62. end;

63. 'c':begin

64. State:=3;{переводим автомат в состояние 3}

65. CurrentABC:='b';{изменяем допустимый алфавит}

66. end;

67. end;{case CurrentTerm of}

68. {state=1}

69. 2:State:=4;{переводим автомат в состояние 4}

70. {state=2}

71. 3:begin

72. State:=5;{переводи автомат в состояние 5}

73. CurrentABC:='b#';{изменяем допустимый алфавит}

74. end;

75. {state=3}

76. 4:State:=6;{переводим автомат в режим окончания работы}

77. {state=4}

78. 5:if CurrentTerm='#' then State:=6;{проверяем окончание работы автомата}

79. {state=5}

80. end;{case state of}

81. until State=6;

82. if pos('#',CurrentJob)>0 then delete(CurrentJob,pos('#',CurrentJob),1);{удаляем символ окончания работы}

83. Writeln('Result: ',CurrentJob);{вывод результата работы}

84. Readln(CurrentJob);{ожитания наджатия клавиши ВВОД}

85. end.

Программа реализует оба множества последовательностей (anbbb, где n=0,1,2,... и ancbm, где n,m=1,2,3,...)

При попытке ввести неверный символ выдается ошибка и ввод повторяется.

Литература

Основная

1. Бройдо В.Л. Вычислительные системы, сети телекоммуникации. - СПб.: Питер, 2005. - 568 с.

2. Мелехин В.Ф. Вычислительные машины, системы и сети. - М.: Академия, 2006. - 560 с.

3. Пятибратов А.П. Вычислительные системы, сети телекоммуникации. - М.: Финансы и статистика, 2005. - 470 с.

Дополнительная

1. Высшая математика / Под ред. Н.М. Кремера. - М.: ЮНИТИ - ДАНА, 2007

2. Дорофеева А.В. Высшая математика. - М.: Дрофа, 2003. - 384 с.: ил.

3. Хандадашева Л.Н. Программное обеспечение. Вычислительные сети. - Ростов н/Д.: МарТ, 2005. - 320 с.

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