формальные языки, грамматика, теория автоматов
Я пересматривал Теорию вычислений для забавы, и этот вопрос меня мучил некоторое время (забавно, никогда не думал об этом, когда я изучал Теорию автоматов в моем старшекурснике). Итак, «почему» мы точно изучаем детерминированные и недетерминированные конечные автоматы (DFA / NFAs)? Итак, вот...
Иерархия Хомского (–Schützenberger) используется в учебниках теоретической информатики, но она, очевидно, охватывает только очень небольшую часть формальных языков (REG, CFL, CSL, RE) по сравнению с полной диаграммой зоопарка сложности . Играет ли иерархия какую-либо роль в текущих исследованиях? Я...
Я думаю о следующей проблеме: я хочу найти регулярное выражение, которое соответствует определенному набору строк (например, действительные адреса электронной почты) и не соответствует другим (недействительные адреса электронной почты). Предположим, что под регулярным выражением мы подразумеваем...
Реальные компьютеры имеют ограниченную память и ограниченное число состояний. Так что они по сути конечные автоматы. Почему теоретические компьютерные ученые используют машины Тьюринга (и другие эквивалентные модели) для изучения компьютеров? Какой смысл изучать эти гораздо более сильные модели по...
Всегда есть способ применения в темах, связанных с теоретической информатикой. Но учебники и курсы бакалавриата обычно не объясняют причину, по которой теория автоматов является важной темой и имеет ли она применение на практике. Поэтому у студентов бакалавриата могут возникнуть проблемы с...
Спросите даже кого-то, имеющего опыт работы в области компьютерных наук, что такое регулярное выражение, и ответ, вероятно, выйдет за пределы возможности быть в пределах досягаемости конечного автомата. Например, «регулярное выражение» /^1?$|^(11+?)\1+$/ созданная известной личностью Perl Абигейл...
Мне нужна книга по теории конечных автоматов с множеством примеров, которые я могу использовать для самостоятельного изучения и подготовки к
В предисловии к своим очень влиятельным книгам «Автоматы, языки и машины» (тома A, B) Самуэль Эйленберг обещал соблазнительно изложить тома C и D, посвященные «иерархии (называемой рациональной иерархией) нерациональных явлений ... используя рациональные отношения как инструмент для сравнения....
Хорошо известно, что регулярное выражение может быть распознано недетерминированным конечным автоматом, размер которого пропорционален регулярному выражению, или детерминированным FA, который потенциально экспоненциально больше. Кроме того, учитывая строку и регулярное выражение , NFA может...
Является ли язык { } не зависит от контекста или нет?aibjck | i≠j,i≠k,j≠kaibjck | i≠j,i≠k,j≠ka^{i}b^{j}c^{k} ~|~ i \neq j, i \neq k, j \neq k Я понял, что столкнулся почти со всеми вариантами этого вопроса с различными условиями относительно отношений между i, j и k, но не с этим. Я думаю, что это...
Зафиксируйте целое число и алфавит . Определим как совокупность всех конечных автоматов на состояниях с начальным состоянием 1. Мы рассматриваем все DFA (не только связанные, минимальные или невырожденные); таким образом,...
В качестве стороннего проекта я пишу язык с использованием Python. Я начал с использования клона flex / bison под названием Ply, но столкнулся с трудностями, которые я могу выразить с помощью этого стиля грамматики, и мне не интересно взламывать свой язык из-за несоответствия импеданса с...
Мне было интересно, существует ли «лучший» (я объясню в каком смысле) алгоритм для запуска из DFA и построения регулярного выражения такого что , чем в книге Хопкрофта и Уллмана (1979). Там наборы используются для представления наборов строк, которые переводят DFA из состояния в без прохождения...
Рассмотрим недетерминированные конечные автоматы A=(Q,Σ,δ,q0,F)A=(Q,Σ,δ,q0,F)A = (Q, \Sigma, \delta, q_0, F) и функцию f(n)f(n)f(n) . Дополнительно определим Σ≤k=⋃i≤kΣiΣ≤k=⋃i≤kΣi\Sigma^{\leq k} = \bigcup_{i \leq k} \Sigma^i . Теперь давайте проанализируем следующее утверждение: Если...
Мы определяем язык регулярного дерева, как в книге TATA : это множество деревьев, принятых недетерминированным автоматом конечного дерева (глава 1) или, что эквивалентно, множество деревьев, порожденных грамматикой регулярного дерева (глава 2). Оба формализма очень похожи на хорошо известные...
Учитывая регулярный язык (NFA, DFA, грамматика или регулярное выражение), как можно посчитать количество принимаемых слов на данном языке? Интерес представляют как «ровно n букв», так и «не более n букв». У Маргареты Акерман есть две статьи по теме перечисления слов, принятых NFA, но я не смог...
Во многих работах с использованием контекстно-свободных грамматик (CFG) примеры таких грамматик, представленные там, часто допускают простую характеристику языка, который они генерируют. Например: S→aaSbS→aaSbS \to a a S b S→S→S \to генерирует {a2ibi|i≥0}{a2ibi|i≥0}\{ a^{2i} b^i | i \geq 0\} ,...
1) Какова связь между статической типизацией и формальными грамматиками, если таковые имеются? 2) В частности, возможно ли, чтобы линейный ограниченный автомат проверял, хорошо ли, например, написана программа на C ++ или SML? Вложенный стек? 3) Есть ли естественный способ выразить статические...
Я недавно читал о парсере Earley и думаю, что это один из самых элегантных алгоритмов, которые я когда-либо видел. Однако алгоритм в его традиционном смысле является распознавателем, а не анализатором, то есть он может определять, соответствует ли строка определенному CFG, но не генерировать для...
Для любого языка над определите На словах состоит из всех , для которых есть одинаковой длины таким образом, что .Σ * L +1 / +2 = { х ∈ Σ * : х у ∈ L , у ∈ Σ | х | } . L 1 / 2 х у й у ∈ LLLLΣ*Σ∗\Sigma^*L1 / 2= { x ∈ Σ*: х у∈ L , y∈ Σ| х |} .L1/2={x∈Σ∗:xy∈L,y∈Σ|x|}.L_{1/2} = \{x \in \Sigma^* : xy\in...