p_ce1052   9달 전

preview 다음과 같이 상태천이도를 그려서 냈더니 틀렸습니다를 받았습니다. 모든 경우를 고려한 것 같은데 어디가 문제일까요?

djm03178   9달 전

DFA를 만드신 거라면 28번째 줄처럼 같은 입력에 대해 두 군데를 가보는 일이 있어서는 안 됩니다.

p_ce1052   9달 전

DFA에 대해서는 잘 모르지만 위 경우에 7번 정점에 있을 때 문자가 1이라면 그대로 남아있어도 되고 1번으로 가도 둘 중 어느 경우만 맞으면 답이라고 생각해서 저렇게 하였습니다. 7번 정점이 (100+1+)패턴의 1+ 를 처리할 때인데 뒤에 1을 붙여서 앞의 패턴을 안끝내도 되고 끝내고 새로운 패턴을 시작할 수도 있어서 저렇게 해도 맞지 않나요?

djm03178   9달 전

반례는 100101입니다. YES가 나와야 합니다.

bupjae   9달 전

7번 노드가 잘못되었습니다.

7번 노드에서 새로운 100+1+ 패턴이 시작되려는 걸 살펴보려면, 1 한 개를 읽은 후에 1번 노드가 아니라 3번 노드로 가야 합니다.

p_ce1052   9달 전

저 그림이 잘못되었군요 감사드립니다

댓글을 작성하려면 로그인해야 합니다.