Мне нужно научиться проектировать DFA таким образом, чтобы при любом числе n он принимал двоичные строки {0, 1}, десятичное эквивалентное число которых делится на n.
Для разных 'n' будут разные DFA, но может ли кто-нибудь дать базовый подход, которому я должен следовать, чтобы перейти к любому числу 0 <n <10.
Ниже я написал ответ для n равным 5, но вы можете применить такой же подход для рисования DFA для любого значения n и "любой системы позиционных номеров", например двоичной, тройной...
Сначала оставьте термин "Полный DFA", DFA определенный в полном домене в формате δ: Q × Σ → Q называется "Полный DFA". Другими словами, мы можем сказать; в диаграмме перехода полного DFA нет отсутствующего края (например, из каждого состояния в Q имеется один исходящий край, присутствующий для каждого символа языка в Σ). Примечание: Когда-то мы определяем partial DFA как δ ⊆ Q × Σ → Q (Читать: Как "δ: Q × Σ → Q" читается в определении DFA).
Шаг-1. Когда вы делите число ω на n, тогда напоминание может быть либо 0, 1,..., (n - 2), либо (n - 1). Если остаток 0 означает, что ω делится на n в противном случае. Таким образом, в моем DFA будет состояние q r, которое будет соответствовать остаточному значению r, где 0 <= r <= (n - 1), а общее число состояний в DFA равно n.
После обработки числовой строки ω над Σ конечное состояние q r означает, что ω% n = > r (% оператор напоминания).
В любых автоматах назначение состояния подобно элементу памяти. Состояние в атомате хранит некоторую информацию, такую как переключатель вентилятора, который может определить, находится ли вентилятор в выключенном состоянии или в состоянии 'on'. Для n = 5 пять состояний в DFA соответствуют пяти напоминаниям следующим образом:
Используя приведенную выше информацию, мы можем начать рисовать диаграмму перехода из пяти состояний следующим образом:
Рис-1
Итак, 5 состояний для 5 остаточных значений. После обработки строки ω, если конечное состояние становится q 0, это означает, что десятичный эквивалент входной строки делится на 5. В приведенном выше рисунке q 0 отмечен конечное состояние как два концентрических круг.
Кроме того, я определил правило перехода δ: (q 0, 0) → q 0 как цикл self для символа '0' в состоянии q 0, это потому, что десятичный эквивалент любой строки состоит только из '0' равен 0, а 0 является делимым на n.
Шаг-2: TD выше неполный; и может обрабатывать только строки '0' s. Теперь добавьте еще несколько ребер, чтобы он мог обрабатывать последующие строки чисел. В приведенной ниже таблице показаны новые правила перехода, которые можно добавить следующим шагом:
┌──────┬──────┬─────────────┬─────────┐ │Number│Binary│Remainder(%5)│End-state│ ├──────┼──────┼─────────────┼─────────┤ │One │1 │1 │q1 │ ├──────┼──────┼─────────────┼─────────┤ │Two │10 │2 │q2 │ ├──────┼──────┼─────────────┼─────────┤ │Three │11 │3 │q3 │ ├──────┼──────┼─────────────┼─────────┤ │Four │100 │4 │q4 │ └──────┴──────┴─────────────┴─────────┘
'1' должно существовать правило перехода δ: (q 0, 1) → q 1'10', конечное состояние должно быть q 2, а для обработки '10' нам просто нужно добавить еще одно правило перехода δ: (q 1, 0) → q 2'11', конечное состояние - q 3, и нам нужно добавить правило перехода δ: (q 1, 1 ) → д <юг > 3суб > '100', конечное состояние - q 4. TD уже обрабатывает строку префикса '10', и нам просто нужно добавить новое правило перехода: (q 2, 0) → q 4
Рис-2
Шаг-3: Пять = 101
Над диаграммой перехода на рисунке-2 все еще неполна и имеется много недостающих краев, для примера не определен переход для δ: (q 2, 1) - ?. И правило должно присутствовать для обработки строк, таких как '101'.
Поскольку '101'= 5 делится на 5 и принимает '101', я добавлю δ: (q 2, 1) → q 0 в приведенном выше рисунке-2.
Путь: → (q 0) ─1 → (д <суб > 1суб > ) ─0 → (д <суб > 2суб > ) ─1 → (д <суб > 0суб > )
с этим новым правилом диаграмма перехода становится следующей:
Рис-3
Ниже на каждом шаге я выбираю следующий последующий двоичный номер, чтобы добавить недостающий край, пока я не получу TD как "полный DFA".
Шаг-4: Шесть = 110.
Мы можем обрабатывать '11' в настоящем TD на рисунке 3 как: → (q 0) ─11 → (q 3) ─0 → (). Поскольку 6% 5 = 1, это означает добавить одно правило: (q 3, 0) → q 1.
Рис-4
Шаг-5: Семь = 111
┌──────┬──────┬─────────────┬─────────┬────────────┬───────────┐ │Number│Binary│Remainder(%5)│End-state│ Path │ Add │ ├──────┼──────┼─────────────┼─────────┼────────────┼───────────┤ │Seven │111 │7 % 5 = 2 │q2 │ q0─11→q3│ q3─1→q2 │ └──────┴──────┴─────────────┴─────────┴────────────┴───────────┘
Рис-5
Шаг-6: Восемь = 1000
┌──────┬──────┬─────────────┬─────────┬──────────┬─────────┐ │Number│Binary│Remainder(%5)│End-state│ Path │ Add │ ├──────┼──────┼─────────────┼─────────┼──────────┼─────────┤ │Eight │1000 │8 % 5 = 3 │q3 │q0─100→q4 │ q4─0→q3 │ └──────┴──────┴─────────────┴─────────┴──────────┴─────────┘
Рис-6
Шаг-7: Девять = 1001
┌──────┬──────┬─────────────┬─────────┬──────────┬─────────┐ │Number│Binary│Remainder(%5)│End-state│ Path │ Add │ ├──────┼──────┼─────────────┼─────────┼──────────┼─────────┤ │Nine │1001 │9 % 5 = 4 │q4 │q0─100→q4 │ q4─1→q4 │ └──────┴──────┴─────────────┴─────────┴──────────┴─────────┘
Рис-7
В TD-7 общее число ребер равно 10 == Q × Σ = 5 × 2. И это полный DFA, который может принимать все возможные двоичные строки, то десятичный эквивалент делится на 5.
Шаг-1 Точно так же, как и для двоичного кода, используйте цифру-1.
Шаг-2 Добавить нуль, один, два
┌───────┬───────┬─────────────┬─────────┬──────────────┐ │Decimal│Ternary│Remainder(%5)│End-state│ Add │ ├───────┼───────┼─────────────┼─────────┼──────────────┤ │Zero │0 │0 │q0 │ δ:(q0,0)→q0 │ ├───────┼───────┼─────────────┼─────────┼──────────────┤ │One │1 │1 │q1 │ δ:(q0,1)→q1 │ ├───────┼───────┼─────────────┼─────────┼──────────────┤ │Two │2 │2 │q2 │ δ:(q0,2)→q3 │ └───────┴───────┴─────────────┴─────────┴──────────────┘
Рис-8
Шаг-3 Добавить три, четыре, пять
┌───────┬───────┬─────────────┬─────────┬─────────────┐ │Decimal│Ternary│Remainder(%5)│End-state│ Add │ ├───────┼───────┼─────────────┼─────────┼─────────────┤ │Three │10 │3 │q3 │ δ:(q1,0)→q3 │ ├───────┼───────┼─────────────┼─────────┼─────────────┤ │Four │11 │4 │q4 │ δ:(q1,1)→q4 │ ├───────┼───────┼─────────────┼─────────┼─────────────┤ │Five │12 │0 │q0 │ δ:(q1,2)→q0 │ └───────┴───────┴─────────────┴─────────┴─────────────┘
Рис-9
Шаг-4 Добавить шесть, семь, восемь
┌───────┬───────┬─────────────┬─────────┬─────────────┐ │Decimal│Ternary│Remainder(%5)│End-state│ Add │ ├───────┼───────┼─────────────┼─────────┼─────────────┤ │Six │20 │1 │q1 │ δ:(q2,0)→q1 │ ├───────┼───────┼─────────────┼─────────┼─────────────┤ │Seven │21 │2 │q2 │ δ:(q2,1)→q2 │ ├───────┼───────┼─────────────┼─────────┼─────────────┤ │Eight │22 │3 │q3 │ δ:(q2,2)→q3 │ └───────┴───────┴─────────────┴─────────┴─────────────┘
Рис-10
Шаг-5 Добавить девять, десять, одиннадцать
┌───────┬───────┬─────────────┬─────────┬─────────────┐ │Decimal│Ternary│Remainder(%5)│End-state│ Add │ ├───────┼───────┼─────────────┼─────────┼─────────────┤ │Nine │100 │4 │q4 │ δ:(q3,0)→q4 │ ├───────┼───────┼─────────────┼─────────┼─────────────┤ │Ten │101 │0 │q0 │ δ:(q3,1)→q0 │ ├───────┼───────┼─────────────┼─────────┼─────────────┤ │Eleven │102 │1 │q1 │ δ:(q3,2)→q1 │ └───────┴───────┴─────────────┴─────────┴─────────────┘
Рис-11
Шаг-6 Добавить двенадцать, тринадцать, четырнадцать
┌────────┬───────┬─────────────┬─────────┬─────────────┐ │Decimal │Ternary│Remainder(%5)│End-state│ Add │ ├────────┼───────┼─────────────┼─────────┼─────────────┤ │Twelve │110 │2 │q2 │ δ:(q4,0)→q2 │ ├────────┼───────┼─────────────┼─────────┼─────────────┤ │Thirteen│111 │3 │q3 │ δ:(q4,1)→q3 │ ├────────┼───────┼─────────────┼─────────┼─────────────┤ │Fourteen│112 │4 │q4 │ δ:(q4,2)→q4 │ └────────┴───────┴─────────────┴─────────┴─────────────┘
<Т411 >
Рис-12
Общее количество ребер в диаграмме перехода -12 составляет 15 = Q × Σ = 5 * 3 (полный DFA). И этот DFA может принимать все строки, состоящие из {0, 1, 2}, эти десятичные эквиваленты делятся на 5.
Если вы заметили на каждом шаге, в таблице есть три записи, потому что на каждом шаге я добавляю все возможные исходящие края из состояния, чтобы сделать полный DFA (и добавляю ребро, чтобы получить состояние q r для остатка r)!
Чтобы добавить далее, помните, что объединение двух регулярных языков также является регулярным. Если вам нужно создать DFA, который принимает двоичные строки, то десятичный эквивалент делится на 3 или 5, затем нарисуйте два отдельных DFA для делимых на 3 и 5, затем объедините оба DFA для построения целевого DFA (для 1 <= n <= 10 у вас есть союз 10 DFA).
Если вас попросят нарисовать DFA, который принимает двоичные строки таким образом, что десятичный эквивалент делится на 5 и 3, то вы ищите DFA с делимыми на 15 (но как насчет 6 и 8?).
Примечание: DFA, нарисованные с помощью этой техники, будут минимизированы DFA только тогда, когда нет общего коэффициента между числом n и базой, например. в первом примере нет от 5 до 2 или от 5 до 3 во втором примере, поэтому обе построенные выше DFA являются минимизированными DFA. Если вам интересно узнать о возможных мини-состояниях для числа n и base b, прочитайте документ: Делимость и государственная сложность.
ниже Я добавил Python script, я написал его для удовольствия, изучая Python library pygraphviz. Я добавляю его, я надеюсь, что он может быть полезен кому-то в чем-то.
Таким образом, мы можем применить вышеприведенный трюк, чтобы нарисовать DFA для распознавания числовых строк в любой базе 'b', которые делятся на заданное число 'n'. В этом DFA общее число состояний будет n (для n остатков), а число ребер должно быть равно 'b' * 'n' — то есть полный DFA: 'b' = количество символов на языке DFA и 'n' = количество состояний.
Используя вышеприведенный трюк, ниже я написал Python Script для рисования DFA для ввода base и number. В script функция divided_by_N заполняет правила перехода DFA в шагах base * number. В каждом шаге-num я конвертирую num в числовую строку num_s с помощью функции baseN(). Чтобы избежать обработки каждой числовой строки, я использовал временную структуру данных lookup_table. На каждом шаге конечное состояние для числовой строки num_s оценивается и сохраняется в lookup_table для использования на следующем шаге.
Для графа перехода DFA я написал функцию draw_transition_graph с помощью библиотеки Pygraphviz (очень проста в использовании). Чтобы использовать этот Script, вам необходимо установить graphviz. Чтобы добавить красочные ребра в диаграмму перехода, я произвольно генерирует цветовые коды для каждой функции символа get_color_dict.
Рис-2
Рис-3
Рис-4
Рис-5
Рис-6
Рис-7
#!/usr/bin/env python
import pygraphviz as pgv
from pprint import pprint
from random import choice as rchoice
def baseN(n, b, syms="0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"):
""" converts a number `n` into base `b` string """
return ((n == 0) and syms[0]) or (
baseN(n//b, b, syms).lstrip(syms[0]) + syms[n % b])
def divided_by_N(number, base):
"""
constructs DFA that accepts given `base` number strings
those are divisible by a given `number`
"""
ACCEPTING_STATE = START_STATE = '0'
SYMBOL_0 = '0'
dfa = {
str(from_state): {
str(symbol): 'to_state' for symbol in range(base)
}
for from_state in range(number)
}
dfa[START_STATE][SYMBOL_0] = ACCEPTING_STATE
# `lookup_table` keeps track: 'number string' -->[dfa]--> 'end_state'
lookup_table = { SYMBOL_0: ACCEPTING_STATE }.setdefault
for num in range(number * base):
end_state = str(num % number)
num_s = baseN(num, base)
before_end_state = lookup_table(num_s[:-1], START_STATE)
dfa[before_end_state][num_s[-1]] = end_state
lookup_table(num_s, end_state)
return dfa
def symcolrhexcodes(symbols):
"""
returns dict of color codes mapped with alphabets symbol in symbols
"""
return {
symbol: '#'+''.join([
rchoice("8A6C2B590D1F4E37") for _ in "FFFFFF"
])
for symbol in symbols
}
def draw_transition_graph(dfa, filename="filename"):
ACCEPTING_STATE = START_STATE = '0'
colors = symcolrhexcodes(dfa[START_STATE].keys())
# draw transition graph
tg = pgv.AGraph(strict=False, directed=True, decorate=True)
for from_state in dfa:
for symbol, to_state in dfa[from_state].iteritems():
tg.add_edge("Q%s"%from_state, "Q%s"%to_state,
label=symbol, color=colors[symbol],
fontcolor=colors[symbol])
# add intial edge from an invisible node!
tg.add_node('null', shape='plaintext', label='start')
tg.add_edge('null', "Q%s"%START_STATE,)
# make end acception state as 'doublecircle'
tg.get_node("Q%s"%ACCEPTING_STATE).attr['shape'] = 'doublecircle'
tg.draw(filename, prog='circo')
tg.close()
def print_transition_table(dfa):
print("DFA accepting number string in base '%(base)s' "
"those are divisible by '%(number)s':" % {
'base': len(dfa['0']),
'number': len(dfa),})
pprint(dfa)
if __name__ == "__main__":
number = input ("Enter NUMBER: ")
base = input ("Enter BASE of number system: ")
dfa = divided_by_N(number, base)
print_transition_table(dfa)
draw_transition_graph(dfa)
Выполнить его:
~/study/divide-5/script$ python script.py
Enter NUMBER: 5
Enter BASE of number system: 4
DFA accepting number string in base '4' those are divisible by '5':
{'0': {'0': '0', '1': '1', '2': '2', '3': '3'},
'1': {'0': '4', '1': '0', '2': '1', '3': '2'},
'2': {'0': '3', '1': '4', '2': '0', '3': '1'},
'3': {'0': '2', '1': '3', '2': '4', '3': '0'},
'4': {'0': '1', '1': '2', '2': '3', '3': '4'}}
~/study/divide-5/script$ ls
script.py filename.png
~/study/divide-5/script$ display filename
Вывод:
DFA, принимающий числовые строки в базе 4, делится на 5
Аналогичным образом введите base = 4 и number = 7 для генерации - dfa, принимающих числовую строку в базе "4" , которые делятся на "7"
Btw, попробуйте изменить filename на .png или .jpeg.
<суб > Ссылки, которые я использую для написания этого script:
➊ Функция baseN из "преобразовать целое число в строку в заданной числовой базе в python"
➋ Чтобы установить "pygraphviz": "Python не видит pygraphviz"
➌ Чтобы изучить использование Pygraphviz: "Python-FSM"
➍ Чтобы генерировать случайные шестнадцатеричные цветовые коды для каждого символа языка: "Как создать случайный генератор кода hexdigit с использованием .join и для циклов?"
Суб >
Я знаю, что я довольно поздно, но я просто хотел добавить несколько вещей к уже правильному ответу, предоставленному @Grijesh. Я хотел бы просто указать, что ответ, предоставленный @Grijesh, не дает минимального DFA. Хотя ответ, безусловно, является правильным способом получить DFA, если вам нужен минимальный DFA, вам придется заглянуть в ваш делитель.
Как, например, в двоичных числах, если делитель является степенью 2 (т.е. 2 ^ n), то минимальное количество требуемых состояний будет n + 1. Как бы вы создали такой автомат? Просто просмотрите свойства двоичных чисел. Для числа, скажем, 8 (что равно 2 ^ 3), все его кратные будут иметь последние 3 бита как 0. Например, 40 в двоичном формате - 101000. Поэтому для того, чтобы язык принял любое число, делящееся на 8, нам просто нужно автомат, который видит, если последние 3 бита равны 0, что мы можем сделать только в 4 состояниях вместо 8 состояний. Эта половина сложности машины.
Фактически, это может быть распространено на любую базу. Для тройной системы базовых номеров, если, например, нам нужно создать автомат для делимости с 9, нам просто нужно увидеть, будут ли последние 2 числа ввода равными 0. Это может быть снова выполнено только в трех состояниях.
Хотя, если делитель не настолько особенный, нам нужно пройти только с помощью ответа @Grijesh. Например, в двоичной системе, если мы возьмем делители 3 или 7 или, может быть, 21, нам нужно будет иметь только такое количество состояний. Поэтому для любого нечетного числа n в двоичной системе нам нужно n состояний для определения языка, который принимает все кратные n. С другой стороны, если число четное, но не мощность 2 (только в случае двоичных чисел), то нам нужно разделить число на 2, пока не получим нечетное число, и тогда мы сможем найти минимальное число состояний через добавляя нечетное число и количество раз мы разделили на 2.
Например, если нам нужно найти минимальное число состояний DFA, которое принимает все двоичные числа, делящиеся на 20, мы делаем:
20/2 = 10
10/2 = 5
Следовательно, наш ответ равен 5 + 1 + 1 = 7. (1 + 1, потому что мы дважды разделили число 20).
Вы можете построить DFA с помощью простой модульной арифметики. Мы можем интерпретировать w являющуюся строкой k-арных чисел, используя следующее правило
V[0] = 0
V[i] = (S[i-1] * k) + to_number(str[i])
V[|w|] - это число, которое представляет w. Если изменить это правило, чтобы найти w mod N, это правило станет.
V[0] = 0
V[i] = ((S[i-1] * k) + to_number(str[i])) mod N
и каждый V[i] является одним из числа от 0 до N-1, что соответствует каждому состоянию в DFA. Мы можем использовать это как переход состояния.
См. Пример.
k = 2, N = 5
| V | (V*2 + 0) mod 5 | (V*2 + 1) mod 5 |
+---+---------------------+---------------------+
| 0 | (0*2 + 0) mod 5 = 0 | (0*2 + 1) mod 5 = 1 |
| 1 | (1*2 + 0) mod 5 = 2 | (1*2 + 1) mod 5 = 3 |
| 2 | (2*2 + 0) mod 5 = 4 | (2*2 + 1) mod 5 = 0 |
| 3 | (3*2 + 0) mod 5 = 1 | (3*2 + 1) mod 5 = 2 |
| 4 | (4*2 + 0) mod 5 = 3 | (4*2 + 1) mod 5 = 4 |
k = 3, N = 5
| V | 0 | 1 | 2 |
+---+---+---+---+
| 0 | 0 | 1 | 2 |
| 1 | 3 | 4 | 0 |
| 2 | 1 | 2 | 3 |
| 3 | 4 | 0 | 1 |
| 4 | 2 | 3 | 4 |
Теперь вы можете увидеть очень простой шаблон. Фактически вы можете построить переход DFA, просто записывая повторяющиеся числа слева направо, сверху вниз, от 0 до N-1.
постройте dfa, который примет строку на {a, b}, где число делится на 3