Мне было интересно, так как * сама звезда-свободный язык, есть регулярный язык , который не является звездой свободного языка? Не могли бы вы привести пример?a∗a∗a^* (из википедии ) Лоусон определяет беззвездные языки как: Обычный язык называется свободным от звезд, если он может быть описан с...
Какое из следующих утверждений является правильным? достаточные и необходимые условия о регулярности языка существуют, но еще не обнаружены. Там нет достаточного и необходимого условия о регулярности языка. Насосная лемма является необходимым условием нерегулярности языка. Насосная лемма является...
Регулярная expresssion определяется рекурсивно aaa для некоторых - это регулярное выражение,a ∈ Σa∈Σa \in \Sigma εε\varepsilon - это регулярное выражение, ∅∅\emptyset - это регулярное выражение, ( R1∪ R2)(R1∪R2)(R_1 \cup R_2) где и - регулярные выражения, регулярное выражение,р1R1R_1р2R2R_2 ( R1∘...
На работе мне было поручено вывести некоторую информацию о типах динамического языка. Я переписываю последовательности операторов во вложенные letвыражения, например так: return x; Z => x var x; Z => let x = undefined in Z x = y; Z => let x = y in Z if x then T else F; Z => if x then {...
Например, я знаю, что нерегулярный язык находится в A C 0 . Я хотел бы знать больше примеров, как
Учитывая два набора строк над алфавитом Σ , можем ли мы вычислить наименьший детерминированный конечный автомат (DFA) M такой, что A ⊆ L ( M ) и L ( M ) ⊆ Σ ∗ ∖ B ?А , БA,ВA,BΣΣ\SigmaMMMA ⊆ L ( M)A⊆L(M)A \subseteq L(M)Л ( М) ⊆ Σ*∖ BL(M)⊆Σ*∖ВL(M) \subseteq \Sigma^*\setminus B Другими словами,...
Существует ли алгоритм / систематическая процедура для проверки правильности языка? Другими словами, учитывая язык , заданный в алгебраической форме (думаю , что - то вроде ), проверить , является ли регулярным или не язык. Представьте, что мы пишем веб-сервис, чтобы помочь студентам со всеми...
Предположим, что - обычный язык над упорядоченным алфавитом. Создан ли язык, беря каждое слово в и сортируя его всегда как обычный
Я знаю, что языки, которые можно определить с помощью регулярных выражений, и языки, распознаваемые DFA / NFA (конечными автоматами), эквивалентны. Также не существует DFA для языка . Но все это можно записать с помощью регулярных выражений (в этом отношении любого нерегулярный язык может быть) ,...
Опишите обычный язык, который не может быть принят ни одним DFA, имеющим только три состояния. Я не совсем уверен, с чего начать, и мне было интересно, если кто-то может дать мне несколько советов или советов. Я понимаю, что лемму прокачки можно использовать для доказательства того, что язык не...
Из моего чтения кажется, что большинство грамматик занимается созданием бесконечного числа строк. Что делать, если вы работали наоборот? Если задано n строк длиной m, должна быть возможность создать грамматику, которая будет генерировать эти строки и только эти строки. Есть ли известный способ...
Напишите для десятичного расширения (без начального ). Пусть и целые числа с . Рассмотрим язык десятичных разложений кратных плюс константа:n¯n¯\bar nnnn0aaabbba>0a>0a > 0aaa M={ax+b¯¯¯¯¯¯¯¯¯¯¯¯¯¯∣x∈N}M={ax+b¯∣x∈N}M = \{ \overline{a\,x+b} \mid x\in\mathbb{N} \} Является регулярными?...
Или, по крайней мере, сгенерируйте набор строк, которые принимает один NFA, чтобы я мог передать их в другой NFA. Если я сделаю поиск по каждому пути NFA, это будет работать? Хотя это займет много...
Я сдал экзамены по теории вычислений несколько недель назад, и это был один из вопросов: Предположим, что языкL={(anbm)r∣n,m,r≥0}L={(anbm)r∣n,m,r≥0}L=\{(a^nb^m)^r \mid n,m,r\ge 0\} L регулярно? Если да, укажите для него регулярное выражение или автомат. После того, как я кратко спросил его ответ...
Я думаю об унарных языках LkLkL_k , где LkLkL_k - множество всех слов, длина которых равна сумме kkk квадратов. Формально: Легко показать, что L 1 = { a n 2 ∣ n ∈ N 0 } не является регулярным (например, с леммой Пампинга). Кроме того, мы знаем, что каждое натуральное число является суммой четырех...
Мы можем сформировать DFA, принимающий двоичные числа, делимые на nnn . Например, DFA, принимающий двоичные числа, делимые на 2, может быть сформирован следующим образом: Аналогично, DFA, принимающий двоичные числа, делимые на 3, может быть сформирован следующим образом: Мы можем следовать четко...
Учитывая язык L={anbncn}L={anbncn} L= \{a^n b^n c^n\} , как я могу прямо сказать, не глядя на правила производства, что этот язык не является регулярным? Я мог бы использовать лемму прокачки, но некоторые парни говорят, просто глядя на грамматику, что это не совсем так. Как это...
Я начал изучать недетерминированные автоматы, используя книгу Хопкрофта и Уллмана . Я застрял в проблеме, которая показалась мне очень интересной: Дать недетерминированный конечный автомат, принимающий все строки, имеющие одинаковое значение, при оценке слева направо как справа налево путем...
Я работаю через Sipser Book (2-е издание) и наткнулся на этот пример, который я не понимаю. В книге говорится, что этот NFA принимает пустую строку εε\epsilon . Может ли кто-нибудь объяснить мне, почему это так? Насколько я понимаю, εε\epsilon перейдет к Q3Q3q_3 который не является состоянием...