|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
03.10.2016, 16:17 | #1 |
Регистрация: 03.10.2016
Сообщений: 3
|
Машина Тьюринга. Проверка скобочной последовательности
Добрый день. Возникла такая задача - реализовать машину Тьюринга для проверки правильности скобочной последовательности. Описание мат. части:
Есть лента, скобочная последовательность ограничена символами А. Головка находится в самом левом положении. Работа машины: сначала ГЗЧ движется вправо до первой правой скобки, заменяет ее символом X, переходит в состояние q1 и движется влево до ближайшей левой скобки, заменяет ее символом X, переходит в состояние q0 , и челночное движение повторяется. Если машина, находясь в состоянии q1, достигает левого символа А, то печатает "0" и останавливается – скобочное выражение неправильно. Если машина, находясь в состоянии q0, достигает правого символа А, не обнаружив больше правой скобки, то переходит в заключительное состояние q2, связанное с движе- нием влево, и в последний раз просматривает последовательность: не осталась ли непар- ная левая скобка. Если по пути встретится левая скобка, то машина печатает "0" и оста- навливается. При достижении в состоянии q2 левого символа А, машина печатает "1" и останавливается – скобочное выражение правильное Опишу реализацию. Интерфейс Код:
Q0 Код:
Код:
Код:
Код:
Код:
Последний раз редактировалось ProOvenvan; 03.10.2016 в 16:25. |
06.10.2016, 14:10 | #2 |
personality
Старожил
Регистрация: 28.04.2009
Сообщений: 2,876
|
Вот кой чего исправил в коде и набросал заготовочку простенькую для тестирования автомата, а то вводить руками всё это неудобно.
Начну с того, что скомпилировать не получилось сходу, в эклипсе были ошибки, что мол LinkedList и ListIterator не моут быть непараметризованы типом, сделал параметризацию им по Character. Потом поправил ошибки в рантайме - где-то некорретно работа со строками и символами, где-то обход по итератору и всякие мелочи. Сейчас остановился, ибо некогда, сделал одно исправление, которое уже касатеся алгоритма - в самом начале нужен один шаг вправо явно сделать (думаю, особенность итератора такая, надо покурить ман), а то без него почему-то итерации сразу останавливались на первом же А, хотя по идее не должны были, т.к. та в начале и пропускается "сдвигом", но вот почему-то нет. Далее уже идут тонкости в логике или ещё в чём, но на мои тестовые случаи он пробегает некорректно, сразу после первого Х выходит с неуспехом (кроме случая когда нет закрывающих скобов вообще, который считает успехом). Вобщем, надо разбираться в алгоритме автомата. Желаю удачи, запостите решение, я посмотрю тоже. Ну или может на след неделе потыкаюсь ещё. |
11.10.2016, 10:09 | #3 | |
Пользователь
Регистрация: 09.06.2015
Сообщений: 21
|
Цитата:
Продублирую словесное описание, для удобства: Cначала ГЗЧ движется вправо до первой правой скобки, заменяет ее символом X, переходит в состояние q1 и движется влево до ближайшей левой скобки, заменяет ее символом X, переходит в состояние q0 , и челночное движение повторяется. Если машина, находясь в состоянии q1, достигает левого символа А, то печатает "0" и останавливается – скобочное выражение неправильно. Если машина, находясь в состоянии q0, достигает правого символа А, не обнаружив больше правой скобки, то переходит в заключительное состояние q2, связанное с движением влево, и в последний раз просматривает последовательность: не осталась ли непарная левая скобка. Если по пути встретится левая скобка, то машина печатает "0" и останавливается. При достижении в состоянии q2 левого символа А, машина печатает "1" и останавливается – скобочное выражение правильно. |
|
18.10.2016, 09:32 | #4 | |
Регистрация: 03.10.2016
Сообщений: 3
|
Цитата:
Прикреплю обновлённый проект. |
|
27.10.2016, 09:50 | #5 |
personality
Старожил
Регистрация: 28.04.2009
Сообщений: 2,876
|
Посмотрел мельком.
Вижу что при наличии закрывашки он вроде как хочет всё корректно посчитать. Но если он не нашёл закрывашки вообще (случай с ((((( ) или не нашёл закрывашки после очередного найденного () при том, что не все символы ещё распарсены, он говорит что всё правильно, а по идее он должен в этих случаях начинать с первого символа снова, искать что не взял (ну или вернуться назад смотря что ещё не взято). По коду кажется всё правильно, но вот меня опять же смущает итератор, находясь на конце, вызов привиоус приводит к тому, что следующая итерация вайла срывается, т.к. символ == А, т.е. семантический казус, думаем что в буфер ляжет "следующий символ", а по факту кладётся текущий символ и производится сдвиг. Посему надо во втором стейте сперва двинуть один раз налево безусловно (как и в начале всего автомата, как я писал выше - разик направо): Код:
Последний раз редактировалось phomm; 27.10.2016 в 09:52. |
31.10.2016, 17:54 | #6 |
Регистрация: 03.10.2016
Сообщений: 3
|
Действительно, теперь всё работает, погонял на тестах, вроде всё нормально. А алгоритм всё-таки удивляет) И очень благодарен Вам за помощь
Для всех желающих прикреплю финальный вариант проекта |
Опции темы | Поиск в этой теме |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Машина тьюринга. проверка на четность | I am Olik | Помощь студентам | 3 | 09.06.2014 07:08 |
Машина Тьюринга, алгоритм Маркова, РАМ-машина | Irinabrik | Фриланс | 10 | 21.03.2014 13:19 |
Машина Тьюринга, алгоритм Маркова, РАМ-машина | Irinabrik | Помощь студентам | 4 | 16.03.2014 22:59 |
Машина Тьюринга и алгоритмы Маркова. Машина Поста. | MarkForMath | Помощь студентам | 0 | 27.04.2011 21:55 |