Конечные автоматы!

@videolord · Регистрация: 20.02.2011

Студворк — интернет-сервис помощи студентам

Как можно написать с помошью конечных автоматов (Было бы классно если можно написать с помошью Детерминированных и недетерминированных конечных автоматов )

Дано массив слов String[] dir={"out","output","puton","in","input" ,"one"};
если введенная строка состоит из этих слов то вывести "yes"
если нет то No

Ввод
oneputonininputoutoutput
Вывод
Yes

Ввод
inonputin
Вывод
No

Ввот ссылка на задачу http://acm.timus.ru/problem.aspx?space=1&num=1102
Написал с помошью регулярных выражений но хавает очень много памяти
Memory limit exceeded on test 1 Выделено памяти 16 630 КБ,а ограничение 16мб)!

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import java.io.*;
import java.util.*;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
public class regex {
public static void main(String[] args)  throws IOException {
Scanner sc=new Scanner(System.in);
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
int n=sc.nextInt();
String str;
Pattern p =Pattern.compile("^(out(put)?|puton|in(put)?|one)+$");
for(int i=0;i<n;i++){
Matcher m = p.matcher(reader.readLine());
if (m.matches()==true)
System.out.println("YES");  
else
System.out.println("NO");
}}
}

Norby · 18.04.2011, 02:25

Java - не язык для олимпиадного программирования. Используйте лучше С++, иначе по памяти не пройдет скорее всего.

@Хохол · 25.04.2011, 20:14

Все команды ИТМО, в последние года занимавшие одни из первых мест на финалах ACM ICPC, писали на Java.

Norby · 25.04.2011, 21:46

Не по теме:

Сообщение от Хохол

Все команды ИТМО, в последние года занимавшие одни из первых мест на финалах ACM ICPC, писали на Java.

А ссылочку можно где почитать?

@Хохол · 25.04.2011, 22:04

Для начала - профиль Вингера (Владислав Исенбаев) на тимусе:
http://acm.timus.ru/status.asp... &count=100

Ща еще ченить поищу.

Добавлено через 13 минут
Пруфлинка не нашел. Просто слышал такое в среде олимпиадников. На всех контест-сайтах их топовые участники решают на джаве.
Еще один:
http://acmp.ru/index.asp?main=... t=0&page=0

В общем, будем надеяться что сам Станкевич ответит:

http://vkontakte.ru/andrewzta (на стене)

@popov654 · 26.04.2011, 05:06

Ну ИМХО можно и на Джаве без регэкспов решить... Но это будет сложнее
Здесь первый символ не всегда однозначно определяет следующее слово, поэтому при определённых символах будет возможно несколько переходов... Надо их пробовать все по очереди, пока не подойдёт хотя бы один. Но может так получиться, что рано или поздно он запорется на следующем шаге (или через несколько шагов, если бы пример был чуть сложнее). Так что в общем случае надо делать какую-то очередь, и из неё брать варианты... Если дошли до финиша, очередь можно почистить

@videolord · 26.04.2011, 15:11 **[ТС]**

Кто нить помогите реализовать , как работает конечные автоматы и как минимизировать?

@popov654 · 26.04.2011, 16:31

В общем случае - это двумерная матрица. Значение клетки - новый номер состояния (хранится отдельно между переходами), один индекс - текущее состояние до перехода, второй - входящий управляющий символ (в простейших ВУЗовских задачках - цифра). Ну и вот. Читаем цифру, идём в массив.
Разумеется, некоторое состояние на момент запуска УЖЕ должно быть, т.н. начальое (init state).

Ну у Вас тут всё и проще, и сложней. С одной стороны, массив можно не лепить, ибо вариантов перехода всё равно несколько, придётся вешать в него коллекции (хотя почему нет? с Вас же именно автоматы требуют). Второй вариант - тупой: идти по списку наших лексем, и проверять, какие годятся полностью. Класть их в очередь, чтобы не потерять. Причём складывать следует вместе с числом, характеризующим номер символа, на котором лексема подошла. Я бы в этом случае посоветовал сделать HashMap и в него складывать векторы (аналоги списков), в качестве ключей брать эти самые начальные индексы. А в векторы класть уже строковые лексемы. Поверьте, оно стОит того. У меня в одном серьёзном приложении вообще использовался вектор векторов из строк, и ничего страшного, всё пашет на ура

Смотрите, что Вы выигрываете: хэш сортировать не надо (по определению), обращение к нему делается мгновенно, вы сразу говорите нужный индекс и тащите элемент из вектора, пока тот не опустеет. Опустел - удаляете из хэша. Индексы можно либо хранить отдельным списком (можно заюзать Stack), либо определять самостятельно, вызвав у Вашего HashMap метод keySet() и посмотрев, что у него в конце. Он вроде обычно уже сортирован; если нет, то к нему можно применить волшебную инструкцию Collections.sort(obj)
Как идти по хэшу назад? Используйте Collections.rsort(obj), либо там есть специальный метод, позволяющий получить этот сет в виде массива. Как обойти массив в обратном порядке Вы конечно же знаете.
Вы идёте назад до тех пор, пока не получите новых совпадений, тогда Ваш хэш опять начнёт расти вперёд. Если стёрли весь хэш - значит облом, ответ false

Можно вместо хэша использовать вектор из пар "число-строка", но во-первых я не уверен, как лучше организовать пары (можно тоже вектором, но это тупо и небезопасно: длина-то переменная), а во-вторых, придётся уже в буквальном смысле идти назад по нашему списку, причём возможно довольно долго. Так Вы перебираете элементики вектора из хэша любым удобным способом, хоть с помощью итератора, и когда переходите к другому элементу в хэше, то ВСЕГДА меняете индекс, т.к. он уникален. А так Вам придётся переходить гораздо чаще, чем меняется Ваш индекс. В общем, дело вкуса, особой разницы нет.

Разве что если Вам вдруг понадобится вывести лексемы с произвольным индексом (в чём я сомневаюсь), то в хэше - прямой доступ и вывод вектора, тогда как во втором случае Вам придётся идти от самой головы и проверять первый элемент пары, что совсем не гут.

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

Добавлено через 6 минут
Ещё можно использовать рекурсию, но это ИМХО не то, что требуют в условии, и тоже есть шанс (хотя и небольшой), что у Вас какое-нибудь переполнение получится как с регэкспами.

В общем, попробуйте решить этим способом, если будут проблемы отпишитесь, разберёмся вместе. Меня эта задача тоже весьма заинтресовала) По сути что-то вроде суффиксного массива построить требуется)

@Jennea · 01.02.2012, 01:02

Помогите плиз с заданием!!!!! Нужно изобразить ДКА состоящий из 7 состояний, который допускает все
x mod 7 = 5
Алфавит (0,1)

@mutagen · 01.02.2012, 04:42

Java
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
import java.io.FileReader;
import java.io.IOException;
import java.io.LineNumberReader;
 
/**
 * @author mutagen aka Aleksandr Dudak
 * 
 */
public class KAputin {
    static final String[] one = { "output", "puton", "out" };
    static final String[] puton = { "input", "one", "in" };
    static String s = null;
 
    static enum person {
        ONE, PUTON, UNKN
    };
 
    public static void kaPutin(String file) throws IOException {
        LineNumberReader lnr = new LineNumberReader(new FileReader(file));
        while ((s = lnr.readLine()) != null) {
            ka(lnr.getLineNumber());
        }
    }
 
    public static void ka(int line) {
        if (line != 1)
            System.out.println(validate());
    }
 
    public static String validate() {
        person p = person.UNKN;
        while (!s.equals("")) {
            p = checkStart();
            if (p == person.UNKN)
                return "NO";
        }
        return p != person.UNKN ? "YES" : "NO";
    }
 
    public static person checkStart() {
        person ret = person.UNKN;
        if (starts(one))
            ret = person.ONE;
        if (starts(puton))
            ret = person.PUTON;
        return ret;
    }
 
    public static boolean starts(String[] who) {
        for (String str : who) {
            if (s.startsWith(str)) {
                s = s.replaceFirst(str, "");
                return true;
            }
        }
        return false;
    }
 
    static class Test {
        public static void main(String[] args) throws IOException {
            kaPutin("1.txt");
        }
    }
}

Новые блоги и статьи Все статьи Все блоги /
Модель здравосоХранения 6. ESG-повестка и устойчивое развитие; углублённый анализ кадрового бренда anaschu 31.03.2026 В прикрепленном документе раздумья о том, как можно поменять модель в будущем	10 пpимет, которые всегда сбываются Maks 31.03.2026 1. Чтобы, наконец, пришла маршрутка, надо закурить. Если сигарета последняя, маршрутка придет еще до второй затяжки даже вопреки расписанию. 2. Нaдоели зима и снег? Не надо переезжать. Достаточно. . .	Перемещение выделенных строк ТЧ из одного документа в другой Maks 31.03.2026 Реализация из решения ниже выполнена на примере нетипового документа "ВыдачаОборудованияНаСпецтехнику" с единственной табличной частью "ОборудованиеИКомплектующие" разработанного в конфигурации КА2. . . .	Functional First Web Framework Suave DevAlt 30.03.2026 Sauve. IO Апнулись до NET10. Из зависимостей один пакет, работает одинаково хорошо как в режиме проекта так и в интерактивном режиме. из сложностей - чисто функциональный подход. Решил. . .
Автоматическое создание документа при проведении другого документа Maks 29.03.2026 Реализация из решения ниже выполнена на нетиповых документах, разработанных в конфигурации КА2. Есть нетиповой документ "ЗаявкаНаРемонтСпецтехники" и нетиповой документ "ПланированиеСпецтехники". В. . .	Настройка движения справочника по регистру сведений Maks 29.03.2026 Решение ниже реализовано на примере нетипового справочника "ТарифыМобильнойСвязи" разработанного в конфигурации КА2, с целью учета корпоративной мобильной связи в коммерческом предприятии. . . .	Автозаполнение реквизита при выборе элемента справочника Maks 27.03.2026 Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. При выборе "Спецтехники" (Тип Справочник. Спецтехника), заполняется. . .	Сумматор с применением элементов трёх состояний. Hrethgir 26.03.2026 Тут. https:/ / fips. ru/ EGD/ ab3c85c8-836d-4866-871b-c2f0c5d77fbc Первый документ красиво выглядит, но без схемы. Это конечно не даёт никаких плюсов автору, но тем не менее. . . всё может быть. . .

Norby 66 / 66 / 5 Регистрация: 12.03.2008 Сообщений: 392
	18.04.2011, 02:25
	Java - не язык для олимпиадного программирования. Используйте лучше С++, иначе по памяти не пройдет скорее всего. 0

@Хохол 476 / 444 / 34 Регистрация: 20.11.2009 Сообщений: 1,293
	25.04.2011, 20:14
	Все команды ИТМО, в последние года занимавшие одни из первых мест на финалах ACM ICPC, писали на Java. 0

@Хохол 476 / 444 / 34 Регистрация: 20.11.2009 Сообщений: 1,293
	25.04.2011, 22:04
	Для начала - профиль Вингера (Владислав Исенбаев) на тимусе: http://acm.timus.ru/status.asp... &count=100 Ща еще ченить поищу. Добавлено через 13 минут Пруфлинка не нашел. Просто слышал такое в среде олимпиадников. На всех контест-сайтах их топовые участники решают на джаве. Еще один: http://acmp.ru/index.asp?main=... t=0&page=0 В общем, будем надеяться что сам Станкевич ответит: http://vkontakte.ru/andrewzta (на стене) 0

@popov654 33 / 33 / 7 Регистрация: 09.04.2011 Сообщений: 119
	26.04.2011, 05:06
	Ну ИМХО можно и на Джаве без регэкспов решить... Но это будет сложнее Здесь первый символ не всегда однозначно определяет следующее слово, поэтому при определённых символах будет возможно несколько переходов... Надо их пробовать все по очереди, пока не подойдёт хотя бы один. Но может так получиться, что рано или поздно он запорется на следующем шаге (или через несколько шагов, если бы пример был чуть сложнее). Так что в общем случае надо делать какую-то очередь, и из неё брать варианты... Если дошли до финиша, очередь можно почистить 0

@videolord 49 / 15 / 2 Регистрация: 20.02.2011 Сообщений: 152
	26.04.2011, 15:11 [ТС]
	Кто нить помогите реализовать , как работает конечные автоматы и как минимизировать? 0

@popov654 33 / 33 / 7 Регистрация: 09.04.2011 Сообщений: 119
	26.04.2011, 16:31
	В общем случае - это двумерная матрица. Значение клетки - новый номер состояния (хранится отдельно между переходами), один индекс - текущее состояние до перехода, второй - входящий управляющий символ (в простейших ВУЗовских задачках - цифра). Ну и вот. Читаем цифру, идём в массив. Разумеется, некоторое состояние на момент запуска УЖЕ должно быть, т.н. начальое (init state). Ну у Вас тут всё и проще, и сложней. С одной стороны, массив можно не лепить, ибо вариантов перехода всё равно несколько, придётся вешать в него коллекции (хотя почему нет? с Вас же именно автоматы требуют). Второй вариант - тупой: идти по списку наших лексем, и проверять, какие годятся полностью. Класть их в очередь, чтобы не потерять. Причём складывать следует вместе с числом, характеризующим номер символа, на котором лексема подошла. Я бы в этом случае посоветовал сделать HashMap и в него складывать векторы (аналоги списков), в качестве ключей брать эти самые начальные индексы. А в векторы класть уже строковые лексемы. Поверьте, оно стОит того. У меня в одном серьёзном приложении вообще использовался вектор векторов из строк, и ничего страшного, всё пашет на ура Смотрите, что Вы выигрываете: хэш сортировать не надо (по определению), обращение к нему делается мгновенно, вы сразу говорите нужный индекс и тащите элемент из вектора, пока тот не опустеет. Опустел - удаляете из хэша. Индексы можно либо хранить отдельным списком (можно заюзать Stack), либо определять самостятельно, вызвав у Вашего HashMap метод keySet() и посмотрев, что у него в конце. Он вроде обычно уже сортирован; если нет, то к нему можно применить волшебную инструкцию Collections.sort(obj) Как идти по хэшу назад? Используйте Collections.rsort(obj), либо там есть специальный метод, позволяющий получить этот сет в виде массива. Как обойти массив в обратном порядке Вы конечно же знаете. Вы идёте назад до тех пор, пока не получите новых совпадений, тогда Ваш хэш опять начнёт расти вперёд. Если стёрли весь хэш - значит облом, ответ false Можно вместо хэша использовать вектор из пар "число-строка", но во-первых я не уверен, как лучше организовать пары (можно тоже вектором, но это тупо и небезопасно: длина-то переменная), а во-вторых, придётся уже в буквальном смысле идти назад по нашему списку, причём возможно довольно долго. Так Вы перебираете элементики вектора из хэша любым удобным способом, хоть с помощью итератора, и когда переходите к другому элементу в хэше, то ВСЕГДА меняете индекс, т.к. он уникален. А так Вам придётся переходить гораздо чаще, чем меняется Ваш индекс. В общем, дело вкуса, особой разницы нет. Разве что если Вам вдруг понадобится вывести лексемы с произвольным индексом (в чём я сомневаюсь), то в хэше - прямой доступ и вывод вектора, тогда как во втором случае Вам придётся идти от самой головы и проверять первый элемент пары, что совсем не гут. Ну вроде всё. При этом Вам кстати не придётся мучаться с удалеyием из хэша как мне в той программе: там помимо вектора векторов ещё соответствия позиций уникальным именам хранились в хэше. И вот при удалении вектора из большого вектора, элементы сдвигалис и нумерация менялась. Приходилось весь хэш шерстить. Вам-то это не надо Добавлено через 6 минут Ещё можно использовать рекурсию, но это ИМХО не то, что требуют в условии, и тоже есть шанс (хотя и небольшой), что у Вас какое-нибудь переполнение получится как с регэкспами. В общем, попробуйте решить этим способом, если будут проблемы отпишитесь, разберёмся вместе. Меня эта задача тоже весьма заинтресовала) По сути что-то вроде суффиксного массива построить требуется) 1

@Jennea 8 / 8 / 0 Регистрация: 29.05.2011 Сообщений: 181
	01.02.2012, 01:02
	Помогите плиз с заданием!!!!! Нужно изобразить ДКА состоящий из 7 состояний, который допускает все x mod 7 = 5 Алфавит (0,1) 0