DFA (알파벳 'a'및 'b') 설계 : 문자열의 'a'숫자는 3의 배수 여야하며 문자열에는 'aba'가 포함되지 않아야합니다.

Question

여기에 문제가 있습니다 :

내가 처음에 왔을 때

그리고 여기 추론의 내 라인 :

이

• 이 하나가 힘들 것 같다 위해 정규 표현식을 찾기 어려운
• 것 같다, 그래서 난 정규 표현식을 변환하기 위해이 경로를 따라 갈 수 없어 DFA에
• 그래서 그렇게하기로 결정했습니다. 문제의 첫 부분을 보자. 'a'의 수가 3의 배수 인 스트링을 받아 들인다. 이것은 아주 쉽다. 단지 3 개의 상태가 필요하다 : 1,2,3, 시작 상태로 1, 'a'를 입력하면 다음 상태로, 'b'상태가 지속되면 시작 상태 또한 완료 상태가됩니다. 그러나이 운동에서이 세 국가는 실제로 3 개의 '큰'국가가됩니다. 그런 다음 문제는이 '빅 스테이트의 내부 구조와 어떻게 상호 작용 하는지를 설계하는 것입니다.

나는 해결책을 찾기 위해 추측을 사용하는 것 외에 선택의 여지가 없었습니다. 다음은 제가 생각해 낸 것입니다 (1,2,3은 마무리 상태이고 3은 시작 상태이며 'a'가 입력되면 7과 9가 모두 1이됩니다). DFA 최소화도 사용했습니다. 이것에 관해, 그리고 그것이 벌써 최소다고 알았다. 그러나 교과서는 다른 해결책을 제시합니다.

그러나 나는 그것이 올바른지 이해하지 못합니다! 난 단지 그것을 알아낼 수 없다 :(. 그리고 내 솔루션이 100 % 맞는지조차 모르겠다. 도와주세요, 고마워요. :)

Answer 1

당신의 대답은 맞는 것 같습니다. 나는 신중하게 그것을 증명하지는 못했지만, 논리는 상당히 명확합니다.

def accepts(transitions,initial,accepting,s): 
    state = initial 
    for c in s: 
     state = transitions[state][c] 
    return state in accepting 

dfa = {1:{'a':4, 'b':2}, 
     2:{'a':10, 'b':3}, 
     3:{'a':4, 'b':3}, 
     4:{'a':7, 'b':5}, 
     5:{'a':10, 'b':6}, 
     6:{'a':7, 'b':6}, 
     7:{'a':1, 'b':8}, 
     8:{'a':10, 'b':9}, 
     9:{'a':1, 'b':9}, 
     10:{'a':10, 'b':10}} 

def dfaTest(s): 
    return accepts(dfa,3,{1,2,3},s) 

def valid(s): 
    return s.count('a') % 3 == 0 and not 'aba' in s 

import random 

tests = [''.join(random.choice(['a','b']) for j in range(100)) for i in range(1,1001)] 

print(all(valid(s) == dfaTest(s) for s in tests)) 

기능 accepts의 동작 this answer에 설명되어 있습니다 : 또한, 나는 그것을 테스트하는 파이썬 프로그램을 작성. 나는 당신의 다이어그램과 일치하도록 그것을 맞추었다. 스트레스 테스트를 위해 길이 범위가 1에서 1000 사이 인 100,000 개의 무작위 입력을 생성 한 다음 DFA의 출력을 조건의 직접 검증과 비교했습니다. 이 코드를 실행할 때마다 출력은 만족스러운 True입니다.

개별 문자열을 테스트하려면 :

>>> dfaTest('ababba') 
False 
>>> dfaTest('abbabba') 
True