Вопросы по теме 'computation-theory'
NFA в DFA вопрос
Во-первых, это не вопрос алгоритма преобразования NFA в DFA.
Известно (и доказано), что DFA, эквивалентный NFA, имеет не более 2 n состояний, хотя в большинстве случаев он будет иметь более или менее такое же количество состояний, что и NFA....
8374 просмотров
schedule
13.02.2022
Контекстно-свободная грамматика для языка
У меня проблема со следующим языком:
Я должен написать контекстно-свободную грамматику:
который описывает это. Я уже сделал несколько упражнений, но это действительно сложно для меня. Я сижу часами без полезного подхода. Было бы...
441 просмотров
schedule
14.10.2023
Является ли Big Theta Notation эффективной мерой эффективности алгоритма, когда ожидаемый размер входных данных невелик?
Я искал повсюду информацию о Big-Theta, и я думаю, что пришел к приличному пониманию этого. Однако остается вопрос: является ли Big Theta Notation эффективной мерой эффективности алгоритма, когда ожидаемый размер входных данных невелик?
Я думаю,...
379 просмотров
schedule
20.10.2023
Может ли язык принимать бесконечные числа
У меня есть вопрос, может ли язык принимать бесконечные числа
Я должен уменьшить Lempty до Linf
where Lempty ={e|L(Pe) is null}
Linf={e|L(Pe) is infinite}
так я могу определить программу P, как это
"
input n
Run Pe on 1...n for n...
168 просмотров
schedule
16.06.2022
Каким будет DFA для (0+1)*?
Я нарисовал эту схему ниже. Но я хочу быть уверенным в ответе, так как оператор + и * сбивают с толку.
_
| \
--> q_|- 0,1,E
Здесь мой DFA имеет только одно состояние q. Оба 0,1,empty перенаправляются на сам q.
1416 просмотров
schedule
17.12.2023
Может ли неконтекстно-свободный язык L быть контекстно-свободным при итерации?
Язык L не является контекстно-свободным языком.
Но может ли L* быть контекстно-свободным языком?
349 просмотров
schedule
03.10.2022
Описание действия машины Тьюринга
Я пытаюсь ответить в третьей части на следующий вопрос:
Я нарисовал следующую диаграмму состояний:
Согласно решению, машина «добавляет 1 к двоичному числу с его младшим битом в крайнем левом положении на ленте». Я не понимаю, что это...
636 просмотров
schedule
14.12.2023
в чем именно причина остановки
Проблема остановки заключается в том, что при наличии входных данных и программы не существует алгоритма, который мог бы решить, будет ли программа остановлена. Это делает эту проблему неразрешимой. Мое неправильное понимание проблемы остановки...
49 просмотров
schedule
07.02.2022
Напишите регулярные выражения для следующих языков по алфавиту
Напишите регулярные выражения для следующих языков в алфавите ∑ = {0, 1}:
Язык всех строк, которые не заканчиваются на 11.
Язык всех строк, не содержащих подстроку 01. Также нарисуйте конечный автомат для каждого из вышеописанных языков.
930 просмотров
schedule
26.05.2024
Что такое лемма о накачке и как ее выполнить?
Итак, у меня есть вопрос по лемме прокачки A{www|w ∈ {a,b}*} У меня есть правильный ответ, но я не совсем уверен, как это работает. Я дам ответ, чтобы люди знали, с чем я собираюсь
Предположим, что A представляет собой REG, пусть p будет длиной...
212 просмотров
schedule
20.09.2022
Откуда мы знаем, что NP-полные задачи являются самыми сложными в NP?
Я понимаю, что если вы можете сделать полиномиальное сокращение времени из «каждой» проблемы, это доказывает, что проблема по крайней мере так же сложна, как и любая проблема в NP. Кроме того, как мы узнаем, что обнаружили все проблемы в NP? Не...
746 просмотров
schedule
12.07.2022
Функциональное завершение означает завершение по Тьюрингу?
Я заметил, что И, ИЛИ, НЕ эти три логических элемента являются функционально завершенными, это означает, что я могу представить любую таблицу истин только этими тремя элементами.
Итак, я хочу знать, могу ли я представить какую-либо вычислимую...
196 просмотров
schedule
23.09.2022
как преобразовать DFA в регулярное выражение?
Читаю книгу: введение в теорию вычислений и застрял на этом примере.
Преобразуйте DFA в эквивалентное выражение, сначала преобразовав его в GNFA (обобщенный недетерминированный конечный автомат), а затем преобразовав GNFA в регулярное выражение....
620 просмотров
schedule
17.04.2023
можно ли найти хэш md5 пароля без фактического наличия исходного пароля
Я просто возился с некоторым кодом на python и понял, что не так уж сложно узнать, что такое пароль, если у вас есть md5 (в основном атака грубой силы, вменение md5, просмотр миллионов паролей, преобразование их в md5 и проверка на соответствие, а...
1628 просмотров
schedule
01.04.2022
Быстрее сохранить разделение в переменной и использовать переменную или дважды пересчитать?
Представьте, что у вас есть следующие типы данных (числа заполняются как аргументы):
Целое ‹- Вес
Float ‹- Высота
Цель состоит в том, чтобы вычислить индекс b ody- m ass i , который будет иметь вид 23,13 и т. Д....
56 просмотров
schedule
16.02.2022
Пассивное обучение в конечных автоматах
Я читаю следующий абзац в книге «Основы машинного обучения» https://cs.nyu.edu/~mohri/mlbook/ на странице 362 (книги).
Сейчас я новичок в концепции DFA, но у меня есть некоторый опыт. У меня есть вопросы по абзацу.
Зачем им нужен...
84 просмотров
schedule
30.04.2022
Как стек автоматов с нажатием вниз может принять строку бесконечно большого размера?
Рассмотрим для данного языка L={a^n b^n (степень a n и степень b n) |n›=1}, поэтому в соответствии с языком он должен содержать строки, такие что a и b должны иметь одинаковую частоту в непрерывном мода, теперь предположим, что строка приходит так,...
45 просмотров
schedule
18.05.2023
Если L и L-дополнение рекурсивно перечислимы, то почему L не может быть регулярным языком?
Ниже вопрос был задан в документе GATE 2008:
Если L и L' (дополнение L) рекурсивно перечислимы, то L равно ?
a) Обычный b) CFL c) CSL d) Рекурсивный
Правильным вариантом был вариант (d), и я согласен с тем, что это правда. Но мой вопрос:...
537 просмотров
schedule
02.05.2023
