-1
다음 언어는 간단한 언어를 보완합니다. 간단한 언어로 DFA를 만든 다음이 언어를 사용하여 Σ = {a, b} 인 주어진 언어에 대한 DFA의 상태 다이어그램을 제공하십시오.어떤 언어가 더 간단한 지 확인하는 방법
L = {w : w는 하위 문자열 baba를 포함하지 않습니다}.
어떤 언어가 더 간단한 지 모르겠지만 아무에게도 설명해주십시오.
A
답변
0
문자열 '바바'를 포함하는 모든 단어를 받아들이는 오토마타는 다음과 같습니다
이
(이것은 단순한 언어의 IT에 대한 정규 표현식은 다음과 같습니다. (A | B) * 바바 (A | B) *)
그리고 당신이 그것을 했나요으로 우리는 비 받아들이고 그 반대로 받아들이는 상태를 돌려 보완 DFA를 구축 할 수 있습니다 :
(완료해야 함)
0
Logic & Computability 클래스는 꽤 오래되었지만, Lc는 = {w : w는 하위 문자열 'baba'}를 포함하는 보완 언어입니다.
'baba'의 부분 문자열을 허용하는 DFA를 만드는 것은 매우 쉽습니다. firstB, firstA, secondB 및 secondA 등의 상태를 가질 수 있습니다.
보완 DFA를 만드는 것은 간단합니다. 수락하는 국가를 수락하지 않고 그 반대의 경우도 마찬가지입니다.
+0
"간단한 언어"가 의미하는 바는 {w : w는 하위 문자열 'baba'}를 포함합니다. 나는 ucept를 언급 한대로 받아들이지 않는 상태로 ccepting states를 바꿀 것인가? – nmorsi
덕분에 많이 .. 상태 5는 생략되었으므로 생략되었거나 도달 할 수 없기 때문에 생략 되었습니까? – nmorsi
예, 죽은 상태입니다. 추가하면 전체 DFA를 얻을 수 있습니다. –