Найти грамматику двоичного числа, делимого на 5 с 1 как MSB

Как я могу найти грамматику двоичного числа, делимого на 5 с 1 как MSB и найти обращение L

Итак, мне нужна грамматика, которая генерирует числа, как..

5 = 101
10 = 1010
15 = 1111
20 = 10100
25 = 110011

и так далее

Источник

2 ответа

Решение

Я предполагаю, что это домашнее задание, а вы просто хотите намекнуть.

Давайте рассмотрим несколько похожий вопрос, но в базе 10. Как мы можем написать CFG для чисел, кратных 3.

На первый взгляд это кажется маловероятным, но на самом деле все довольно просто. Начнем с наблюдения, что:

10k ≅ 1 (mod 3) для любого неотрицательного целого числа k,

Теперь рассмотрим целое число dδ, где d десятичная цифра и δ является (возможно, пустой) последовательностью десятичных цифр. Мы пишем |δ| на длину δ, Понятно, что:

d × 10|δ| ≅ d (mod 3), поскольку 10|δ| ≅ 1 (mod 3),

Но dδ = d × 10|δ| + δ

Так dδ ≅ d + δ (mod 3),

Теперь предположим, что у нас есть три языка, L0, L1 а также L2, где Li это язык всех десятичных чисел, которые i mod 3,

Я собираюсь злоупотреблять нотацией, написав операторы включения набора, как если бы они были грамматическими произведениями, сбивающими с толку языки и грамматики. Прости меня. Кажется, легче читать, если вы сосредоточены на CFG.

Для однозначных чисел мы можем определить:

D0 → 0 | 3 | 6 | 9
D1 → 1 | 4 | 7
D2 → 2 | 5 | 8

и тогда мы имеем:

L0 → D0
L1 → D1
L2 → D2

По вышеупомянутым арифметическим тождествам мы также имеем:

L0 → D0 L0 | D1 L2 | D2 L1
L1 → D0 L1 | D1 L0 | D2 L2
L2 → D0 L2 | D1 L1 | D2 L0

Это CFG, так что мы сделали. (Ну, почти готово. Было бы полезно доказать, что L0 ⋃ L1 ⋃ L2 это набор всех строк в алфавите {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, но это легко по индукции по длине строки.)

На самом деле, не только Li контекстно-свободные языки; на самом деле это обычные языки. Таким образом, существует регулярное выражение, эквивалентное каждому из них. Например, я считаю, что L0 является:

(D0|D2D0*D1|(D1|D2D0*D2)(D0|D1D0*D2)*(D2|D1D0*D1))*

Теперь, как это можно повторить для двоичных чисел, кратных 5?

Источник

Вы можете легко прийти с грамматикой, которая даст вам все четные умножения 5 (10,20,30...) теперь, после того, как у вас есть это - вы можете констатировать строку '101' и получить почти все нечетное умножение.. вы будете

надеюсь, это поможет - это, вероятно, не самый умный способ, хотя

Источник
Другие вопросы по тегам