Обратите внимание, что это вопрос, связанный с обучением на курсе CS в университете, это НЕ домашняя работа, и его можно найти здесь под экзаменом осень 2011 года2. Вот два вопроса, на которые я смотрю с прошлого экзамена. Похоже, они связаны, первое: Позволять FINITECFG={<G>∣G is a Context...
Это дополнительный вопрос этого . В предыдущем вопросе об экзотических конечных автоматах Алекс тен Бринк и Рафаэль обратились к вычислительным возможностям особого вида конечного автомата: автоматов с минимальной кучей. Они смогли показать, что набор языков, принимаемых такими машинами ( HALHALHAL...
Детерминированный конечный автомат (DFA) - это модель конечного автомата, способная принимать все и только обычные языки. DFA могут быть (и обычно) определены таким образом, что каждое состояние должно обеспечивать некоторый переход для всех элементов входного алфавита; другими словами, функция...
Если у меня есть грамматика типа 3, она может быть представлена в автомате (без каких-либо операций со стеком), поэтому я могу представлять регулярные выражения с использованием контекстно-свободных языков. Но могу ли я знать, что грамматика типа 3 - это , L L ( 1 ) , S L R ( 1 ) и т. Д. Без...
В моем учебнике упоминается, что: где - пустой язык.∅*= { ϵ }∅*знак равно{ε}\emptyset^*=\{\epsilon\}∅∅\emptyset Однако мы знаем, что , где - любой язык.L ⋅ ∅ = ∅L⋅∅знак равно∅L \cdot \emptyset = \emptysetLLL Я не могу интуитивно понять эту концепцию, потому что операция звезды Клини указывает на...
Пусть . Язык Говорят , обладает свойством «анти-палиндром» , если для каждой строки , что является палиндром, . Кроме того, для каждой строки которая не является палиндромом, либо либо , но не оба (!) (Исключая или).L ⊆ Σ ∗ w w ∉ L u u ∈ L R e v e r s e ( u ) ∈ LΣ={0,1}Σ={0,1}\Sigma = \{ 0, 1...
Существует ли алгебраическая характеристика числа слов заданной длины в обычном языке? Википедия приводит результат несколько неточно: Для любого регулярного языка существуют константы и многочлены таким образом, что для каждого п числа s_L (п) из слова длины n в L удовлетворяют уравнению s_L (n) =...
Таким образом, в основном L удовлетворяет условиям леммы накачки для КЛЛ, но не является КЛЛ (это возможно в соответствии с определением
Это дополнительный вопрос этого . В предыдущем вопросе об экзотических конечных автоматах Алекс тен Бринк и Рафаэль обратились к вычислительным возможностям особого вида конечного автомата: автоматов с минимальной кучей. Они смогли показать, что множество языков, принятых на таких машинах ( ), не...
Можно утверждать, что большинство языков, созданных для описания повседневных проблем, являются контекстно-зависимыми. С другой стороны, возможно и нетрудно найти некоторые языки, которые не являются рекурсивными или даже не рекурсивно-перечислимыми. Между этими двумя типами находятся рекурсивные,...
Для языка LLL определите множество длин как множество длин слов в : L L S ( L ) = { | ты | | U ∈ L }LLLLLLL S (L)={ | ты | |U∈L}LS(L)={|u|∣u∈L}\mathrm{LS}(L) = \{|u| \mid u \in L \} Какие наборы целых чисел могут быть набором длины обычного...
Согласно статье в Википедии , L в означает «сканирование слева направо», а «R» означает «крайний правый вывод». Однако в оригинальной статье Кнута по грамматике L R ( k ) он определяет язык L R ( k ) (на стр. 610) как язык, который «переводим слева направо с ограничением k ».L R (k )Lр(К)LR(k)L R (...
Меня интересует связь между вычислительной сложностью и иерархией Хомского в целом. В частности, если я знаю, что какая-то проблема является NP-полной, следует ли из этого, что язык этой проблемы не является контекстно-свободным? Например, проблема клики является NP-полной. Следует ли из этого, что...
Я пытаюсь научить себя использованию зубров. На странице man bison (1) говорится о зубре: Создайте детерминированный LR или обобщенный анализатор LR (GLR) с использованием таблиц LALR (1), IELR (1) или канонических LR (1). Что такое IELR-парсер? Все соответствующие статьи, которые я нашел во...
Мне было интересно, когда языки, которые содержат одинаковое количество экземпляров двух подстрок, будут регулярными. Я знаю, что язык, содержащий равное количество единиц и нулей, не является регулярным, но является языком, таким как , где = число экземпляров подстроки "001" равно числу...
Учитывая алфавит , сколько существует различных регулярных языков, которые могут быть приняты недетерминированным конечным автоматом с n состояниями?Σ={a,b}Σ={a,b}\Sigma = \{ a,b \}nnn В качестве примера рассмотрим . Затем у нас есть 2 18 различных конфигураций перехода и 2 3 различных конфигурации...
Пусть GGG - не зависящая от контекста грамматика. Строка терминалов и нетерминалов из GGG называется быть сентенциальная формой из GGG , если вы можете получить его путем применения постановки GGG нуля или более раз для начального символа SSS . Пусть SF(G)SF(G)\operatorname{SF}(G) множество...
Определим язык LLL как L = { a , b } ∗ - { w w ∣ w ∈ { a , b } ∗ }L={a,b}∗−{ww∣w∈{a,b}∗}L = \{a, b\}^* - \{ww\mid w \in \{a, b\}^*\} . Другими словами, LLL содержит слова, которые не могут быть выражены как какое-то слово, повторенное дважды. Является ли LLL контекстно-свободный или нет? Я пытался...
Мне бы очень понравилась ваша помощь в следующем: Для любого фиксированного мне нужно решить, есть ли замыкание под следующими операторами: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...
Тем не менее, многие «знаменитые» неразрешимые проблемы, по крайней мере, полуразрешимы, а их дополнение неразрешимо. Одним из примеров, прежде всего, может быть проблема остановки и ее дополнение. Тем не менее, кто-нибудь может привести пример, в котором проблема и ее дополнение неразрешимы и не...