{a, b, c} 알파벳으로 DFA 작성

Question

알파벳 {a, b, c}에 DFA를 작성하여 세 개의 연속 된 문자로 된 모든 문자열 세트를 허용합니다. 나는 다른 방법을 많이 시도

AAA, BBB, CCC, abbb, caaac, ccbbbcc, aaabbbc을 ... 그리고 더 우아한 방법이 있는지 궁금 해서요 거대한 그림입니다 :

는 그래서 받아 들일 수 이거하고 있니?

Answer 1

먼저 제목에 NFA가 표시되지만 질문 본문에는 DFA가 나와 있습니다. 나는 그 문제가 왜 중요한지 설명하기 위해 두 가지 방법으로 모두 대답 할 것입니다.

먼저 NFA를 고려하십시오. 우리는 같은 종류의 세 연속 기호가있는 문자열 만 허용하려고합니다. 세 개의 기호가 있으므로 세 가지 방법이 있습니다 (문자열이 세 개의 연속 된 기호가 처음 나오는 이후에 받아 들여진다는 것을 알고 있다고 가정 할 때). 우리는 무엇이든을 볼 수 있고, 그 다음에 똑같은 상징의 세 개를 볼 수 있습니다. NFA가 적어 쉽게 :

• Q0 :

   __ 
      /\     __ 
      |/a,b,c   /\ 
      V/    |/a,b,c 
  --->q0--a->q1-a->q4-a-\ V/
      | \-b->q2-b->q5-b-->(q7) 
      \---c->q3-c->q6-c-/ 
  

  우리의 상태는 다음과 같이 초기 상태는의, B 년대와 C의의 접두사를 받아들입니다. 에서만 문자열로 BB와 문자열이 방문 할 수있다 상태

• Q3, Q6 :
• Q1, Q4 :에서만 문자열로 AA와 문자열 방문한
• Q2, Q5 수있다 상태 그 상태 수도 서브 문자열로 cc가있는 문자열 만 방문하십시오.
• q7 : 부분 문자열로 aaa, bbb 또는 ccc가있는 문자열로만 방문 할 수있는 수용 상태. 입력 문자열의 일부 접두사를 읽은 후

는 NFA nondeterministically 가지가 않는 경우, Q7을 입력하고 접미사로 남아있을 수 있습니다 무엇이든을 받아, 입력 문자열은 AAA가 포함되어 있는지 여부를 확인 BBB 또는 CCC십시오.

최소 DFA를 얻으려면 Myhill-Nerode 정리에 따라 문자열을 사전 식으로 검사하여 이미 고려한 문자열과 구분할 수 있는지 확인하고 DFA 한 상태를 시간.

1. 빈 문자열은 구별 할 수 있습니다. L에있는 문자열을 얻기 위해 L의 임의의 문자열이 올 수 있습니다. 상태 [e]를 호출합니다.
2. 문자열 a는 빈 문자열과 구별 할 수 있습니다. 그 뒤에는 aaL + L이 붙어 L에서 문자열을 얻을 수 있습니다. 상태 [a]를 호출하십시오.
3. 문자열 b와 c도 마찬가지로 구분할 수 있으며 상태 [b]와 [c]를 갖습니다.
4. 문자열 [aa]는 L로 문자열을 가져 오기 위해 aL + L이 올 수 있으므로 구별 할 수 있습니다. 상태 [aa]를 호출하십시오.
5. 문자열 bb 및 cc도 마찬가지로 구분할 수 있으며 상태 [bb] 및 [cc]를 갖습니다.
6. ba 및 ca는 a와 구별 할 수 없습니다. 그 뒤에는 L과 같은 문자열이 계속 나옵니다.
7. ab/cb와 ac/bc는 각각 b와 c와 구별 할 수 없습니다.
8. aaa는 아무 것도 따라 올 수 있으며 언어의 문자열로 남아 있기 때문에 구별 할 수 있습니다.
9. bbb와 ccc는 aaa와 구별 할 수 없습니다. 길이 3
10. 모든 다른 스트링은 A, B, C, AA, BB 또는 CC로부터 구별 AAA 시작 길이 4
11. 모든 문자열 짧은 문자열로부터 구별 (이 확인)
(이 확인) 우리가 구별 문자열의 부족 때문에

, 우리는 우리가 최소한의 DFA 필요한 모든 상태를 나열했습니다 알고 우리는 답변을 적어 수 있습니다

   +---a--->[a]<---a----+ 
       | +-c--->[c]<---c-+ | 
       | |    | | 
    +----b--->[b]-------b------>[bb]---b----+ 
    |          | 
    |   +---b--->[b]<---b----+  | +--+ 
    |   | +-c--->[c]<---c-+ |  | | a,b,c 
    |   | |    | |  V V | 
--->[e]---a--->[a]-------a------>[aa]---a--->[aaa]--+ 
    |          ^
    |   +---a--->[a]<---a----+  | 
    |   | +-b--->[b]<---b-+ |  | 
    |   | |    | |  | 
    +----c--->[c]-------c------>[cc]---c----+ 

을 (주 [A], [B] 와 [c]는 다이어그램을 더 예쁘게 만들기 위해 두 번씩 복제됩니다. 전이 그래프가 평면이 아니며 ASCII 아트에서 렌더링하는 것이 혼란 스럽습니다).

이것은 우리가 적어 놓은 간단한 NFA와 동일한 수의 상태를 가지고 있음을 주목하십시오. 이것은 비 결정 성을 제거한 것입니다.

• 전환을 얻는 방법은 상태 [x]에서 기호 [s]로 상태 [y]로 이동하는 방법은 xs가 z와 구별 할 수 없는지 확인하는 것입니다.
• 초기 상태는 항상 [e]입니다.
• 방법은 우리는 그 문자열 전자 수 올 수 있습니다 L.
에서 문자열을 얻을 당신이 --a을 작업하는 방법