Описание тега automaton
An automaton is a mathematical object describing an abstract machine with a finite set of states and transitions between these that runs on sequences of inputs consisting of letters (or symbols) picked from an alphabet.
1
ответ
Как бы вы доказали, что заказанный язык является регулярным?
Я хочу знать, как доказать, что язык с ограничениями порядка является регулярным. Например, если у вас есть Σ = {1,2,3,4,5}, где L (подмножество Σ*) = (a1,a2,...an) такое, что +1 было больше, чем как бы Вы доказываете, что это обычный язык? например…
29 окт '13 в 23:07
1
ответ
Понять лемму прокачки
Я относительно новичок в лемме прокачки, и у меня есть проблема, которая, я думаю, я ответил правильно, может кто-нибудь сказать мне, если это работает, и если нет, то почему Проблема: {www | w is {a,b}*} Мой подход: L = www u * (v ^ k) * w должно б…
30 апр '14 в 23:14
1
ответ
Грамматическая помощь (Теория автоматов)?
Привет, ребята, у меня есть вопрос, простой вопрос с Automaton, я не уверен, является ли это правильным местом или нет psoting такого рода вопроса. На самом деле, в этом году у меня есть курс по компиляции, и если кто-нибудь знает какой-нибудь хорош…
11 ноя '11 в 21:38
2
ответа
Что такое суффикс автомат?
Может кто-нибудь объяснить мне, что такое суффиксный автомат, и как он работает и отличается от суффиксных деревьев и суффиксных массивов? Я уже пробовал поиск в Интернете, но не смог найти четкого исчерпывающего объяснения. Я нашел следующую ссылку…
25 июн '14 в 14:10
3
ответа
Разработка недетерминированных конечных автоматов в C++ (неверный вывод)
Я делаю задание для симуляции недетерминированного конечного автомата, как я объясняю в этом посте. У меня есть этот вход читать из файла tarea4.in: 1 6 8 0 2 2 5 0 0 a 0 1 a 1 1 b 1 2 c 1 3 c 3 4 d 4 4 d 4 5 d 5 aaabcccc aabbbbcdc abbcdddcc acddddd…
16 май '12 в 20:44
1
ответ
Алгоритм, который проверяет, генерирует ли контекстно-свободная грамматика бесконечный язык, который отклоняет DFA
У меня есть DFA A и CFG G, тогда я должен проверить, генерирует ли G бесконечные слова, которые A не принимает (отклоненные A), и хорошее время сложности. Я думал построить граф с CFG, и если он содержит направленный цикл, то производит бесконечный …
06 апр '17 в 10:48
3
ответа
Объединение нескольких регулярных выражений в один автомат
Допустим, у меня есть список регулярных выражений (чтение из внешнего источника - файла, базы данных и т. Д.). Я хочу проверить, какому из этих регулярных выражений соответствует строка. Я могу создать итерации по всем этим регулярным выражениям и с…
08 мар '13 в 15:47
1
ответ
Как спроектировать машину Тьюринга, которая проверяет, является ли число простым или нет?
Я мог только понять, что логика должна была включать логику умножения и деления на машинах Тьюринга. Но на самом деле я не могу разобрать точное решение.
03 дек '18 в 15:17
1
ответ
Напишите регулярное выражение, описывающее множество
L {w | w содержит любое количество подстрок 00 и 11, причем одна из них встречается в любом месте w} Я предполагаю, что, поскольку 1 может быть где угодно, поэтому Σ*001Σ*1Σ*11Σ* должно быть регулярным выражением. Есть мысли или исправления?
20 фев '19 в 11:37
1
ответ
Матрица представлена в виде блоков - Клен - Сотовый автомат
У меня есть только базовые навыки Maple, и я не знаю, как представлять матрицу графически, как блоки, где 1 в матрице соответствует блоку, а 0 - пустому пространству. Пожалуйста, смотрите мой код ниже, где я добавляю "1", то есть блок к центральному…
24 апр '17 в 11:56
0
ответов
Лемма прокачки на регулярном языке для строки с четными нулями
Определить, является ли строка с четным числом нулей а) контекстной, б) регулярной а) используя лемму прокачки для КЛЛ.... ее можно представить как e (0n) e (0n) e. так что это КЛЛ. б) это можно представить как (00)* в регулярном выражении Итак, я д…
07 апр '14 в 09:36
2
ответа
Переход из состояния в состояние в этом автомате с помощью HashMap
Я использую этот метод для перехода от состояния к следующему на этом симуляторе автомата: public void processString (String string){ StringBuilder stepString= new StringBuilder (string); int actualStateIntIndex; System.out.println("THE FOUND INITIA…
09 дек '09 в 16:16
1
ответ
Как мне реализовать методы equals и hashCode в HashMap для представления состояния автомата?
Я хочу поместить объекты State (которые являются HashMaps с Character в качестве ключа и State как Value в ArrayList с именем allStates. Должен ли я переопределить здесь методы equals и hashCode? Почему? Как? Этот код предназначен для классов Automa…
09 дек '09 в 18:23
1
ответ
Что такое пересечение двух языков?
Учитывая языки L1={anb2m|n,m≥1} L2={anb3n|n≥0} L = L1 ∩ L2 я знаю это L1 это обычный язык и L2 может быть представлен КПК. Но я не понимаю ответ, который утверждает, что L является {a2nb6n|n≥1}, Как рассчитывалось это решение?
16 фев '17 в 18:03
1
ответ
Рисование простого недетерминированного конечного автомата (NFA)
Как я могу нарисовать NFA (автомат) для этого вопроса? Сначала следует принять: алфавит = х, у, г L= { w | w такой, что одно из числа вхождений x,y,z кратно трем. } Например: {xxx, yyy, zzz, xyxyzzz, xyxyx, zyzyz...}
26 мар '12 в 22:08
2
ответа
Как преобразовать DFA в регулярное выражение?
Я читаю книгу: введение в теорию вычислений и застрял на этом примере. Преобразуйте DFA в эквивалентное выражение, преобразовав его сначала в GNFA(обобщенный недетерминированный конечный автомат), а затем преобразуйте GNFA в регулярное выражение. во…
06 май '17 в 03:23
0
ответов
Информатика. Нужно объяснение об асинхронном автомате ввода-вывода
В настоящее время я читаю книгу Нэнси Линч о распределенных системах, главу об автомате ввода-вывода. И у меня есть следующие вопросы, связанные с упражнением книги 8.13(с). Нам дан некоторый автомат A с sig(A) пустым. Traces(P) - это набор последов…
16 ноя '17 в 09:52
1
ответ
Недетерминированный эпсилон-автомат Python: объект не повторяется
Я должен сделать недетерминированный конечный автомат с эпсилон-переходами. Я в большей степени специалист по ac, C#, JavaScript, но мой университет считает, что питон - это единственный путь, по которому я почему-то работал, поэтому сегодня я выучи…
11 апр '14 в 20:39
1
ответ
Автомат с нажатием кнопки, который распознает отрицание языка
В качестве примера: Скажем, я хочу создать КПК, который распознает язык всех строк в алфавите {1,0}, которые НЕ являются палиндромами. Если я спроектирую карманный компьютер, который распознает язык всех строк по {1,0}, которые являются палиндромами…
22 ноя '14 в 00:31
1
ответ
Почему язык не является регулярным?
Покажите, что язык не является регулярным. L = {a^n b^m: n>m}
24 фев '12 в 00:32