Вопросы, связанные с формальными языками, грамматикой и теорией автоматов
Преобразование регулярных выражений в (минимальный) NFA, который принимает тот же язык, легко с помощью стандартных алгоритмов, например , алгоритма Томпсона . Другое направление кажется более утомительным, и иногда получающиеся выражения являются грязными. Какие существуют алгоритмы для...
Люди часто говорят, что парсеры LR (k) более мощные, чем парсеры LL (k) . Эти заявления в большинстве случаев расплывчаты; в частности, следует ли сравнивать классы для фиксированного или объединения по всем ? Так как на самом деле ситуация? В частности, меня интересует, как вписывается LL...
Есть много способов доказать, что язык не является регулярным , но что мне нужно сделать, чтобы доказать, что какой-то язык является регулярным? Например, если мне дано, что регулярно, как я могу доказать, что следующее регулярно?LLLL'L′L' L': = { w ∈ L : u v = w для u ∈ Σ*∖ L и v ∈...
Смотрите в конце этого поста некоторые пояснения к определению (ям) автоматов с минимальной кучей. Можно представить себе использование различных структур данных для хранения информации для использования конечными автоматами. Например, автоматы с отложенным запуском хранят информацию в стеке, а...
Похоже, что на этом сайте люди часто исправляют других за запутанные «алгоритмы» и «проблемы». В чем разница между этими? Как я узнаю, когда мне следует рассмотреть алгоритмы и рассмотреть проблемы? И как они связаны с понятием языка в теории формального...
Давайте назовем контекстно-свободный язык детерминированным тогда и только тогда, когда он может быть принят детерминированным автоматом, и недетерминированным в противном случае. Давайте назовем контекстно-свободный язык по своей сути неоднозначным тогда и только тогда, когда все...
Видя, что в иерархии Хомского языки типа 3 могут распознаваться конечным автоматом без внешней памяти (т. Е. Конечным автоматом), тип 2 - конечным автоматом с одним стеком (т. Е. Автоматом с понижением) и тип 0 - конечный автомат с двумя стеками (или, что эквивалентно, лента, как в случае с...
Я только что закончил первую главу « Введение в теорию вычислений » Майкла Сипсера, в которой объясняются основы конечных автоматов. Он определяет обычный язык как что-либо, что может быть описано конечными автоматами. Но я не мог найти, где он объясняет, почему обычный язык называется «обычный»?...
Для обычного языка , пусть с п ( Ь ) быть число слов в L длины п . Используя Jordan канонической форму (применительно к Неаннотированным матрицам перехода некоторого DFA для L ), можно показать , что при достаточно большой п , с п ( L ) = K Е я = 1 P я ( п ) Л н I , где Р я являются сложными...
У меня есть набор пар. Каждая пара имеет форму (x, y), так что x, y принадлежат целым числам из диапазона [0,n). Итак, если n равно 4, то у меня есть следующие пары: (0,1) (0,2) (0,3) (1,2) (1,3) (2,3) У меня уже есть пары. Теперь я должен построить комбинацию, используя n/2пары, чтобы ни одно из...
Википедия, а также другие источники, которые я обнаружил в списке voidтипа C как тип единицы, а не пустой тип. Мне кажется, что это сбивает с толку, так как мне кажется, что оно voidлучше подходит под определение пустого / нижнего типа voidНасколько я могу судить, ценности не обитают . Функция с...
Есть много способов доказать, что язык не является контекстно-свободным, но как мне доказать, что язык не является контекстно-независимым? Какие методы существуют, чтобы доказать это? Очевидно, один из способов - показать контекстную грамматику для языка. Существуют ли какие-либо систематические...
Является ли следующий языковой контекст бесплатным? 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, слово в этом языке также...
Вот гипотеза для регулярных выражений: Для регулярного выражения пусть длина | R | быть количеством символов в нем, игнорируя скобки и операторы. Например | 0 ∪ 1 | = | ( 0 ∪ 1 ) ∗ | = 2ррR| R ||р||R|| 0∪1 | = | (0∪1 )*| =2|0∪1|знак равно|(0∪1)*|знак равно2|0 \cup 1| = |(0 \cup 1)^*| = 2 Гипотеза:...
Я искал в сети ответ на этот вопрос, и кажется, что все безоговорочно знают ответ, кроме меня. Предположительно, это потому, что заботятся только люди, получившие высшее образование по этому предмету. Я, с другой стороны, был брошен в глубокий конец для школьного задания. Мой вопрос, как именно...
Конструктивистская логика - это система, которая исключает Закон Исключенной Среды, а также Двойное Отрицание как аксиомы. Это описано в Википедии здесь и здесь . В частности, система не допускает доказательств от противного. Мне интересно, кто-нибудь знаком с тем, как это влияет на результаты,...
Мы знаем, что DFAs эквивалентны NFAs в силе выразительности; Существует также известный алгоритм для преобразования NFA в DFA (к сожалению, я теперь знаю изобретателя этого алгоритма), который в худшем случае дает нам состояния, если у нашего NFA было S состояний.2S2S2^SSSS Мой вопрос: что...
Этот вопрос был перенесен из теоретического обмена стеков информатики, поскольку на него можно ответить в обмене стеков информатики. Мигрировал 6 лет назад . Я встречал много определений рекурсивных и рекурсивно перечислимых языков. Но я не мог понять, кто они. Может кто-нибудь сказать мне, что...
EPAL, язык четных палиндромов, определяется как язык, генерируемый следующей однозначной контекстно-свободной грамматикой: S→aaS→aaS \rightarrow a a S→bbS→bbS \rightarrow b b S→aSaS→aSaS \rightarrow a S a S→bSbS→bSbS \rightarrow b S b EPAL - это «проклятие» многих алгоритмов синтаксического...
Как следует из названия, на прошлых выходных я потратил пару часов, пытаясь обдумать класс языков, сопоставляемых с Perl-совместимыми регулярными выражениями, за исключением любого оператора сопоставления, который позволяет выполнять произвольный код внутри шаблона . Если вы не знаете, что такое...