Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > Java программирование > Общие вопросы по Java, Java SE, Kotlin
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 03.10.2016, 16:17   #1
ProOvenvan
 
Регистрация: 03.10.2016
Сообщений: 3
По умолчанию Машина Тьюринга. Проверка скобочной последовательности

Добрый день. Возникла такая задача - реализовать машину Тьюринга для проверки правильности скобочной последовательности. Описание мат. части:
Есть лента, скобочная последовательность ограничена символами А.
Головка находится в самом левом положении. Работа машины: сначала ГЗЧ движется вправо до первой правой скобки, заменяет ее символом X, переходит в состояние q1 и движется влево до ближайшей левой скобки,
заменяет ее символом X, переходит в состояние q0 , и челночное движение повторяется.
Если машина, находясь в состоянии q1, достигает левого символа А, то печатает "0"
и останавливается – скобочное выражение неправильно.
Если машина, находясь в состоянии q0, достигает правого символа А, не обнаружив
больше правой скобки, то переходит в заключительное состояние q2, связанное с движе-
нием влево, и в последний раз просматривает последовательность: не осталась ли непар-
ная левая скобка. Если по пути встретится левая скобка, то машина печатает "0" и оста-
навливается. При достижении в состоянии q2 левого символа А, машина печатает "1" и
останавливается – скобочное выражение правильное

Опишу реализацию.
Интерфейс
Код:
package mtbrackets;
 
import java.util.ListIterator;
 
public interface State {
    public State calculate(ListIterator listIterator /*указание на текущее положение головки */);
    /*метод перехода состояния головки*/
Классы, описывающие состояния головок:
Q0
Код:
package mtbrackets;
 
import java.util.ListIterator;
 
public class StateQ0 implements State {
    @Override
    public State calculate(ListIterator listIterator) {
        char symbol = ' ';
        while(symbol != ')' && symbol != 'A') {
            symbol = (char) listIterator.next();
        }
        if (symbol == ')') {
            listIterator.set('X');
            return new StateQ1();
        }
        else return new StateQ2();
    }
}
Q1
Код:
package mtbrackets;
 
import java.util.ListIterator;
 
public class StateQ1 implements State {
    @Override
    public State calculate(ListIterator listIterator) {
        char symbol = ' ';
        while(symbol != '(' || symbol != 'A') {
            symbol = (char) listIterator.previous();
        }
        if (symbol == '(') {
            listIterator.set('X');
            return new StateQ0();
        }
        else {
            listIterator.set('0');
            System.out.println("Неправильная скобочная последовательность");
            return null;
        }
    }
}
Q2
Код:
import java.util.ListIterator;
 
public class StateQ2 implements State {
    @Override
    public State calculate(ListIterator listIterator) {
        char symbol = ' ';
        while(symbol != '(' || symbol != 'A') {
            symbol = (char) listIterator.previous();
        }
        if (symbol == '(') {
            listIterator.set('0');
            return null;
        }
        else {
            listIterator.set('1');
            System.out.println("Правильная скобочная последовательность");
            return null;
        }
    }
}
Класс для заполнения последовательности и объединения состояний головки.
Код:
package mtbrackets;
 
 
import java.util.LinkedList;
import java.util.ListIterator;
import java.util.Scanner;
 
public class Сalculation {
    LinkedList linkedList = new LinkedList(); /*на основе LinkedList формируется последовательность*/
    Scanner in = new Scanner(System.in);
 
    public void calc() {
        System.out.println("Введите длину последовательности");
        int lenghtlist = in.nextInt();
        if (lenghtlist % 2 != 0 ) {
            System.out.println("Последовательность изначально неправильная");
        }
        else {
            linkedList.addFirst("A");
            System.out.println("Введите саму скобочную последовательность");
            for (int i = 0; i <= lenghtlist - 1; i++) {
                linkedList.add(in.next());
            }
            linkedList.addLast("A");
 
            ListIterator listIterator = linkedList.listIterator();
            State state = new StateQ0();
            while (state != null) {
                System.out.println("Состояние ленты:" + linkedList.toString());
                state = state.calculate(listIterator);
            }
            System.out.println("Состояние ленты:" + linkedList.toString());
        }
    }
}
Main класс для запуска программы
Код:
package mtbrackets;
 
public class Main {
 
    public static void main(String[] args) {
        Сalculation сalculation = new Сalculation();
        сalculation.calc();
    }
}
При выполнении программы выдаёт ошибку при входе в состояние Q0. Помогите, пожалуйста, разобраться

Последний раз редактировалось ProOvenvan; 03.10.2016 в 16:25.
ProOvenvan вне форума Ответить с цитированием
Старый 06.10.2016, 14:10   #2
phomm
personality
Старожил
 
Аватар для phomm
 
Регистрация: 28.04.2009
Сообщений: 2,876
По умолчанию

Вот кой чего исправил в коде и набросал заготовочку простенькую для тестирования автомата, а то вводить руками всё это неудобно.
Начну с того, что скомпилировать не получилось сходу, в эклипсе были ошибки, что мол LinkedList и ListIterator не моут быть непараметризованы типом, сделал параметризацию им по Character. Потом поправил ошибки в рантайме - где-то некорретно работа со строками и символами, где-то обход по итератору и всякие мелочи.
Сейчас остановился, ибо некогда, сделал одно исправление, которое уже касатеся алгоритма - в самом начале нужен один шаг вправо явно сделать (думаю, особенность итератора такая, надо покурить ман), а то без него почему-то итерации сразу останавливались на первом же А, хотя по идее не должны были, т.к. та в начале и пропускается "сдвигом", но вот почему-то нет. Далее уже идут тонкости в логике или ещё в чём, но на мои тестовые случаи он пробегает некорректно, сразу после первого Х выходит с неуспехом (кроме случая когда нет закрывающих скобов вообще, который считает успехом). Вобщем, надо разбираться в алгоритме автомата.

Желаю удачи, запостите решение, я посмотрю тоже. Ну или может на след неделе потыкаюсь ещё.
Вложения
Тип файла: zip mtbrackets.zip (2.9 Кб, 9 просмотров)
phomm вне форума Ответить с цитированием
Старый 11.10.2016, 10:09   #3
Ovenvan
Пользователь
 
Регистрация: 09.06.2015
Сообщений: 21
По умолчанию

Цитата:
Сообщение от phomm Посмотреть сообщение
Вот кой чего исправил в коде и набросал заготовочку простенькую для тестирования автомата, а то вводить руками всё это неудобно.
Начну с того, что скомпилировать не получилось сходу, в эклипсе были ошибки, что мол LinkedList и ListIterator не моут быть непараметризованы типом, сделал параметризацию им по Character. Потом поправил ошибки в рантайме - где-то некорретно работа со строками и символами, где-то обход по итератору и всякие мелочи.
Сейчас остановился, ибо некогда, сделал одно исправление, которое уже касатеся алгоритма - в самом начале нужен один шаг вправо явно сделать (думаю, особенность итератора такая, надо покурить ман), а то без него почему-то итерации сразу останавливались на первом же А, хотя по идее не должны были, т.к. та в начале и пропускается "сдвигом", но вот почему-то нет. Далее уже идут тонкости в логике или ещё в чём, но на мои тестовые случаи он пробегает некорректно, сразу после первого Х выходит с неуспехом (кроме случая когда нет закрывающих скобов вообще, который считает успехом). Вобщем, надо разбираться в алгоритме автомата.

Желаю удачи, запостите решение, я посмотрю тоже. Ну или может на след неделе потыкаюсь ещё.
Применил Ваши исправления, от большинства первоначальных ошибок это действительно избавило. Премного благодарен. Сейчас займусь самим алгоритмом, ибо работает не особо корректно. Если получится обязательно прикреплю, но и Вас прошу не забывать, так как могу и не справиться. Для доп. понимания алгоритма прикреплю графическое представление.

Продублирую словесное описание, для удобства:
Cначала ГЗЧ движется вправо до первой правой скобки, заменяет ее символом X, переходит в состояние q1 и движется влево до ближайшей левой скобки, заменяет ее символом X, переходит в состояние q0 , и челночное движение повторяется.
Если машина, находясь в состоянии q1, достигает левого символа А, то печатает "0" и останавливается – скобочное выражение неправильно.
Если машина, находясь в состоянии q0, достигает правого символа А, не обнаружив больше правой скобки, то переходит в заключительное состояние q2, связанное с движением влево, и в последний раз просматривает последовательность: не осталась ли непарная левая скобка. Если по пути встретится левая скобка, то машина печатает "0" и останавливается. При достижении в состоянии q2 левого символа А, машина печатает "1" и останавливается – скобочное выражение правильно.
Ovenvan вне форума Ответить с цитированием
Старый 18.10.2016, 09:32   #4
ProOvenvan
 
Регистрация: 03.10.2016
Сообщений: 3
По умолчанию

Цитата:
Сообщение от phomm Посмотреть сообщение
Вот кой чего исправил в коде и набросал заготовочку простенькую для тестирования автомата, а то вводить руками всё это неудобно.
Начну с того, что скомпилировать не получилось сходу, в эклипсе были ошибки, что мол LinkedList и ListIterator не моут быть непараметризованы типом, сделал параметризацию им по Character. Потом поправил ошибки в рантайме - где-то некорретно работа со строками и символами, где-то обход по итератору и всякие мелочи.
Сейчас остановился, ибо некогда, сделал одно исправление, которое уже касатеся алгоритма - в самом начале нужен один шаг вправо явно сделать (думаю, особенность итератора такая, надо покурить ман), а то без него почему-то итерации сразу останавливались на первом же А, хотя по идее не должны были, т.к. та в начале и пропускается "сдвигом", но вот почему-то нет. Далее уже идут тонкости в логике или ещё в чём, но на мои тестовые случаи он пробегает некорректно, сразу после первого Х выходит с неуспехом (кроме случая когда нет закрывающих скобов вообще, который считает успехом). Вобщем, надо разбираться в алгоритме автомата.

Желаю удачи, запостите решение, я посмотрю тоже. Ну или может на след неделе потыкаюсь ещё.
Немного исправил алгоритм, теперь проставляет "X" (в некоторых случаях даже определяет правильные и неправильные последовательности), но не везде, думаю, проблема в состоянии StateQ2, но не вижу ошибки(
Прикреплю обновлённый проект.
Вложения
Тип файла: rar MTBrackets.rar (15.1 Кб, 9 просмотров)
ProOvenvan вне форума Ответить с цитированием
Старый 27.10.2016, 09:50   #5
phomm
personality
Старожил
 
Аватар для phomm
 
Регистрация: 28.04.2009
Сообщений: 2,876
По умолчанию

Посмотрел мельком.
Вижу что при наличии закрывашки он вроде как хочет всё корректно посчитать.
Но если он не нашёл закрывашки вообще (случай с ((((( ) или не нашёл закрывашки после очередного найденного () при том, что не все символы ещё распарсены, он говорит что всё правильно, а по идее он должен в этих случаях начинать с первого символа снова, искать что не взял (ну или вернуться назад смотря что ещё не взято).
По коду кажется всё правильно, но вот меня опять же смущает итератор, находясь на конце, вызов привиоус приводит к тому, что следующая итерация вайла срывается, т.к. символ == А, т.е. семантический казус, думаем что в буфер ляжет "следующий символ", а по факту кладётся текущий символ и производится сдвиг. Посему надо во втором стейте сперва двинуть один раз налево безусловно (как и в начале всего автомата, как я писал выше - разик направо):
Код:
if (listIterator.hasPrevious()) // проверка на всякий
    listIterator.previous();
В итоге работа более-менее похожа на правду, погоняйте всякие тестовые случаи.

Последний раз редактировалось phomm; 27.10.2016 в 09:52.
phomm вне форума Ответить с цитированием
Старый 31.10.2016, 17:54   #6
ProOvenvan
 
Регистрация: 03.10.2016
Сообщений: 3
По умолчанию

Действительно, теперь всё работает, погонял на тестах, вроде всё нормально. А алгоритм всё-таки удивляет) И очень благодарен Вам за помощь
Для всех желающих прикреплю финальный вариант проекта
Вложения
Тип файла: rar MTBrackets.rar (15.1 Кб, 26 просмотров)
ProOvenvan вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Машина тьюринга. проверка на четность 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