두 언어 조합에 대해 DFA를 만들어야하는 문제를 해결하려고합니다.두 개의 결정적 유한 오토마타의 합집합?
이들은 다음과 같습니다. {s is {a, b, c} * | s의 모든 "a"바로 뒤에 "b"가옵니다} 및
{s는 {a, b, c} * | s의 모든 "c"는 "b"로 즉시 시작됩니다.
나는 제대로 된 길로 가고 있다고 생각하지만, 그것이 맞는지 확실하지 않습니다. 누군가 좀 봐 주시겠습니까?
여기에 두 DFAS의 조합을 찾는 방법을 설명하는 유사한 post입니다.
두 가지 DFA를 동시에 실행해야하거나 일반적으로 DFA의 두 DFA 상태를 유지 관리해야한다는 것을 이해해야합니다.
편집 :
당신의 DFAS가 결정하지 않으며 실제로 언어를 결정하지 않기 때문에 당신이 설명하기 때문에 당신이 잘못된 결과를 얻고있는 이유입니다. 나는 당신의 연합 계산이 정확하다고 생각하지만, 앞으로 나아 가기 전에 DFA를 수정해야합니다.
두 언어의 교차점은 L1 ∩ L2 = not(not(L1) ∪ not(L2)) (드 모르간 법)입니다.
DFA의 보수 ("not")는 모든 수락 상태를 수락하지 않음으로, 그 반대의 경우도 마찬가지입니다. 이것은 당신에게 비 결정론적인 유한 오토마타 (NFA)를 줄 것입니다.
두 개의 DFA 또는 NFA를 결합하여 두 언어를 동시에 허용하는 새 NFA로 유니언을 만듭니다. 이것은 아무것도 소비하지 않고 두 NFA의 시작 상태로 이동할 수있는 시작 상태를 도입함으로써 수행됩니다 (ε 만 소모).
이 모든 작업을 완료하면 NFA가 있습니다. 일반적인 방법을 사용하여이를 DFA로 줄일 수 있습니다.
사실, 문제는 두 번째 DFA가 실제로 NFA라는 것입니다. 상태 2에있는 경우 DFA는 'c'를 입력으로 할 때 수행 할 작업을 알 수 없습니다. –
그래, 그게 내가 한 짓이야.하지만 나는 DFA로 모든 국가의 각 레이블마다 전환이 필요하지 않으므로 내 최종 답변이 너에게 잘 보이는지 궁금한가요? – AkshaiShah
두 번째 DFA는 비 결정적입니다. 상태가 '2'이고 입력으로 'c'를 얻으면 어떻게 될까요? –
알 겠어. 그래서 상태 2에서 덤프 상태로 전환 할 수 있습니까? – AkshaiShah