FSM의 상태 집합을 읽는 프로그램을 작성하는 방법. 입력 데이터는 형식 (상태 입력 next-state)의 텍스트 파일에서 가져 오며 마지막 줄은 최종 상태입니다. 예 :Java에서 Finite State Machine을 만드는 방법
s0 a s1
s1 a s2
s2 a s2
s1
프로그램 출력 할 : FSM에 의해 생성 된 문자열
a)리스트.
B) 프로그램은 FSM은 DFA 또는 NDFA 여부를 결정하고 그 결과
내가 당신에게 코딩 솔루션을 제공하지 않을거야를 인쇄하지만, 생각의 몇 가지 방향입니다 수 있습니다.
우선 FSM에는 시작 상태와 종료 상태가 필요하므로 중요한 정보가 누락되었습니다.
문자열 목록을 생성하는 경우 제한된 수의 문자열을 허용하는 매우 제한된 FSM 하위 집합을 처리 할 수 있습니다. 그러므로 모든 가능성을 시도하는 것이 합리적입니다. 그래프를 통해 모든 경로를 따라 가며 끝 상태에 도달 할 때마다 인쇄하십시오.
DFSM과 NDFSM의 차이점에 대해 생각해보십시오. 입력에 따라 여러 가지 방법이있는 경우 비 결정적입니다. 따라서 그래프를 작성할 때 서로 다른 상태로 두 개의 동일한 전환이있는 노드가있는 경우 이는 비 결정적입니다. 모든 비 결정론이 전체 시스템을 비 결정적으로 만들기 때문에 결정론은 비 결정론의 부재입니다.
그럼 실제로 표현을 만드는 것으로 시작하고 싶을 것입니다. 두 가지 쉬운 방법이 떠오른다. 보다 시각적으로 그래프를 만들 수 있습니다. 이를 수행하는 가장 간단한 방법은 노드 클래스를 생성 한 다음 각 노드에 대해 전환 및 대상 쌍을 포함하는 객체를 만드는 것입니다.
내가 FSM을 나타내는 것을 선호하는 방법은 해시 맵/사전을 사용하는 것입니다. 대상을 값으로 사용하여 노드와 전환을 키로 사용하십시오. 따라서 탐색이 매우 쉽습니다.
행운을 빈다.
편집 : (난 그냥 잠시처럼 :).) 비 결정론을 결정, 엡실론 전환에 대해 생각하는 것을 잊지 마세요
길 찾기에 감사드립니다. 프로그램이 입력 파일을 찾아 데이터를 검색하고 배열에 모든 상태와 입력을 저장할 수있게 만들었습니다. 그러나 그 이후에, 나는 알고리즘이 어떻게 될지 알지 못합니다. 경로가 최종 상태에 도달하는 한 문자열은 다를 수 있습니다. Thats는 문자열이 둘 이상일 수 있음을 의미합니다. 어떻게 프로그램을 계산할 수있게 만드시겠습니까? 나는 완전한 코딩을 요구하지 않는다. 적어도 그것을 이해하는 데 도움이 될 수있는 알고리즘의 그림을 보여 주라. –
아마도 재귀가 가장 쉽습니다. 그래프를 통과하는 방법을 작성하십시오. 시작 상태가 무엇이든간에 메소드를 시작하십시오. 그런 다음 가능한 모든 변환을 찾으십시오. 재귀 적으로 현재있는 메서드를 호출하여 가능한 모든 전환을 새로운 상태로 가져옵니다. FSM (가능한 모든 가능한 문자열을 취하는)을 통해 가능한 모든 경로를 취하는 많은 재귀 호출을 통해 이것이 어떻게 분기되어 있는지 확인할 수 있습니다. 자 이제 기본 케이스 : 그것이 최종 상태에 도달했을 때입니다. 그런 다음 도착하기까지 소요 된 경로를 인쇄 할 수 있습니다. – akroy
그래프를 살펴보면, 두 개의 동일한 트랜지션 (또는 동일한 트랜지션으로의 엡실론 트랜지션)이 있다면, 비 결정적이라고 판단한 것입니다. – akroy
이 숙제인가? 너 뭐 해봤 니? –
@home 완전한 솔루션을 요구하는 것은 좋지 않습니다. 그는 상당한 노력을 보여 주어야합니다. –