Недавно был задан интересный вопрос, который впоследствии был удален. Для обычного языка его сложность DFA - это размер минимального DFA, принимающего его, а сложность NFA - это размер минимального NFA, принимающего его. Хорошо известно, что между двумя сложностями существует экспоненциальное...
Существует ли алгебраическая характеристика числа слов заданной длины в обычном языке? Википедия приводит результат несколько неточно: Для любого регулярного языка существуют константы и многочлены таким образом, что для каждого п числа s_L (п) из слова длины n в L удовлетворяют уравнению s_L (n) =...
Известно, что язык слов, содержащих одинаковые числа 0 и 1, не является регулярным, а язык слов, содержащих одинаковые числа 001 и 100, является регулярным ( см. Здесь ). Учитывая два слова , разрешимо ли, если язык слов, содержащий равное количество и является...
Учитывая алфавит , сколько существует различных регулярных языков, которые могут быть приняты недетерминированным конечным автоматом с n состояниями?Σ={a,b}Σ={a,b}\Sigma = \{ a,b \}nnn В качестве примера рассмотрим . Затем у нас есть 2 18 различных конфигураций перехода и 2 3 различных конфигурации...
Мне было интересно, когда языки, которые содержат одинаковое количество экземпляров двух подстрок, будут регулярными. Я знаю, что язык, содержащий равное количество единиц и нулей, не является регулярным, но является языком, таким как , где = число экземпляров подстроки "001" равно числу...
Выполняя текущее задание по курсу формальных языков и автоматов, я как бы застрял на упражнениях с унарными языками (надеюсь, это правильный термин), то есть на языках, которые основаны на одной букве. Я не хочу спрашивать о конкретных упражнениях, а о гораздо более общей гипотезе, с которой я...
Я знаю, что существуют нерегулярные языки, поэтому является регулярным, но все примеры, которые я могу найти, являются контекстно-зависимыми, но не контекстно-свободными.L∗L∗L^* Если нет ни одного, как вы это...
Мне бы очень понравилась ваша помощь в следующем: Для любого фиксированного мне нужно решить, есть ли замыкание под следующими операторами:L2L2L_2 Ar(L)={x∣∃y∈L2:xy∈L}Ar(L)={x∣∃y∈L2:xy∈L}A_r(L)=\{x \mid \exists y \in L_2 : xy \in L\} .Al(L)={x∣∃y∈L:xy∈L2}Al(L)={x∣∃y∈L:xy∈L2}A_l(L)=\{x \mid \exists...
Проблема Нет простого способа получить перестановку с помощью регулярного выражения. Перестановка: Получение слово ( «ААБК») в другом порядке, без изменения числа или рода писем.w=x1…xnw=x1…xnw=x_1…x_n Regex: Регулярное выражение. Для подтверждения: «Перестановки регулярных выражений без...
Пусть язык L ⊆ Σ ∗L⊆Σ∗\mathcal{L} \subseteq \Sigma^* регулярный. Факторизация LL\mathcal{L} - это максимальная пара ( X , Y )(X,Y)(X,Y) наборов слов с X ⋅ Y ⊆ LX⋅Y⊆LX \cdot Y \subseteq \mathcal{L} X ≠ ∅ ≠ YX≠∅≠YX \neq \emptyset \neq Y , где X ⋅ Y = { x yX⋅Y={xyX \cdot Y = \{xy | x ∈ X , y ∈ Y...
LLL - обычный язык над алфавитом . Левый фактор относительно - это язык Σ={a,b}Σ={a,b}\Sigma = \{a,b\}LLLw∈Σ∗w∈Σ∗w \in \Sigma^*w−1L:={v∣wv∈L}w−1L:={v∣wv∈L}w^{-1} L := \{v \mid wv \in L\} Как я могу доказать, что...
Итак, я знаю, что проверка того, является ли обычный язык рRR подмножеством обычного языка SSS , разрешима, поскольку мы можем преобразовать их оба в DFA, вычислить R ∩ S¯R∩S¯R \cap \bar{S} , а затем проверить, является ли этот язык пустым. Однако, поскольку это требует преобразования в DFA,...
Я наткнулся на этот рисунок, который показывает, что контекстно-свободные и регулярные языки являются (правильными) подмножествами эффективных задач (предположительно ). Я прекрасно понимаю, что эффективные проблемы являются подмножеством всех разрешимых проблем, потому что мы можем их решить, но...
Я думал, что все регулярные языки могут быть выражены с помощью регулярных выражений (если язык регулярный, он может быть выражен с помощью регулярных выражений), но мне сказали, что для этого вам нужны все три регулярные операции (конкатенация, объединение и звездочка) держать. Например, мне...
Скажем, L⊆{0}∗L⊆{0}∗L \subseteq \{0\}^* . Тогда как мы можем доказать, что L∗L∗L^* регулярно? Если LLL регулярно, то, конечно, L∗L∗L^* также регулярно. Если LLL конечно, то оно регулярно и снова L∗L∗L^* регулярно. Также я заметил, что для L={0p∣p is a prime}L={0p∣p is a prime}L = \{0^p \mid p...
Если регулярно, следует ли из этого, что A регулярно?A2A2A^2AAA Моя попытка доказательства: Да, для противоречия предположим, что не является регулярным. Тогда 2 = ⋅ .AAAA2= A ⋅ AA2=A⋅AA^2 = A \cdot A Поскольку конкатенация двух нерегулярных языков не является регулярной, не может быть регулярной....
Я сталкивался с таким вопросом: «Приведите примеры двух обычных языков, которые их объединение не выводит на обычном языке». Это довольно шокирует меня, потому что я считаю, что обычные языки закрыты для объединения. Что означает для меня, что, если я возьму два обычных языка и объединю их, я...
Я хочу доказать, что дополнение не является регулярным, используя свойства замыкания.{ 0N1N∣ n ≥0 }{0N1N|N≥0}\{0^n1^n \mid n \geq{} 0\} Я понимаю, что лемму прокачки можно использовать, чтобы доказать, что не является регулярным языком. Я также понимаю, что обычные языки закрыты в рамках операции...
Вот проблема: Докажите, что одноленточные машины Тьюринга, которые не могут писать на той части ленты, которая содержит входную строку, распознают только обычные языки. Моя идея состоит в том, чтобы доказать, что этот конкретный TM эквивалентен DFA. Использовать эту ТМ для симуляции DFA очень...
Пусть регулярный, регулярный, не регулярный. Покажите, что не является регулярным, или приведите контрпример.L1L1L_1L1∩L2L1∩L2L_1 \cap L_2L2L2L_2L1∪L2L1∪L2L_1 \cup L_2 Я попробовал это: Посмотрите на . Это регулярно. Для этого я могу построить конечный автомат: регулярный, регулярный, поэтому...