이 유한 한 오토 마톤을 어떻게 구축합니까?

Question

나는 개별 수학 테스트를 위해 공부하고 있으며이 운동을 발견 할 수없는 것을 발견했습니다.

"알파벳 시그마 (Alphabet Sigma = {0,1,2}의 언어에 대한 기본 유한 한 오토 마톤) (DFA, NFA, NFA-LAMBDA)를 구축하십시오.

나는이 정규 표현과 관련된 두 가지 언어를 연결하는 것과 같은 두 언어를 연결하는 Kleene의 정리를 사용해 보았습니다.

(00 U 11 U 22 U 02 U 20)* - 짝수 요소

이것으로

(22 U 1111 U 222 U 2222)* - 합계가 3보다 큰 것

이것은 의미가 있습니까? 내 성분이 연약하다고 생각합니다.

Answer 1

나는 당신의 표명이 약간 퍼지라고 생각하기 때문에 아마도 나는 완전히 오해하고 있습니다. 그렇다면 다음을 무시하십시오. 당신이 아직 없어요 :

• * '0 이상'을 의미한다고 가정합니다. 그러나 sum> = 3 인 문자열 중 하나가 발생해야합니다. A + ( '1 배 이상')가 필요하다고합니다.
• 112와 211은 sum> = 3 인 문자열 목록에서 누락되었습니다.
• 이 목록의 222 및 2222는 불필요합니다.
• 이 모든 문자열은 0 초로 임의적으로 산재 할 수 있습니다.
• 00의 합은 0의 합보다 더 이상 없다.

---

편집하다: 이건 어때 (acc 유일한 수용 상태입니다. 도트 소스):

Automaton http://student.science.uva.nl/~sschroev/so/885411.png

주에서 ㅏ 그리고 씨 문자열 합은 항상 홀수입니다. 주에서 시작, 비 그리고 acc 합은 항상 짝수입니다. 또한, AT 시작 합은 0, at입니다 비 2와 AT입니다 디 > = 4입니다. 이것은 다소 쉽게 입증 될 수 있습니다. 따라서 수용 상태 acc 모든 기준을 충족합니다.

편집 2 : 나는 이것이 요청 된 언어를 받아들이는 정규식이라고 말하고 싶습니다.

0*(2|(1(0|2)*1))(0*(2|(1(0|2)*1))+

Answer 2

이것이 귀하의 질문에 대답하는지 확실하지 않지만 : 정규 표현을 제출해야합니까? 아니면 FSM이할까요?

어쨌든 FSM을 먼저 그리는 것이 도움이 될 수 있습니다. 생각한다 이것은 올바른 DFA입니다.

fsm http://img254.imageshack.us/img254/5324/fsm.png

이 경우, 정규 표현식을 구성 할 때 ( "Regex"를 프로그래밍하는 것과는 다른 구문이 있습니다) :

0* "0만큼 여러 번"을 표시합니다. 문자열의 0이 기계 상태를 변경하지 않기 때문에 이것은 의미가 있습니다. (FSM에서 0을 참조하십시오.

합계에서 최소 4 개에 도달 할 때까지 "112"또는 "22"등의 다양한 조합을 설명해야합니다.

합계가 3보다 크고 심지어 (0 | 2)*가 최종 상태로 유지할 것입니다. 그렇지 않으면 (합계> 3, 홀수) 수락 상태에있게하려면 1 (0 | 2)*와 같은 것이 필요합니다.

(이것이 도움이되는지 또는 옳은지 모르겠습니다. 그러나 그것은 시작일지도 모릅니다!)

Answer 3

스테판이 안내하는 각 표현은 다음과 같습니다.

(0* u 2* u 11)* - 짝수 합계

이것으로

(22 u 11 u 222 u 112 u 211 u 121)+ - 합계가 3보다 큰 것

더 단순화 될 수 있는지 모르겠습니다. 자동 설계에 도움이 될 것입니다.

Answer 4

나는 국가 측면에서 생각하기가 더 쉽다는 것을 알았습니다. 5 개의 상태를 사용하십시오 : 0, 1, 2, 짝수, 홀수

전환 :

State, Input -> New State

(0, 0) -> 0
(0, 1) -> 1
(0, 2) -> 2

(1, 0) -> 1
(1, 1) -> 2
(1, 2) -> ODD

(2, 0) -> 2
(2, 1) -> ODD
(2, 2) -> EVEN

(ODD, 0) -> ODD
(ODD, 1) -> EVEN
(ODD, 2) -> ODD

(EVEN, 0) -> EVEN
(EVEN, 1) -> ODD
(EVEN, 2) -> EVEN

만 수용 상태 일뿐 만합니다.