Я понял логику машины Тьюринга. Когда мне дают машину Тьюринга, я могу понять, как она работает и как останавливается. Но когда просят построить машину Тьюринга, это сложнее. Есть ли простой способ найти ответ на такие вопросы, как: Construct...

Я новичок в CFG, Может ли кто-нибудь дать мне совет по созданию CFG, который генерирует какой-либо язык Например L = {a m b n | m >= n} Что я получил: S o -> a | aS o | aS 1 | e S 1 -> b | bS 1 | e но я...

У меня проблемы с решением/доказыванием этой проблемы. Любые идеи, пожалуйста?

Я читаю книгу о языках и автоматах, и я не понимаю машины Тьюринга. Я без проблем научился использовать DFA NFA и Pushdown Automata. Может кто-нибудь объяснить, что это делает? B = {w#w|w ∈ {0, 1}*} Следующий рисунок содержит несколько снимков...

Цель: найти способ формального определения грамматики, которая распознает элементы из множества 0 или 1 раз в любом порядке. Впоследствии я хочу разобрать его и также сгенерировать AST. Например: скажем, набор допустимых строк на моем языке равен...

У меня есть следующая грамматика в файле Bison: lst: ID COMMA lst | ID | /*empty*/ plst: lst SEMICOLON lst | SEMICOLON lst | lst ГДЕ первое правило фактически пытается отобразить список идентификаторов, таких как...

Учитывая следующий язык: L 1 = { (ab) n | n ≥ 0 } То есть L 1 = { ε ab, abab, ababab, abababab, ... } Вопрос в том, чтобы найти язык L 1 2 . Я предполагаю, что это равно { (ab) 2n | n ≥ 0 } . Это правильно?...

Я пытаюсь описать регулярное выражение на английском здесь, и допустим у нас есть для (b(bb)*)* вы бы сказали: zero or more b's или мы можем иметь (a(aa)*b(bb)*)* вы бы сказали: odd number of a's that end in odd number of b's...

Учитывая языки L 1 ={a n b 2m |n,m≥1} L 2 ={a n b 3n |n≥0} L = L 1 ∩ L 2 Я знаю, что L 1 — это обычный язык, а L 2 может быть представлен КПК. Но я не понимаю ответа, в котором говорится, что L это {a 2n b 6n |n≥1} ....

Является ли WW, где W принадлежит {a,b}*, контекстно-свободным языком? Если да, пожалуйста, предоставьте КПК для него.

Я использую F* 0.9.6.0 и не могу заставить эту простую программу пройти проверку подтипов: module Test open FStar.String let minlen s n = strlen s >= n let maxlen s n = strlen s <= n let isLanguageValid s = (minlen s 2) && (maxlen...

Мне нужно написать CFG для языка ниже: L = { w ∈ Σ* | w is a regular expression over a binary alphabet } Я придумал: S = SΣ* | ε X = S | ε Я начинаю дисциплину сейчас, и если это не правильно, я был бы признателен за объяснение. Большое...