Описание тега pushdown-automaton
Автомат выталкивания (КПК) - это конечный автомат с добавленной стековой памятью. Это математическое описание алгоритма разбора контекстно-свободных языков.
2
ответа
Построение автомата пуш-ап из контекстно-свободной грамматики
Из этого раздела вики-статьи о КПК я получил приблизительное представление о процессе создания КПК из данного CFG. То, что эта статья не проясняет, является шагом, необходимым, когда есть несколько производственных правил для одного нетерминала. Нап…
04 ноя '13 в 06:29
3
ответа
КПК принимает язык строк, содержащий больше а, чем б
Создайте КПК для распознавания следующего языка: язык строк, содержащих больше а, чем б Я боролся с этим вопросом уже несколько дней, похоже, у меня полная психическая блокада. Сможет ли кто-нибудь дать какое-нибудь руководство или руководство, как …
29 мар '12 в 17:06
1
ответ
Конечные автоматы, автоматы Pushdown и примеры машин Тьюринга
Я ищу хороший источник примеров конечных автоматов, автоматов раскрытия и задач машины Тьюринга (для решения вручную, вручную). Я искал вокруг, но не нашел ничего особенного, поэтому мне интересно, есть ли у кого-нибудь хорошие примеры. Заранее спас…
28 авг '12 в 17:30
3
ответа
Могут ли автоматы с выпадающим меню иметь нулевые конечные состояния?
В соответствии с вопросом, могут ли автоматы с выпадением иметь нулевые конечные состояния?
30 мар '13 в 21:28
0
ответов
КПК (Pushdown Automata) Трассировка - я не понимаю ответ
Я изучаю КПК и узнаю, как отследить набор символов или алфавит для данного нарисованного КПК. Тем не менее, я не знаю, как отследить для данного КПК (в письменной форме) см. Ниже. Итак, это письменный КПК: Q={s0,f} Σ={a,b,c} Γ={S,X,a,b,c} F={f} δ={(…
14 янв '16 в 22:05
2
ответа
Путаница в поиске первой и последующей левой рекурсивной грамматики
Недавно я столкнулся с проблемой поиска первого и последующего S->cAd A->Ab|a Здесь я путаюсь с первым из A, который является правильным {a}, {empty,a}, поскольку в производстве A есть рекурсия слева. Я запутался, стоит ли включать пустую стро…
30 дек '14 в 06:28
2
ответа
Как спроектировать автомат
Как бы я спроектировал карманный компьютер, который принимает сбалансированные скобки и скобки, например ([][]), мне трудно начинать. Мне нужна помощь в написании функций перехода для этой проблемы. Любая помощь приветствуется
19 ноя '12 в 00:10
6
ответов
Разработайте КПК со всеми строками 0 и 1 так, чтобы число 1 было вдвое больше, чем 0
Во время подготовки к последним экзаменам я нашел этот вопрос в " Теории автоматов, языке и вычислениях" Дж. Хопкрофта, Р. Мотвани, Дж. Уллмана на странице 222. КПК должен принять строку, в которой число цифр 1 равно удвоенному числу 0, и, если я не…
16 май '15 в 16:52
1
ответ
Частота подсчета букв в КПК
Я пытаюсь создать КПК или CFG, который принимает все слова, где E является наиболее распространенной буквой. Сыр и чай будут на языке, например. Я уверен, что этот язык не зависит от контекста, но я не могу создать для него КПК. Это возможно?
26 окт '15 в 23:15
1
ответ
Ошибка компиляции детерминированного автомата нажатия в C (DPDA)
Я читал о том, как реализовать DPDA, и нашел этот код по следующему Интернет-адресу: http://code.zhoubot.com/, Этот файл c реализует простые автоматы. Автоматы прочитают описание своих функций перехода и ввода, выполнят его вычисления на входе, а за…
16 июл '11 в 21:48
1
ответ
Докажите, что КПК с k стеками распознается по Тьюрингу
Когда-то это было домашнее задание, но сейчас я использую его для пересмотра; Но нет решения этой проблемы. Любые советы будут высоко ценится. Вопрос задается следующим образом: "Пусть k-PDA будет автоматом с пониженным доступом с доступом к k стека…
26 апр '15 в 20:45
1
ответ
Подход к поиску контекстно-свободной грамматики более сложных языков
У меня проблемы с приближением к следующей проблеме. Дайте контекстно-свободную грамматику для следующего языка: {x#y | x,y in {0,1}* and |x| != |y|} Как лучше всего подойти к этому вопросу? Сейчас я просто использую интуицию для решения подобных во…
26 апр '15 в 10:26
1
ответ
Автоматы и арифметические выражения
Я пытаюсь выяснить, как сделать арифметические выражения в Pushdown Automata?(PDA), например, L=W|W= Bm Cn-m. Что я думаю сделать, это нажать As, затем pop Bs, а затем либо pop As. C или B с C в зависимости от того, что осталось. Например, aaabbc (н…
30 окт '15 в 17:49
2
ответа
Является ли bin(n)bin(2^(k+1) * n + 1)^R контекстом бесплатно?
bin - самое короткое число в двоичной системе Является ли bin(n)bin(2^(k+1) * n + 1)^R контекстом бесплатно? k, n принадлежит натуральным числам. Я знаю, что bin(n)bin(n + 1)^R не зависит от контекста, но я не знаю, как решить bin(n)bin(2^(k+1) * n …
11 фев '19 в 06:28
1
ответ
Недетерминированные пушдаунные автоматы и палиндром
Мне нужно найти палиндромы в тексте (слова имеют длину <= 6 и состоят из строчных и прописных букв) и использовать для этого автоматы Pushdown, но, к сожалению, я не совсем знаком с этой темой. Может ли кто-нибудь объяснить мне, как я могу запрограм…
28 фев '19 в 15:39
1
ответ
Создание автомата нажатия для обеспечения двух одинаковых вхождений подстроки
Меня просят создать автомат сжатия (PDA), чтобы обеспечить наличие равного количества подстрок 01 как 10 подстрок, а также, что число подстрок, равное 00, равно 11 подстрокам. Вот проблема: Пусть L1 ⊆ {0, 1}* будет языком строк, которые имеют то же …
29 мар '16 в 07:02
1
ответ
В пуш-вниз стека автоматов является общим со всеми другими состояниями?
Я хочу знать, что в пуш-ап стека автомат делится со всеми другими состояниями или нет?
07 сен '14 в 08:55
2
ответа
НПД для языкового числа а меньше или равно в 3 раза больше числа б
Я пытаюсь построить НПД для L = {w ∈ {a, b} * | n a (w) <= 3 * n b (w)}. Это означает, что для каждого b может быть не более 3 a. Прежде всего, это то, что я сделал до сих пор. Из начального состояния мы помещаем один " a " в стек. (в конце дня нам …
11 ноя '16 в 15:49
0
ответов
Принятие языка детерминированными автоматами
Это язык a^n b^m, где n>=m,m>=1, принятый детерминистскими автоматами. Я пытался, но всегда оставался позади в конце стека.
09 дек '17 в 18:40
1
ответ
Очередь автоматов может имитировать любые автоматы Pushdown?
Я работаю над теоретическим заданием, и этот вопрос действительно заставил меня задуматься. Вопрос звучит так: покажите, что любой автомат с нажатием кнопки может быть смоделирован с помощью автоматов очереди. Сначала я думал, что это будет просто, …
24 ноя '12 в 02:03