Я почти уверен, что он у меня действительно есть, но он имеет 42 правила построения и плохо обобщает. Как я могу сделать это с меньшим количеством правил построения? Язык {a,b}*, где число a в пять раз превышает количество b. Я знаю, что для...

{WW} — разрешимый, но не свободный от контекста {WW^R} — свободный от контекста, но не в обычном языке Σ* — обычный язык Как определить, к какому классу они принадлежат?

Чтобы нарисовать граф переходов NPDA, который принимает L, я думаю, что можно начать эту задачу, прочитав a , написав a , затем переместившись вправо, а затем проделав то же самое для b , чтобы было какое-то состояние q 1 , который получает...

Может ли каждое состояние быть конечным при построении детерминированных автоматов с выталкиванием вниз? У меня возникли проблемы, в частности, с созданием DPDA, который принимает следующий язык: L = { 0 n 1 m | п ≥ м} Мой подход состоит в...

Предположим, у нас есть этот PA: -> q0 (e, e -> $) --> q1 Где: q0 — конечное и начальное состояние; e это эпсилон (пусто); и q1 — другое состояние. Если бы автомат прочитал слово e , он мог бы либо совершить переход к q1,...

У меня есть КПК и некоторые регулярные выражения. Есть ли какой-нибудь алгоритм, который я могу использовать, чтобы убедиться, что мой КПК принимает строки, которые являются подмножеством того, что может быть создано регулярным выражением?...