Для фиксированного конечного алфавита , формальный язык над является регулярным , если существует детерминированный конечный автомат (ДКА) над , которая принимает ровно .L ΣΣΣ\SigmaLLLΣΣ\SigmaLΣΣ\SigmaLLL Я интересуюсь языками, которые «почти» регулярны в том смысле, что они могут распознаваться...
Некоторые из вас, возможно, следили за этим вопросом , который был закрыт из-за отсутствия уровня исследования. Итак, я извлекаю часть вопроса, которая находится на исследовательском уровне. Помимо «более простых» техник, таких как приведение к сортировке или задача, полная по EXPTIME, какие методы...
Когда я возился с неканоническим анализом LR, я придумал метод синтаксического анализа (с таблицами бесконечного размера, что делает его несколько непрактичным ), способный анализировать ровно однозначные грамматики за времени, и мне было интересно, возможно ли это сделать лучше:O(n2)O(n2)O(n^2)...
Помимо (детерминированной) сложности связи отношения , другой основной мерой для объема необходимой связи является номер раздела протокола . Связь между этими двумя показателями известна до постоянного фактора. Монография Кушилевица и Нисана (1997) даетRc c ( R )сс(р)cc(R)ррR p p ( R )пп(р)pp(R) c...
Я заметил, что обычные языки над алфавитом можно естественно рассматривать как набор символов, а на самом деле как решетку. Более того, конкатенация вместе с пустым языком ϵ определяет строгую моноидальную структуру в этой категории, которая является дистрибутивной по объединениям (я не уверен...
Насосная лемму для регулярных языков можно доказать, рассматривая конечный автомат, распознающий язык изучал, выбирая строку с длиной больше , чем его число состояний, и применением принципа Дирихля. Однако прокачивающая лемма для языков без контекста (а также лемма Огдена, которая является...
Определите следующий класс «круговых» языков поверх конечного алфавита Sigma. На самом деле, название уже существует для обозначения другой вещи, которая, кажется, используется в области вычислений ДНК. AFAICT, это другой класс языков. Язык L является круговым, если для всех слов www в Σ...
При заданных регулярных выражениях , существуют ли нетривиальные ограничения на размер наименьшей контекстно-свободной грамматики для R 1 ∩ ⋯ ∩ R n ?р1, … , RNR1,…,RnR_1, \dots, R_nр1∩ ⋯ ∩ RNR1∩⋯∩RnR_1 \cap \cdots \cap...
Обозначим через количество слов длины в (возможно, неоднозначном) контекстно-свободном языке.wnwnw_nnnn Что известно о ?wnwnw_n Я уверен, что это много изучалось, но я ничего не мог найти на...
DFA имеет синхронизирующее слово, если есть строка, которая отправляет любое состояние DFA в одно состояние. В «Гипотезе Черни для апериодических автоматов» А. Н. Трахтмана («Дискретная математика и теоретическая информатика», том 9: 2, 2007, с. 3-10) он писал: В 1964 году Черни предположил, что...
Главный / Общий Вопрос Пусть LLL будет языком. Определим языки LiLiL_i с L0=LL0=LL_0 = L и Li={xwy:xy∈Li−1,w∈L}Li={xwy:xy∈Li−1,w∈L}L_i = \{xwy : xy \in L_{i-1}, w \in L\} для i≥1i≥1i \geq 1 . Рассмотрим L = ⋃ л я . Таким образом, мы неоднократно «встраивать» L в себя , чтобы получить L...
Вопрос прост и прям: для фиксированного , сколько (разных) языков принято DFA размером n (то есть nnnnnnnnnn состояний)? Я официально заявлю это: Определите DFA как , где все как обычно и δ : Q × Σ → Q (возможно, частичная) функция. Нам нужно установить это, поскольку иногда только полные функции...
Большинство современных реализаций регулярных выражений, таких как perl или .NET, выходят за рамки классического компьютерного определения REGEX с такими функциями, как lookahead и lookbehind. Позволяют ли эти функции анализировать операторы, которые не могут быть описаны конечным автоматом без...
Мне было интересно, если спецификация JSON определяет обычный язык. Это кажется достаточно простым, но я не уверен, как это доказать самому. Причина, по которой я спрашиваю, заключается в том, что мне было интересно, можно ли использовать регулярные выражения для эффективного анализа JSON. Может ли...
У меня совсем недавно была дискуссия о машинах Тьюринга, когда меня спросили: «Машина Тьюринга получена из автоматов или наоборот»? Конечно, я не знал ответа, но мне любопытно узнать. Машина Тьюринга - это немного более сложная версия автоматов Push-Down. Исходя из этого, я предполагаю, что машина...
Хорошо известно, что проблема эквивалентности неразрешима для общих контекстно-свободных языков. Тем не менее, все доказательства этого факта, о которых я знаю, похоже, включают в себя некоторые неоднозначные контекстно-свободные грамматики. По этой причине я хотел бы спросить, известно ли,...
Можно ли алгоритмически проверить, является ли вычисляемое число рациональным или целым? Другими словами, возможно ли для библиотеки, которая реализует вычислимые числа, предоставлять функции isIntegerили isRational? Я предполагаю, что это невозможно, и что это как-то связано с тем, что невозможно...
Я пытаюсь решить конкретную проблему, и я подумал, что смогу решить ее, используя теорию автоматов. Мне интересно, какие модели автоматов имеют разрешимость за полиномиальное время? то есть если у вас есть машины вы можете проверить, эффективно ли . L ( M 1 ) ⊆ L ( M 2 )M1, M2M1,M2M_1, M_2Л ( М1) ⊆...
Это известный результат, что вопрос Генерирует ли контекстно-свободная грамматика обычный язык? неразрешима. Однако он становится разрешимым в унарном алфавите просто потому, что в этом случае классы контекстно-свободных и регулярных языков совпадают. Мой вопрос состоит в том, чтобы знать, что...
Существует множество алгоритмов, которые могут анализировать грамматику без контекста за . Используя матричное умножение, можно даже пойти асимптотически быстрее, чем это.O(n3)O(n3)O(n^3) Тем не менее, все алгоритмы для разбора произвольных CFG, которые я знаю, имеют использование пространства в...