숫자 'n'으로 나눌 수있는 바이너리 문자열을 허용하는 DFA 설계
숫자 'n'이 주어지면 10 진수에 해당하는 숫자가 'n'으로 나눌 수있는 바이너리 문자열 {0, 1}을 허용하도록 DFA를 설계하는 방법을 배워야합니다.
다른 'n'에 대해 다른 DFA가 있지만 누군가 0 <n <10으로 진행하기 위해 따라야하는 기본 접근 방식을 제공 할 수 있습니다.
아래 n에 5와 같음에 대한 답변을 작성 했지만 동일한 접근 방식을 적용하여 모든 값 n및 '모든 위치 번호 시스템'(예 : 이진, 삼항)에 대해 DFA를 그릴 수 있습니다.
먼저 'Complete DFA'라는 용어를 사용 합니다 . δ : Q × Σ → Q의 전체 도메인 에 정의 된 DFA를 'Complete DFA'라고합니다. 즉, 우리는 말할 수 있습니다. 완전한 DFA의 전환 다이어그램에는 누락 된 가장자리가 없습니다 (예 : Q의 각 상태에서 Σ의 모든 언어 기호에 대해 하나의 나가는 가장자리가 있음). 참고 : 때때로 부분 DFA를 δ ⊆ Q × Σ → Q로 정의합니다 (읽기 : DFA 정의에서 "δ : Q × Σ → Q"는 어떻게 읽음 ).
숫자 'n'으로 나눌 수있는 이진수를 허용하는 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 (% 알림 연산자)임을 의미합니다.
모든 자동 장치에서 상태의 목적은 메모리 요소와 같습니다. atomata의 상태는 팬이 'off'상태인지 'on'상태인지를 알 수있는 팬의 스위치와 같은 정보를 저장합니다. n = 5 인 경우 다음과 같이 5 개의 알림 정보에 해당하는 DFA의 5 개 상태
- 알림이 0이면 상태 q 0에 도달했습니다. 상태 q 0 은 최종 상태 (수락 상태)입니다. 또한 초기 상태입니다.
- 알림이 1 인 경우 상태 q 1 은 최종 상태가 아닙니다.
- 미리 알림이 2이면 최종 상태가 아닌 경우 q 2 상태입니다.
- 알림이 3이면 최종 상태가 아닌 경우 q 3 상태입니다.
- 알림이 4이면 최종 상태가 아닌 경우 q 4를 상태로 표시합니다.
위의 정보를 사용하여 다음과 같이 다섯 가지 상태의 전환 다이어그램 TD 그리기를 시작할 수 있습니다.
그림 -1
따라서 5 개의 나머지 값에 대해 5 개의 상태가 있습니다. 문자열 ω를 처리 한 후 end-state가 q 0 이되면 입력 문자열과 동등한 십진수를 5로 나눌 수 있음을 의미합니다. 위 그림에서 q 0 은 최종 상태를 두 개의 동심원으로 표시합니다.
또한 전이 규칙 δ : (q 0 , 0) → q 0'0' 을 상태 q 0 에서 기호 에 대한 자체 루프로 정의했습니다. 이는 모든 문자열에 해당하는 십진수 '0'가 0이고 0은로 나눌 수 있기 때문 n입니다.
2 단계 : 위의 TD가 불완전합니다. '0's의 문자열 만 처리 할 수 있습니다 . 이제 후속 숫자의 문자열을 처리 할 수 있도록 가장자리를 더 추가합니다. 아래 표는 다음 단계에 추가 할 수있는 새로운 전환 규칙을 보여줍니다.
┌──────┬──────┬─────────────┬─────────┐ │ 숫자 │ 바이너리 │ 나머지 (% 5) │ 최종 상태 │ ├──────┼──────┼─────────────┼─────────┤ │One │1 │1 │q 1 │ ├──────┼──────┼─────────────┼─────────┤ │2 개 │10 │2 │q 2 │ ├──────┼──────┼─────────────┼─────────┤ │Three │11 │3 │q 3 │ ├──────┼──────┼─────────────┼─────────┤ │4 │100 │4 │q 4 │ └──────┴──────┴─────────────┴─────────┘
- 이진 문자열을 처리하려면
'1'전환 규칙 δ : (q 0 , 1) → q 1 이 있어야합니다. - 2 :-이진 표현은
'10', end-state는 q 2 여야하며 , 처리'10'하려면 전환 규칙을 하나 더 추가하면됩니다. δ : (q 1 , 0) → q 2
Path : → (q 0 ) ─1 → ( q 1 ) ─0 → (q 2 ) - 셋 :-바이너리에서는
'11', end-state는 q 3 이고, 전환 규칙 δ : (q 1 , 1) → q 3
Path : → (q 0 ) ─1 → (q 1 ) ─1을 추가해야합니다. → (Q 3 ) - 4 :-바이너리
'100'에서 최종 상태는 q 4 입니다. TD는 이미 접두사 문자열을 처리'10'하고 새로운 전환 규칙 δ : (q 2 , 0) → q 4
경로 : → (q 0 ) ─1 → (q 1 ) ─0 → (q 2 ) ─0 → (Q 4 )
그림 -2
3 단계 : Five = 101
그림 2의 전환 다이어그램 위는 여전히 불완전하고 누락 된 모서리가 많이 있습니다. 예를 들어 δ : (q 2 , 1)- ? . 그리고 같은 문자열을 처리하려면 규칙이 있어야합니다 '101'. = 5는 5로 나눌 수
있기 때문에 위의 그림 -2에서 δ : (q 2 , 1) → q 0 을 더합니다. 경로 : → (q 0 ) ─1 → (q 1 ) ─0 → (q 2 ) ─1 → (q 0 ) 이 새로운 규칙으로 전환 다이어그램은 다음과 같이됩니다.'101''101'
그림 -3
아래 각 단계에서 다음 이진수를 선택하여 TD를 '완전한 DFA'로 얻을 때까지 누락 된 가장자리를 추가합니다.
4 단계 : 6 = 110.
우리는 처리 할 수있는 '11'그림 3과 같은 존재 TD에서 : → (Q 0 ) ─11 → (Q 3 ) ─0 → ( ? ). 6 % 5 = 1이기 때문에 이것은 하나의 규칙 δ : (q 3 , 0) → q 1 을 추가 함을 의미합니다 .
그림 -4
5 단계 : 일곱 = 111
┌──────┬──────┬─────────────┬─────────┬─────────── ─┬───────────┐ │ 숫자 │ 바이너리 │ 나머지 (% 5) │ 최종 상태 │ 경로 │ 추가 │ ├──────┼──────┼─────────────┼─────────┼─────────── ─┼───────────┤ │7 │111 │7 % 5 = 2 │q 2 │ q 0 ─11 → q 3 │ q 3 ─1 → q 2 │ └──────┴──────┴─────────────┴─────────┴─────────── ─┴───────────┘
그림 -5
6 단계 : 여덟 = 1000
┌──────┬──────┬─────────────┬─────────┬──────────┬ ─────────┐ │ 숫자 │ 바이너리 │ 나머지 (% 5) │ 최종 상태 │ 경로 │ 추가 │ ├──────┼──────┼─────────────┼─────────┼──────────┼ ─────────┤ │8 │1000 │8 % 5 = 3 │q 3 │q 0 ─100 → q 4 │ q 4 ─0 → q 3 │ └──────┴──────┴─────────────┴─────────┴──────────┴ ─────────┘
그림 -6
7 단계 : 아홉 = 1001
┌──────┬──────┬─────────────┬─────────┬──────────┬ ─────────┐ │ 숫자 │ 바이너리 │ 나머지 (% 5) │ 최종 상태 │ 경로 │ 추가 │ ├──────┼──────┼─────────────┼─────────┼──────────┼ ─────────┤ │9 │1001 │9 % 5 = 4 │q 4 │q 0 ─100 → q 4 │ q 4 ─1 → q 4 │ └──────┴──────┴─────────────┴─────────┴──────────┴ ─────────┘
그림 -7
TD-7에서 총 모서리 수는 10 == Q × Σ = 5 × 2입니다. 그리고 십진수에 해당하는 값을 5로 나눌 수있는 가능한 모든 이진 문자열을 수용 할 수있는 완전한 DFA입니다.
n으로 나눌 수있는 삼항 숫자를 허용하는 DFA 설계 :
Step-1 바이너리와 똑같습니다. figure-1을 사용하세요.
2 단계 0, 1, 2 추가
┌───────┬───────┬────────────┬─────────┬───────── ─────┐ │ Decimal │ Ternary │ Remainder (% 5) │ End-state │ Add │ ├───────┼───────┼────────────┼─────────┼───────── ─────┤ │0 │0 │0 │q0 │ δ : (q0,0) → q0 │ ├───────┼───────┼────────────┼─────────┼───────── ─────┤ │One │1 │1 │q1 │ δ : (q0,1) → q1 │ ├───────┼───────┼────────────┼─────────┼───────── ─────┤ │2 개 │2 │2 │q2 │ δ : (q0,2) → q3 │ └───────┴───────┴─────────────┴─────────┴───────── ─────┘
그림 -8
3 단계 , 3, 4, 5 추가
┌───────┬───────┬────────────┬─────────┬───────── ────┐ │ Decimal │ Ternary │ Remainder (% 5) │ End-state │ Add │ ├───────┼───────┼────────────┼─────────┼───────── ────┤ │3 개 │10 │3 │q3 │ δ : (q1,0) → q3 │ ├───────┼───────┼────────────┼─────────┼───────── ────┤ │4 │11 │4 │q4 │ δ : (q1,1) → q4 │ ├───────┼───────┼────────────┼─────────┼───────── ────┤ │5 │12 │0 │q0 │ δ : (q1,2) → q0 │ └───────┴───────┴─────────────┴─────────┴───────── ────┘
그림 -9
4 단계 6, 7, 8 추가
┌───────┬───────┬────────────┬─────────┬───────── ────┐ │ Decimal │ Ternary │ Remainder (% 5) │ End-state │ Add │ ├───────┼───────┼────────────┼─────────┼───────── ────┤ │6 │20 │1 │q1 │ δ : (q2,0) → q1 │ ├───────┼───────┼────────────┼─────────┼───────── ────┤ │Seven │21 │2 │q2 │ δ : (q2,1) → q2 │ ├───────┼───────┼────────────┼─────────┼───────── ────┤ │8 │22 │3 │q3 │ δ : (q2,2) → q3 │ └───────┴───────┴─────────────┴─────────┴───────── ────┘
그림 -10
Step-5 더하기 9, 10, 11
┌───────┬───────┬────────────┬─────────┬───────── ────┐ │ Decimal │ Ternary │ Remainder (% 5) │ End-state │ Add │ ├───────┼───────┼────────────┼─────────┼───────── ────┤ │9 │100 │4 │q4 │ δ : (q3,0) → q4 │ ├───────┼───────┼────────────┼─────────┼───────── ────┤ │10 │101 │0 │q0 │ δ : (q3,1) → q0 │ ├───────┼───────┼────────────┼─────────┼───────── ────┤ │Eleven │102 │1 │q1 │ δ : (q3,2) → q1 │ └───────┴───────┴─────────────┴─────────┴───────── ────┘
그림 -11
6 단계 : 12, 13, 14 추가
┌────────┬───────┬─────────────┬─────────┬──────── ─────┐ │ Decimal │ Ternary │ Remainder (% 5) │ End-state │ Add │ ├────────┼───────┼─────────────┼─────────┼──────── ─────┤ │12 개 │110 │2 │q2 │ δ : (q4,0) → q2 │ ├────────┼───────┼─────────────┼─────────┼──────── ─────┤ │13│111 │3 │q3 │ δ : (q4,1) → q3 │ ├────────┼───────┼─────────────┼─────────┼──────── ─────┤ │Fourteen│112 │4 │q4 │ δ : (q4,2) → q4 │ └────────┴───────┴────────────┴─────────┴──────── ─────┘
그림 -12
트랜지션 다이어그램 그림 -12의 총 에지 수는 15 = Q × Σ = 5 * 3 (전체 DFA)입니다. 그리고이 DFA는 {0, 1, 2} 이상으로 구성된 모든 문자열을 허용 할 수 있습니다. 10 진수는 5로 나눌
수 있습니다. 각 단계에서 알 수있는 경우 표에는 세 항목이 있습니다. 각 단계에서 가능한 모든 나가는 에지를 추가하기 때문입니다. 완전한 DFA를 만들기 위해 (그리고 q r 상태가 나머지를 얻 도록 가장자리를 추가합니다 r)!
추가로, 두 개의 일반 언어의 결합도 일반임을 기억하십시오. 바이너리 문자열을 허용하는 DFA를 설계해야하는 경우 10 진수에 해당하는 값은 3 또는 5로 나눌 수 있으며, 3과 5로 나눌 수있는 두 개의 개별 DFA를 그린 다음 두 DFA를 결합하여 타겟 DFA를 구성합니다 (1 <= n <= 10 10 개의 DFA를 통합해야합니다).
10 진수에 해당하는 값을 5와 3으로 나눌 수있는 바이너리 문자열을 허용하는 DFA를 그리라는 요청을 받으면 15로 나눌 수있는 DFA를 찾는 것입니다 (하지만 6과 8은 어떨까요?).
참고 :이 기술로 그린 DFA 는 숫자 와 밑수 사이에 공통 요소 가 없는 경우에만 DFA가 최소화됩니다. 예를 들어 첫 번째 예에서는 5와 2 사이, 두 번째 예에서는 5와 3 사이 n가 없으므로 위에서 구성된 두 DFA가 모두 최소화됩니다. DFA. 숫자 n및 기본 에 대한 가능한 미니 상태에 대해 자세히 알아 보려면 분할 가능성 및 상태 복잡성을b 읽어보십시오 .
아래에 Python 스크립트를 추가했습니다. Python 라이브러리 pygraphviz를 배우면서 재미있게 작성했습니다. 나는 그것을 추가하고 나는 그것이 누군가에게 도움이 될 수 있기를 바랍니다.
숫자 'n'으로 나눌 수있는 기본 'b'숫자 문자열에 대한 DFA 설계 :
따라서 위의 트릭을 적용 'b'하여 주어진 숫자로 나눌 수있는 모든 염기의 숫자 문자열을 인식하도록 DFA를 그릴 수 'n'있습니다. DFA의 총 상태 수는 n( n나머지의 경우) 엣지 수는 'b'* 'n'과 같아야합니다. 즉, 완전한 DFA : 'b'= DFA 언어의 기호 수, 'n'= 상태의 수.
위의 트릭을 사용하여 아래에서 입력 base및 .NET 용 DFA를 그리는 Python 스크립트를 작성했습니다 number. 스크립트에서 함수는 divided_by_NDFA의 전환 규칙을 base * number단계별로 채 웁니다 . 각 단계 num번호에서 num_sfunction을 사용하여 숫자 문자열 로 변환 합니다 baseN(). 각 숫자 문자열 처리를 피하기 위해 임시 데이터 구조를 사용했습니다 lookup_table. 각 단계에서 숫자 문자열의 종료 상태 num_s가 평가되고 lookup_table다음 단계에서 사용하기 위해 저장됩니다 .
DFA의 전환 그래프를 위해 Pygraphviz 라이브러리를draw_transition_graph 사용하여 함수 를 작성했습니다 (매우 사용하기 쉽습니다). 이 스크립트를 사용하려면 . 트랜지션 다이어그램에 다채로운 가장자리를 추가하기 위해 각 기호 기능 에 대해 무작위로 색상 코드를 생성 합니다.graphvizget_color_dict
#!/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 accepting number strings in base 4 those are divisible by 5
Similarly, enter base = 4 and number = 7 to generate - dfa accepting number string in base '4' those are divisible by '7'
Btw, try changing filename to .png or .jpeg.
References those I use to write this script:
➊ Function baseN from "convert integer to a string in a given numeric base in python"
➋ To install "pygraphviz": "Python does not see pygraphviz"
➌ To learn use of Pygraphviz: "Python-FSM"
➍ To generate random hex color codes for each language symbol: "How would I make a random hexdigit code generator using .join and for loops?"
I know I am quite late, but I just wanted to add a few things to the already correct answer provided by @Grijesh. I'd like to just point out that the answer provided by @Grijesh does not produce the minimal DFA. While the answer surely is the right way to get a DFA, if you need the minimal DFA you will have to look into your divisor.
Like for example in binary numbers, if the divisor is a power of 2 (i.e. 2^n) then the minimum number of states required will be n+1. How would you design such an automaton? Just see the properties of binary numbers. For a number, say 8 (which is 2^3), all its multiples will have the last 3 bits as 0. For example, 40 in binary is 101000. Therefore for a language to accept any number divisible by 8 we just need an automaton which sees if the last 3 bits are 0, which we can do in just 4 states instead of 8 states. That's half the complexity of the machine.
In fact, this can be extended to any base. For a ternary base number system, if for example we need to design an automaton for divisibility with 9, we just need to see if the last 2 numbers of the input are 0. Which can again be done in just 3 states.
Although if the divisor isn't so special, then we need to go through with @Grijesh's answer only. Like for example, in a binary system if we take the divisors of 3 or 7 or maybe 21, we will need to have that many number of states only. So for any odd number n in a binary system, we need n states to define the language which accepts all multiples of n. On the other hand, if the number is even but not a power of 2 (only in case of binary numbers) then we need to divide the number by 2 till we get an odd number and then we can find the minimum number of states by adding the odd number produced and the number of times we divided by 2.
For example, if we need to find the minimum number of states of a DFA which accepts all binary numbers divisible by 20, we do :
20/2 = 10
10/2 = 5
Hence our answer is 5 + 1 + 1 = 7. (The 1 + 1 because we divided the number 20 twice).
You can build DFA using simple modular arithmetics. We can interpret w which is a string of k-ary numbers using a following rule
V[0] = 0
V[i] = (S[i-1] * k) + to_number(str[i])
V[|w|] is a number that w is representing. If modify this rule to find w mod N, the rule becomes this.
V[0] = 0
V[i] = ((S[i-1] * k) + to_number(str[i])) mod N
and each V[i] is one of a number from 0 to N-1, which corresponds to each state in DFA. We can use this as the state transition.
See an example.
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 |
Now you can see a very simple pattern. You can actually build a DFA transition just write repeating numbers from left to right, from top to bottom, from 0 to N-1.
'programing' 카테고리의 다른 글
| CMAKE의 OS 별 지침 : 방법? (0) | 2020.11.06 |
|---|---|
| Eclipse-Android 장치 선택기에서 "알 수 없음"대상 (0) | 2020.11.06 |
| Gradle을 사용하여 jar에 리소스, 구성 파일 추가 (0) | 2020.11.06 |
| Java 8, Streams에서 중복 요소 찾기 (0) | 2020.11.06 |
| Chrome 48 이상에서 웹 보안 비활성화 (0) | 2020.11.06 |