Форум программистов, компьютерный форум, киберфорум
Delphi для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.62/21: Рейтинг темы: голосов - 21, средняя оценка - 4.62
 Аватар для Borstch
2 / 2 / 0
Регистрация: 04.10.2013
Сообщений: 15

Конечный автомат для нулей и единиц

06.10.2013, 08:10. Показов 4567. Ответов 14
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Доброго времени суток.
Посоветуйте, что не так?

Имеется задача простроения конечного автомата для цепочек из нулей и единиц. При этом условие -
за каждым вхождением пары единиц следует нуль. Ну и ещё одним условием является то, что при реализации необходимо использовать таблицу переходов и двумерный массив. А не "условия IF".

Взялся реализовать на Delphi.

Delphi
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
unit Unit1;
 
interface
 
uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, Grids, StdCtrls, ComCtrls, ExtCtrls;
 
type
  TForm1 = class(TForm)
    Label1: TLabel;
    Label2: TLabel;
    Button1: TButton;
    Grid1: TStringGrid;
    Label6: TLabel;
    Edit1: TEdit;
    Label8: TLabel;
    Memo2: TMemo;
    Label9: TLabel;
    Image1: TImage;
    Image3: TImage;
    procedure FormCreate(Sender: TObject);
    procedure Button1Click(Sender: TObject);
    procedure Edit1KeyPress(Sender: TObject; var Key: Char);
 
    procedure PM(Grid: TStringGrid; Edit: TEdit; Memo: TMemo; Labele :TLabel);
  private
    { Private declarations }
  public
    { Public declarations }
  end;
 
var
  Form1: TForm1;
implementation
 
{$R *.dfm}
 
procedure TForm1.FormCreate(Sender: TObject);
var i, j: integer;
begin
// Заполнение таблицы переходов
  for i:= 1 to 2 do
   for j:= 1 to 3 do
    Grid1.Cells[i,j]:='*';
  Grid1.Cells[1,0]:= '0';
  Grid1.Cells[2,0]:= '1';
  Grid1.Cells[0,1]:= '0';
  Grid1.Cells[0,2]:= '1';
  Grid1.Cells[0,3]:= '11';
  Grid1.Cells[0,4]:= '0';
  Grid1.Cells[2,2]:= '3';
  Grid1.Cells[1,3]:= '1';
  Grid1.Cells[1,1]:= '1';
  Grid1.Cells[2,1]:= '2';
 
end;
 
procedure TForm1.Button1Click(Sender: TObject);
begin
  Close;
end;
 
procedure TForm1.PM(Grid: TStringGrid; Edit: TEdit; Memo: TMemo; Labele :TLabel);
var i, j, P_1, P_2: integer;
    S: string;
begin
  Memo.Clear;
  P_1:= 1;
  for i:= 1 to Length(Edit.Text) do
   begin
     S:= Copy(Edit.Text,i,1);
     for j:= 1 to Grid.ColCount do
      if (S = Grid.Cells[j,0]) then
       begin
         if (Grid.Cells[j,P_1] <> '*') then
          begin
            P_2:= StrToInt(Grid.Cells[j,P_1]);
            Labele.Caption:= 'Цепочки принята';
            Memo.Lines.Add(IntToStr(i)+': из  позиции '+IntToStr(P_1)+' в позицию '+IntToStr(P_2));
            P_1:= P_2;
          end
         else
          begin
            Labele.Caption:= 'Цепочка не принята! ВВедите корректную цепочку';
            Memo.Clear;
            Exit;
          end;
       end;
   end;
end;
 
procedure TForm1.Edit1KeyPress(Sender: TObject; var Key: Char);
begin
  if (Key = '0')or(Key = '1')or(Key=Chr(vk_Back)) then Edit1.ReadOnly:=False
   else Edit1.ReadOnly:=True;
  if (Key = #13) then PM(Grid1,Edit1,Memo2,Label9);
end;
 
 
end.
Интерфейс выглядит так
[img]http://i.**********/srSmcOu.png[/img]


Вроде работает, но не воспринимает цепочку, если в ней после нуля есть одна единица. Т.е. на запись "01" ругается, а на запись "011" - всё отлично. В чем может быть причина? Опыта построения Конечных автоматов до этого не имел, может чего упустил из виду? Может кто-нибудь помочь? Два дня бьюсь, не пойму в чем причина. Точнее почему "011" принимает, а "01" не желает.
0
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
06.10.2013, 08:10
Ответы с готовыми решениями:

Задать конечный автомат, преобразующий строку из нулей и единиц
Σ=Σ’={0;1}. На входной ленте записана произвольная последовательность из нулей и единиц. После каждой входной комбинации «01» следующие 3...

Построить конечный автомат, распознающий среди цепочек из нулей и единиц такие, где на каждом третьем месте 0
Доброго времени суток! Помогите, пожалуйста, с решением задачи, а то совсем никак -_- Постройте конечный автомат, распознающий среди...

Поиск числа с максимальным количеством нулей (конечный автомат)
Здравствуйте ребята. Вообщем суть такова: Создать программу, которая позволяет пользователю выбрать текстовый файл. Пусть текст содержит...

14
Заблокирован
06.10.2013, 11:54
Тяк.... Для начала
Перменную S лучше сделать типом Char поскольку она представляет единственный символ.
S:= Copy(Edit.Text,i,1);
Так не надо... Строка - Это массив символов. Зачем воротить такую функцию как Copy? Если бы вы резали несколько символов... А так... S:= Edit.Text[i];
Глянем дальше...
Значит как я понял, цепочку вы вводите сами, а прога проверяет её на корректность?

Добавлено через 19 минут
а таблица эта зачем? Вообще бред какой-то понятный только вам.
Если вам нужно сравнение через таблицу.. то
единственное условие правильности цепочки - что после 11 должен быть 0
То есть у вас получается проверка на триплет 110, и другие возможные сочетания
а возможны все сочетания кроме 111
вот и таблица
000
001
010
011
100
101
110

И далее

Из строки проверяем сначала на её длину.
Проверка начнётся, если символов больше или равно 3, то есть есть триплеты.
И нам нужно проверять только триплеты, а оставшийся хвост - игнорировать.
Для этого достаточно длину строки Len div 3
Получаем количество шагов цикла проверки
И тогда уже сканируем строку, вырезая из неё триплеты и сравнивая с триплетами таблицы.
S:= Copy(Edit.Text,i,3); Вот теперь S - string

Добавлено через 8 минут
Скажем таблица - массив m_
Тогда
Delphi
1
2
3
4
5
6
7
8
cor:=false;//Корректность строки. 
for i1= 0 to 6 do begin
                        if S = m[i1] then begin
                                                 cor:=true;//Цепочка корректна
                                                 break;//Останавливаем проверку
                                               end;
                       end; 
//Если корректная цепочка не найдена, то cor так и останется  false
Добавлено через 9 минут
Правда есть один нюанс... если срока завершена, нужно проверить последний треплет.
То есть вырезать последние три символа и проверить на m[3] то есть сочетание 011 по условию, после него должен быть 0, но если конец строки, то нуля нет и строка не корректна.

Добавлено через 13 минут
И вообще накатаю я вам пример.. а то нифига в моём бреде не разберёте.

Добавлено через 33 минуты
И вообще.. пошлите того кто даёт такие задания подальше. не нужно здесь никакой таблицы..
А если с таблицей, то это один одномерный массив с двумя элементами.
Хотя если воспользоваться IF без таблицы на проверку одного единственного некорректного триплета, то это не нарушает условия, поскольку проверяется не переход.
1
Заблокирован
06.10.2013, 13:50
Не знаю как с вашими условиями, но цепочки все корректные.
Вот
Вложения
Тип файла: rar FF.rar (172.6 Кб, 25 просмотров)
1
 Аватар для Borstch
2 / 2 / 0
Регистрация: 04.10.2013
Сообщений: 15
09.10.2013, 08:45  [ТС]
Lirrk,
Благодарю за ответы!
Извиняюсь, пропал "по-английски", не мог ответить, были проблемы с сетью.
Про переменную S сделать Char - спасибо, как-то я не догадался.
Думал, что коль вводим строку, то сразу её и считывать надо строкой.

Да, всё верно, я ввожу цепочку символов, например, 011000011011 , и программа показывает (в виде лога) переходы, так, как если бы это происходило на графе.
Например на таком графе (пример из методички).

таблица переходов такая

Круги - этот состояния, а маленькие латинские буквы - переменные/входные символы.
Состояние E - это, как я понимаю, состояние для исключения ситуации, из которых нет переходов по входным символам.

И да, почему триплет? В моём случае переменных всего две - ноль и единица. Следовательно, в таблице должно быть 2 столбца. Первый столбец я использовал для себя (для нумерации).

Добавлено через 14 минут
Lirrk,
Суть задания как раз в том, чтобы показать переходы Конечного Автомата из одного состояния в другое. И чтобы за каждым вхождением пары единиц следовал нуль. Но чтобы не грузить студентов рисованием графов, обозначено было создать таблицу переходов. Ёё примерная работа показана в моём варианте. Т.е. скормили цепочку вида 0100 - и поехало: Было состояние А, получили НОЛЬ, перешли в стостояние, например, Б, получили ОДИН, перешли в А, получили НОЛЬ, перешли из А в Б, получили опять НОЛЬ, перешли из Б в В, и т.д.

[offtop] Про послать подальше - боюсь Вас огорчить) Мне этоу преподавателю ещё сдавать лабы вот по этой красоте
Благо она работает под win7 [/offtop]
0
Заблокирован
09.10.2013, 10:44
Borstch,
треплет по той простой причине, что у вас в условии поставлено исключение 111. Поскольку все остальные сочетания из трёх - правильные. то следует проверять на это сочетание. Вы очевидно не поняли этого момента.
Я исхожу не из тупой методички, а из оптимального алгоритма. Если у вас тема именно по графам, то и задание должно быть соответствующим. Именно это и есть профессиональный подход. А ваши тупые задания да ещё с идиотскими подсказками, делают не специалистов а идиотов.

Borstch,
Кстати по вашему графу. ABCDE Это состояния. XYZ Это и есть триплет.
Тут идёт показ через какие состояния проходят элементы триплета.
0
 Аватар для Borstch
2 / 2 / 0
Регистрация: 04.10.2013
Сообщений: 15
09.10.2013, 13:33  [ТС]
Lirrk,
Да, я не понял того момента про триплеты. Сейчас он стал понятен. Т.е. мы ищем треплет из трех единиц. Если он существует в цепочке - цепочка не принимается.
Алгоритм хороший. Но с переходами как это увязать?
Как показать через какие состояния проходят элементы триплета?
"Из позиции А в позицию Б, оттуда в С, оттуда..."
В моей хромой реализации это худо бедно отображалось в виде текста справа (как и требует преподаватель), но у меня было посимвольно, а не треплетами.

Соглашаюсь с критикой процесса обучения, ибо тема не по графам (не умеем), а просто по Конечным Автоматам, дано на самостоятельное изучение и подразумевается, что программирование мы знаем. Можно считать это "ненормальным программированием".

Я рассуждал иначе:
Переменных всего две - Ноль и Единица. В примере три переменных - X,Y,Z , а у меня всего две - ноль и единица. Значит в таблице переходов будет 2 столбца.
0
Заблокирован
09.10.2013, 15:25
Цитата Сообщение от Borstch Посмотреть сообщение
Lirrk,
Соглашаюсь с критикой процесса обучения, ибо тема не по графам (не умеем), а просто по Конечным Автоматам,
Хм... вполне резонно. Не разбираешься в этих автоматах, пойдёшь разбирать АКМ.
Можно подумать они сами в этом что-то понимают. В теории автоматов...
0
 Аватар для Borstch
2 / 2 / 0
Регистрация: 04.10.2013
Сообщений: 15
09.10.2013, 16:02  [ТС]
Lirrk,
Эм... Как бы сказать, предмет-то не "Теория автоматов", а "Системное программное обеспечение".
0
Заблокирован
09.10.2013, 16:40
Цитата Сообщение от Borstch Посмотреть сообщение
Lirrk,
Эм... Как бы сказать, предмет-то не "Теория автоматов", а "Системное программное обеспечение".
1
 Аватар для Borstch
2 / 2 / 0
Регистрация: 04.10.2013
Сообщений: 15
09.10.2013, 17:31  [ТС]
Lirrk,
Ну как бы компиляторы, трансляторы и иже с ними относятся к системному ПО, а там грамматика, а там и автоматы, слово за слово, и пришли к этой лабе.
Так всё таки, если абстрагироваться, выйти из шока, и на время вновь "поверить в человечество". Может у вас будут идеи? Как сделать "плохо", не эффективно, но с таблицей переходов? Я не могу понять, почему моя программа не принимает цепочку вида "01".
Выложил весь архив, 900 килобайт.
Borstch_KonecAvtomat.rar
0
Заблокирован
09.10.2013, 18:24
Borstch,
Я особо не врубался. Но это из-за звёздочки в таблице в том месте.
Или у вас таблица не так составлена, или столбцы со строками перепутаны. Где-то здесь нужно копать.
И вообще.. у вас там в одном месте 11, а сравниваете одиночные символы всё время. Откуда 11 там возмётся?
0
 Аватар для Borstch
2 / 2 / 0
Регистрация: 04.10.2013
Сообщений: 15
10.10.2013, 10:45  [ТС]
Lirrk,
это не одиннадцать, это 3. Порядковый номер строки.
Т.е. я пронумеровал так.
Вместо 0, 1, 2,
Я написал 0, 1, 11,
0
2838 / 1647 / 254
Регистрация: 03.12.2007
Сообщений: 4,222
10.10.2013, 12:02
В общем, должно быть как-то так:

Code
1
2
3
4
5
6
7
8
9
transitions = [
    {'*': 0, '1': 1},
    {'*': 0, '1': 2},
    {'0': 0, '*': 3},
    {'*': 3}
    ]
for c in (string + '*')
    curState = transitions[curState][c] ?? transitions[curState]['*']
good = curState != transitions.length - 1
0
 Аватар для Borstch
2 / 2 / 0
Регистрация: 04.10.2013
Сообщений: 15
10.10.2013, 18:19  [ТС]
Задание выполнено.Завтра приведу код.
0
 Аватар для Borstch
2 / 2 / 0
Регистрация: 04.10.2013
Сообщений: 15
14.10.2013, 17:23  [ТС]
Задание 1:
Построить конечный автомат для следующих видов цепочек, состоящих из нулей и единиц.
Вариант 2 - за каждым вхождением пары единиц следует нуль.

Задание 2:
Построить конечный автомат, распознающий зарезервированные слова языка С++:
Вариант 2 - continue, class, const

Решение в приложенных ниже файлах. Спасибо за помощь.
Вложения
Тип файла: zip KA_1.zip (1,008.0 Кб, 64 просмотров)
Тип файла: zip KA_2.zip (315.2 Кб, 45 просмотров)
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
14.10.2013, 17:23
Помогаю со студенческими работами здесь

Конечный автомат для строк
Конечный автомат для строк используя switch. Помогите пожалуйста...

Конечный автомат для языка
Необходимо определить КА для языка L = {bnabm|n,m&gt;0} и удалить из него лямбда переходы. Правильно ли я понимаю, что здесь лямбда...

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

Конечный автомат для разбора математических выражений
Написал конечный автомат для разбора математических выражений вида 2*5 - 10/(5-3)*(2)+1 . Мне нужно добавить в него функции вида...

Построить конечный автомат для распознания регулярного множества цепочек трехсимвольного алфавита
Построить конечный автомат (КА–распознаватель) для распознания регулярного множества цепочек трехсимвольного алфавита в соответствии с...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
15
Ответ Создать тему
Новые блоги и статьи
Символьное дифференцирование
igorrr37 13.02.2026
/ * Логарифм записывается как: (x-2)log(x^2+2) - означает логарифм (x^2+2) по основанию (x-2). Унарный минус обозначается как ! в-строка - входное арифметическое выражение в инфиксной(обычной). . .
Камера Toupcam IUA500KMA
Eddy_Em 12.02.2026
Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
И ясному Солнцу
zbw 12.02.2026
И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.
«Знание-Сила»
zbw 12.02.2026
«Знание-Сила» «Время-Деньги» «Деньги -Пуля»
SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров
8Observer8 12.02.2026
Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .
SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image)
8Observer8 11.02.2026
Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .
SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image
8Observer8 10.02.2026
Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .
Установка Qt-версии Lazarus IDE в Debian Trixie Xfce
volvo 10.02.2026
В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru