Вопросы о наборе языков (эквивалентно), описываемых бесконтекстными грамматиками или принимаемыми (недетерминированными) автоматами.
В Интернете есть много определений о том, что такое контекстно-свободная грамматика, но ничего, что я нахожу, не удовлетворяет мою основную проблему: В каком контексте он свободен? Чтобы исследовать, я погуглил «контекстно-зависимую грамматику», но мне так и не удалось найти смысл «контекста»....
Некоторое время я изучал компиляторы и искал, что означает «контекст» в грамматике и что означает, что грамматика должна быть «контекстно-свободной», но безрезультатно. Так может кто-нибудь помочь с...
У меня есть набор пар. Каждая пара имеет форму (x, y), так что x, y принадлежат целым числам из диапазона [0,n). Итак, если n равно 4, то у меня есть следующие пары: (0,1) (0,2) (0,3) (1,2) (1,3) (2,3) У меня уже есть пары. Теперь я должен построить комбинацию, используя n/2пары, чтобы ни одно из...
Есть много способов доказать, что язык не является контекстно-свободным, но как мне доказать, что язык не является контекстно-независимым? Какие методы существуют, чтобы доказать это? Очевидно, один из способов - показать контекстную грамматику для языка. Существуют ли какие-либо систематические...
Является ли следующий языковой контекст бесплатным? L = { u x v y| У , v , х , у∈ { 0 , 1 }+,|u|=|v|,u≠v,|x|=|y|,x≠y}L={uxvy∣u,v,x,y∈{0,1}+,|u|=|v|,u≠v,|x|=|y|,x≠y}L = \{ uxvy \mid u,v,x,y \in \{ 0,1 \}^+, |u| = |v|, u \neq v, |x| = |y|, x \neq y\} Как указывает sdcvvc, слово в этом языке также...
Моя проблема в том, как я могу доказать, что грамматика однозначна? У меня есть следующие грамматики: S→statement∣if expression then S∣if expression then S else SS→statement∣if expression then S∣if expression then S else SS → statement ∣ \mbox{if } expression \mbox{ then } S ∣ \mbox{if } expression...
При наличии не зависящей от контекста грамматики G существует недетерминированный автомат Pushdown N, который принимает именно тот язык, который принимает G. (и наоборот) Там может также существовать детерминированный магазинный автомат D , который принимает именно язык G принимает слишком. Это...
При рассмотрении компьютерных моделей вычислений иерархия Хомского обычно характеризуется (по порядку) конечными автоматами, автоматами со спуском, линейными связанными автоматами и машинами Тьюринга. Для первого и последнего уровней 1 (обычные языки и рекурсивно перечислимые языки) не имеет...
Языки без контекста не закрыты в дополнении, мы это знаем. Насколько я понимаю, контекстно-свободные языки, которые являются подмножеством a*б*a∗b∗a^*b^* для некоторых букв а , бa,ba,b , закрыты в дополнении (!?) Вот мой аргумент. Каждый CF язык LLL имеет полулинейный образ Париха π( L ) = { ( m ,...
Давайте рассмотрим две не зависящие от контекста грамматики и G 2 и зададим следующий вопрос: Являются ли L ( G 1 ) = L ( G 2 ) , то есть эквивалентны ли эти две грамматики?грамм1грамм1G_1грамм2грамм2G_2L ( G1) = L ( G2)L(грамм1)знак равноL(грамм2)L(G_1) = L(G_2) В общем, эта проблема неразрешима....
Существует ли алгоритм / систематическая процедура для проверки того, является ли язык свободным от контекста? Другими словами, учитывая язык, указанный в алгебраической форме (подумайте о чем-то вроде ), проверьте, является ли язык контекстно-свободным или нет , Представьте, что мы пишем...
Может ли контекстно-свободная грамматика включать «мертвые состояния» из автомата, такие как G = ( { a , b , c } , { A , B , C} , { A → a B , B → b , B → C, C→с C} , A )?граммзнак равно({a,б,с},{A,В,С},{A→aВ,В→б,В→С,С→сС},A)?G = \big(\{a, b, c\}, \{A, B, C\}, \{A\to aB, B\to b, B\to C, C\to cC\},...
Мне интересно, возможно ли это вообще, так как . Поэтому КПК, который может отличить слово от остальной части вполне может принять его , что звучит противоречиво для меня. w ∈ { a n b n c n ∣ n ≥ 0 } { a ∗ b ∗ c ∗ }{anbncn∣n≥0}∉CFL{anbncn∣n≥0}∉CFL\{a^n b^n c^n \mid n \geq 0\} \not\in...
Говорят, что пересечение языка L, не зависящего от контекста, с обычным языком M всегда является контекстно-свободным. Я понял доказательство создания перекрестного продукта, но до сих пор не понимаю, почему он не контекстный, а не регулярный. Язык, генерируемый таким пересечением, имеет строки,...
Обратите внимание, что это вопрос, связанный с обучением на курсе CS в университете, это НЕ домашняя работа, и его можно найти здесь под экзаменом осень 2011 года2. Вот два вопроса, на которые я смотрю с прошлого экзамена. Похоже, они связаны, первое: Позволять FINITECFG={<G>∣G is a Context...
Таким образом, в основном L удовлетворяет условиям леммы накачки для КЛЛ, но не является КЛЛ (это возможно в соответствии с определением
Пусть 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 контекстно-свободный или нет? Я пытался...
Я знаю, что существуют нерегулярные языки, поэтому является регулярным, но все примеры, которые я могу найти, являются контекстно-зависимыми, но не контекстно-свободными.L∗L∗L^* Если нет ни одного, как вы это...
У меня проблема с этим упражнением: Пусть G будет следующей неоднозначной грамматикой для λ-исчисления: E → v | λv.E | EE | (E) где E - единственный нетерминальный символ, λv.E представляет абстракцию относительно переменной v в E, а EE представляет приложение. Определите LL (1) грамматику G ′ так,...