|
2 / 2 / 0
Регистрация: 04.10.2013
Сообщений: 15
|
||||||
Конечный автомат для нулей и единиц06.10.2013, 08:10. Показов 4567. Ответов 14
Метки нет (Все метки)
Доброго времени суток.
Посоветуйте, что не так? Имеется задача простроения конечного автомата для цепочек из нулей и единиц. При этом условие - за каждым вхождением пары единиц следует нуль. Ну и ещё одним условием является то, что при реализации необходимо использовать таблицу переходов и двумерный массив. А не "условия IF". Взялся реализовать на Delphi.
Интерфейс выглядит так
[img]http://i.**********/srSmcOu.png[/img]
Вроде работает, но не воспринимает цепочку, если в ней после нуля есть одна единица. Т.е. на запись "01" ругается, а на запись "011" - всё отлично. В чем может быть причина? Опыта построения Конечных автоматов до этого не имел, может чего упустил из виду? Может кто-нибудь помочь? Два дня бьюсь, не пойму в чем причина. Точнее почему "011" принимает, а "01" не желает.
0
|
||||||
| 06.10.2013, 08:10 | |
|
Ответы с готовыми решениями:
14
Задать конечный автомат, преобразующий строку из нулей и единиц Построить конечный автомат, распознающий среди цепочек из нулей и единиц такие, где на каждом третьем месте 0 Поиск числа с максимальным количеством нулей (конечный автомат) |
|
Заблокирован
|
||||||
| 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_ Тогда
Правда есть один нюанс... если срока завершена, нужно проверить последний треплет. То есть вырезать последние три символа и проверить на m[3] то есть сочетание 011 по условию, после него должен быть 0, но если конец строки, то нуля нет и строка не корректна. Добавлено через 13 минут И вообще накатаю я вам пример.. а то нифига в моём бреде не разберёте. Добавлено через 33 минуты И вообще.. пошлите того кто даёт такие задания подальше. не нужно здесь никакой таблицы.. А если с таблицей, то это один одномерный массив с двумя элементами. Хотя если воспользоваться IF без таблицы на проверку одного единственного некорректного триплета, то это не нарушает условия, поскольку проверяется не переход.
1
|
||||||
|
Заблокирован
|
|
| 06.10.2013, 13:50 | |
|
Не знаю как с вашими условиями, но цепочки все корректные.
Вот
1
|
|
|
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
|
|
|
2 / 2 / 0
Регистрация: 04.10.2013
Сообщений: 15
|
|
| 09.10.2013, 13:33 [ТС] | |
|
Lirrk,
Да, я не понял того момента про триплеты. Сейчас он стал понятен. Т.е. мы ищем треплет из трех единиц. Если он существует в цепочке - цепочка не принимается. Алгоритм хороший. Но с переходами как это увязать? Как показать через какие состояния проходят элементы триплета? "Из позиции А в позицию Б, оттуда в С, оттуда..." В моей хромой реализации это худо бедно отображалось в виде текста справа (как и требует преподаватель), но у меня было посимвольно, а не треплетами. Соглашаюсь с критикой процесса обучения, ибо тема не по графам (не умеем), а просто по Конечным Автоматам, дано на самостоятельное изучение и подразумевается, что программирование мы знаем. Можно считать это "ненормальным программированием". Я рассуждал иначе: Переменных всего две - Ноль и Единица. В примере три переменных - X,Y,Z , а у меня всего две - ноль и единица. Значит в таблице переходов будет 2 столбца.
0
|
|
|
Заблокирован
|
||
| 09.10.2013, 15:25 | ||
|
Можно подумать они сами в этом что-то понимают. В теории автоматов...
0
|
||
|
2 / 2 / 0
Регистрация: 04.10.2013
Сообщений: 15
|
|
| 09.10.2013, 16:02 [ТС] | |
|
Lirrk,
Эм... Как бы сказать, предмет-то не "Теория автоматов", а "Системное программное обеспечение".
0
|
|
|
Заблокирован
|
|
| 09.10.2013, 16:40 | |
|
1
|
|
|
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
|
|
|
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 | ||||||
|
В общем, должно быть как-то так:
0
|
||||||
|
2 / 2 / 0
Регистрация: 04.10.2013
Сообщений: 15
|
|
| 10.10.2013, 18:19 [ТС] | |
|
Задание выполнено.Завтра приведу код.
0
|
|
|
2 / 2 / 0
Регистрация: 04.10.2013
Сообщений: 15
|
|
| 14.10.2013, 17:23 [ТС] | |
|
Задание 1:
Построить конечный автомат для следующих видов цепочек, состоящих из нулей и единиц. Вариант 2 - за каждым вхождением пары единиц следует нуль. Задание 2: Построить конечный автомат, распознающий зарезервированные слова языка С++: Вариант 2 - continue, class, const Решение в приложенных ниже файлах. Спасибо за помощь.
0
|
|
| 14.10.2013, 17:23 | |
|
Помогаю со студенческими работами здесь
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, то после закрытия окошка. . .
|