Вопросы о математических устройствах, которые считывают символ входного потока по символу и используют карту перехода состояний для создания выходного потока, возможно, с использованием вторичного хранилища.
Преобразование регулярных выражений в (минимальный) NFA, который принимает тот же язык, легко с помощью стандартных алгоритмов, например , алгоритма Томпсона . Другое направление кажется более утомительным, и иногда получающиеся выражения являются грязными. Какие существуют алгоритмы для...
Я согласен, что машина Тьюринга может решать «все возможные математические задачи». Но это потому, что это всего лишь машинное представление алгоритма: сначала сделайте это, затем сделайте это, наконец, выведите это. Я имею в виду все, что разрешимо, может быть представлено алгоритмом (потому что...
Есть много способов доказать, что язык не является регулярным , но что мне нужно сделать, чтобы доказать, что какой-то язык является регулярным? Например, если мне дано, что регулярно, как я могу доказать, что следующее регулярно?LLLL'L′L' L': = { w ∈ L : u v = w для u ∈ Σ*∖ L и v ∈...
Смотрите в конце этого поста некоторые пояснения к определению (ям) автоматов с минимальной кучей. Можно представить себе использование различных структур данных для хранения информации для использования конечными автоматами. Например, автоматы с отложенным запуском хранят информацию в стеке, а...
В этом ответе упоминается Обычный язык может быть распознан конечным автоматом. Для контекстно-свободного языка требуется стек, а для контекстно-зависимого языка требуются два стека (что эквивалентно тому, что для него требуется полная машина Тьюринга) . Я хотел знать относительно правды смелой...
Давайте назовем контекстно-свободный язык детерминированным тогда и только тогда, когда он может быть принят детерминированным автоматом, и недетерминированным в противном случае. Давайте назовем контекстно-свободный язык по своей сути неоднозначным тогда и только тогда, когда все...
В теории автоматов мы все читаем автоматы как конечные автоматы с самого начала. Я хочу знать, почему автоматы конечны? Чтобы было понятно, что в автомате конечного - алфавит, язык, строки, созданные с помощью регулярных выражений, или что? И есть ли (в теории) какие-нибудь не конечные...
Видя, что в иерархии Хомского языки типа 3 могут распознаваться конечным автоматом без внешней памяти (т. Е. Конечным автоматом), тип 2 - конечным автоматом с одним стеком (т. Е. Автоматом с понижением) и тип 0 - конечный автомат с двумя стеками (или, что эквивалентно, лента, как в случае с...
В моем классе студент спросил, можно ли нарисовать все конечные автоматы без пересекающихся граней (кажется, все мои примеры это делали). Конечно, ответ отрицательный, очевидный автомат для языка имеет структуру , полный граф на пяти узлах , Юваль показал похожую структуру для родственного языка.{x...
Я только что закончил первую главу « Введение в теорию вычислений » Майкла Сипсера, в которой объясняются основы конечных автоматов. Он определяет обычный язык как что-либо, что может быть описано конечными автоматами. Но я не мог найти, где он объясняет, почему обычный язык называется «обычный»?...
У меня есть набор пар. Каждая пара имеет форму (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Насколько я могу судить, ценности не обитают . Функция с...
Я делаю презентацию о машинах Тьюринга, и я хотел бы рассказать о FSM, прежде чем представлять машины Тьюринга. Проблема в том, что я действительно не знаю, что ОЧЕНЬ отличается друг от друга. Вот что я знаю, это другое: FSM имеет последовательные состояния в зависимости от соответствующего...
Этот вопрос был перенесен из переполнения стека, поскольку на него можно ответить в разделе «Информатика в стеке». Мигрировал 7 лет назад . Я создал лексер и анализатор простого регулярного выражения, чтобы взять регулярное выражение и сгенерировать его дерево анализа. Создание...
Является ли следующий языковой контекст бесплатным? 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, слово в этом языке также...
Мы знаем, что DFAs эквивалентны NFAs в силе выразительности; Существует также известный алгоритм для преобразования NFA в DFA (к сожалению, я теперь знаю изобретателя этого алгоритма), который в худшем случае дает нам состояния, если у нашего NFA было S состояний.2S2S2^SSSS Мой вопрос: что...
Автомат - это абстрактная модель цифрового компьютера. Цифровые компьютеры полностью детерминированы; их состояние в любое время однозначно предсказуемо из входных данных и исходного состояния. Когда мы пытаемся моделировать реальные системы, зачем включать недетерминизм в теорию автоматов?...
Есть ли какой-нибудь "естественный" язык, который неразрешим? под «естественным» я подразумеваю язык, определяемый непосредственно свойствами строк, а не с помощью машин и их эквивалентов. Другими словами, если язык выглядит как где - это ТМ, DFA (или регулярное выражение), КПК (или грамматика) и...
При наличии не зависящей от контекста грамматики G существует недетерминированный автомат Pushdown N, который принимает именно тот язык, который принимает G. (и наоборот) Там может также существовать детерминированный магазинный автомат D , который принимает именно язык G принимает слишком. Это...
Все недетерминированные конечные автоматы можно превратить в эквивалентные детерминированные конечные автоматы. Однако детерминированные конечные автоматы допускают только одну стрелку на символ, указывающую из состояния. Следовательно, его штаты должны входить в состав множества штатов НФА....