0
r의 r 및 DFA가 정의되었을 때 r *의 DFA를 찾는 방법을 원합니다. 그리고 생각하는 법? 나는 교과서를 읽었지만 명확하게 이해하지 못합니다. 고맙습니다.r의 r 및 DFA가 정의 된 경우 r *의 DFA 찾기
A
답변
0
r *은 r의 0,1,2,3,4, ... 문자열의 연결 인 모든 문자열을 포함하는 언어입니다. 따라서 r *에 대한 명백한 FA는 r 0,1,2,3,4, ... 시간 동안 DFA를 실행할 수 있고 이러한 실행 중 하나가 발생한 후에 수락 할 수있는 FA입니다. 수락 상태에서 시작 상태로의 λ/빈 전환은 1 회 이상의 실행을 달성합니다. 결과 오토 마톤은 더 이상 결정적이지 않습니다. 표준 방법을 사용하여이를 결정할 수 있습니다. 이 구성은 자동 문자열의 언어에 빈 문자열을 추가하지 않습니다. 이미 r에 있다면, 이것은 필요하지 않습니다. 그렇지 않으면 새로운 시작 상태와 같이 r *에 대해 자동 문자열에 빈 문자열을 허용하는 방법을 추가해야합니다.
빈 전환을 없애는 데 약간의 경험이 있으면 간단한 경우보다 직접 DFA를 구성 할 수도 있습니다.
각 수락 상태에서 시작 상태로 엡실론을 추가하면 입력 언어의 별을 허용하는 NFA가 반드시 작성되지는 않습니다. (나는 보통 이것이 내 이론 수업에서 학생들에게 운동으로 실패한 이유의 예를 찾는 질문을 던집니다.) – templatetypedef
고마워요, @templatetypedef, 저는 여기서 조금 성급한 태도를 보였고 그것을 기억하지 못했습니다. 나는 대답이 나아 졌으면 좋겠다. –
여기에도 여전히 문제가 있습니다. 다음은 작동하는 구성입니다. 새로운 시작 상태를 추가합니다. 엡실론 전환을 이전 시작 상태로 추가하고 각 이전 수용 상태에서 새로운 시작 상태로 엡실론을 추가하십시오. – templatetypedef