Вопросы с тегом «regular-language»

Вопросы о формальных языках, которые можно описать с помощью регулярных выражений (в смысле Клини) или, что эквивалентно, языков, которые могут быть приняты конечными автоматами.

31
Рациональная иерархия Эйленберга нерациональных автоматов и языков - где она сейчас?

В предисловии к своим очень влиятельным книгам «Автоматы, языки и машины» (тома A, B) Самуэль Эйленберг обещал соблазнительно изложить тома C и D, посвященные «иерархии (называемой рациональной иерархией) нерациональных явлений ... используя рациональные отношения как инструмент для сравнения....

27
Почему обычные языки называются «обычными»?

Почему регулярные языки (и из этих регулярных выражений) называются "регулярными"? Существует много закономерностей и в контекстно-свободных языках других типов языков. Я предполагаю, что в начале прилагательное «обычный» использовалось для того, чтобы отличать этот тип языков от других...

26
Существует ли обычный древовидный язык, в котором средняя высота дерева размера

Мы определяем язык регулярного дерева, как в книге TATA : это множество деревьев, принятых недетерминированным автоматом конечного дерева (глава 1) или, что эквивалентно, множество деревьев, порожденных грамматикой регулярного дерева (глава 2). Оба формализма очень похожи на хорошо известные...

26
Подсчет слов, принятых обычной грамматикой

Учитывая регулярный язык (NFA, DFA, грамматика или регулярное выражение), как можно посчитать количество принимаемых слов на данном языке? Интерес представляют как «ровно n букв», так и «не более n букв». У Маргареты Акерман есть две статьи по теме перечисления слов, принятых NFA, но я не смог...

23
Определение пустоты пересечения регулярных языков в субквадратичном времени

Пусть L1,L2L1,L2L_1,L_2 будут двумя обычными языками, заданными NFA M1,M2M1,M2M_1,M_2 качестве входных данных. Предположим, мы хотели бы проверить, является ли L1∩L2≠∅L1∩L2≠∅L_1\cap L_2\neq \emptyset . Это можно сделать с помощью квадратичного алгоритма, который вычисляет автомат произведений...

23
Проверка того, можно ли запланировать буквы для достижения слова на обычном языке

Я фиксируем регулярный язык на алфавите , и я считаю следующую проблему , которую я называю письмо планирования для L . Неофициально, ввод дает мне n букв и интервал для каждой буквы (то есть минимальную и максимальную позицию), и моя цель состоит в том, чтобы поместить каждую букву в ее интервал...

21
Обычные языки с теоретико-категориальной точки зрения

Я заметил, что обычные языки над алфавитом можно естественно рассматривать как набор символов, а на самом деле как решетку. Более того, конкатенация вместе с пустым языком ϵ определяет строгую моноидальную структуру в этой категории, которая является дистрибутивной по объединениям (я не уверен...

20
Особый класс языков: «круговые» языки. Это известно?

Определите следующий класс «круговых» языков поверх конечного алфавита Sigma. На самом деле, название уже существует для обозначения другой вещи, которая, кажется, используется в области вычислений ДНК. AFAICT, это другой класс языков. Язык L является круговым, если для всех слов www в Σ...

20
Сложность пересечения регулярных языков как контекстно-свободных грамматик

При заданных регулярных выражениях , существуют ли нетривиальные ограничения на размер наименьшей контекстно-свободной грамматики для R 1 ∩ ⋯ ∩ R n ?р1, … , RNR1,…,RnR_1, \dots, R_nр1∩ ⋯ ∩ RNR1∩⋯∩RnR_1 \cap \cdots \cap...

20
Отношение между

Пусть R E GREG\mathsf{REG} - класс всех регулярных языков. R E G ⊄ A C 0 A C 0 ∩ R E GA C0⊄ R E GAC0⊄REG\mathsf{AC}^0 \not\subset \mathsf{REG}R E G ⊄ A C0REG⊄AC0\mathsf{REG} \not\subset \mathsf{AC}^0A C0∩ R E GAC0∩REG\mathsf{AC}^0 \cap...

19
Какое количество языков принимается DFA размера

Вопрос прост и прям: для фиксированного , сколько (разных) языков принято DFA размером n (то есть nnnnnnnnnn состояний)? Я официально заявлю это: Определите DFA как , где все как обычно и δ : Q × Σ → Q (возможно, частичная) функция. Нам нужно установить это, поскольку иногда только полные функции...

19
Является ли JSON обычным языком?

Мне было интересно, если спецификация JSON определяет обычный язык. Это кажется достаточно простым, но я не уверен, как это доказать самому. Причина, по которой я спрашиваю, заключается в том, что мне было интересно, можно ли использовать регулярные выражения для эффективного анализа JSON. Может ли...

18
Можно ли проверить, является ли вычислимое число рациональным или целым?

Можно ли алгоритмически проверить, является ли вычисляемое число рациональным или целым? Другими словами, возможно ли для библиотеки, которая реализует вычислимые числа, предоставлять функции isIntegerили isRational? Я предполагаю, что это невозможно, и что это как-то связано с тем, что невозможно...

18
Границы по размеру наименьшего NFA для L_k-отчетливых

Рассмотрим язык different состоящий из всех строк k- букв над Σ, таких, что никакие две буквы не равны:L k - d i s t i n c tLk−distinctL_{k-distinct}kkΣ\Sigma L k - d i s t i n c t : = { w = σ 1 σ 2 . , , σ к | ∀ я ∈ [ к ] : σ я ∈ Е  и  ∀ J ≠ я : σ J ≠ σ я...

17
Какое минимальное расширение FO охватывает класс регулярных языков?

Контекст: отношения между логикой и автоматами Теорема Бучи гласит, что монадическая логика второго порядка над строками (MSO) охватывает класс регулярных языков. Фактически доказательство показывает, что экзистенциальный MSO ( или EMSO ) над строками достаточен для захвата обычных языков. Это...

17
Неоднозначность и логика

В теории автоматов (конечных автоматов, автоматов с выталкиванием, ...) и в сложности существует понятие «неоднозначность». Автомат является неоднозначным, если существует слово по крайней мере, с двумя различными принимающими сериями. Машина является неоднозначной, если для каждого слова принятого...

16
Насколько маленьким может быть NFA по сравнению с минимальным однозначным конечным автоматом (UFA) того же обычного языка?

Однозначные конечные автоматы (UFA) - это особый тип недетерминированных конечных автоматов (NFA). NFA называется однозначным, если каждое слово имеет не более одного приемлемого пути.w ∈ Σ*вес∈Σ*w\in \Sigma^* Это означает , что .D FA ⊂ UFA ⊂ NFADFA⊂UFA⊂NFADFA\subset UFA\subset NFA Известные...

16
Может ли постоянная неоднозначность уменьшить сложность состояния обычных языков?

Мы говорим , что НКА является постоянно Неоднозначность , если существует K ∈ N такое , что любое слово W ∈ Е * принимается либо 0 или (точно) К путям.MMMk∈Nk∈Nk\in \mathbb{N}w∈Σ∗w∈Σ∗w\in \Sigma^*000kkk Если автомат постоянно неоднозначен при k = 1 , то M называется однозначным FA...

14
Значение сложности состояния в автоматах и ​​регулярных языках?

Я читаю " Объединение регулярных языков и сложность описания " Галины Йирасковой, 2009 г., о сложности состояний, возникающей в результате объединения двух регулярных языков (Галина Жираскова), но я не могу понять, каковы будут практические последствия сложности состояний , Первая тривиальная...

14
Обычный против TC0

Согласно Сложности Zoo , и мы знаем, что R e g не может сосчитать, поэтому T C 0 ⊈ R e g . Однако это не говорит, если R e g ⊆ T C 0 или нет. Поскольку мы не знаем N C 1 ⊈ T C 0, мы также не знаем R e g ⊈ T C 0 .Reg⊆NC1Reg⊆NC1\mathsf{Reg} \subseteq \mathsf{NC^1}RegReграмм\mathsf{Reg}TC0E R...