1
이번 학기의 Theory of Computation을 배우기 시작했으며 "DFA for a language"라는 문구로 혼란스러워했습니다. 바이너리 문자열 L의 일부 콜렉션에 대해 DFA를 생성하라는 메시지가 표시되면 L (M) = L 또는 $ L (M) \ supset L $ 인 DFA M을 찾으라는 의미입니까?"DFA for a language"의 정의
A
답변
0
대부분의 컴파일러/이론 코스는 결정 론적 유한 자동 오토마타 및 공식 언어의 교수 정의를 둘러싼 다양한 스타일을 갖는 경향이 있지만 가능한 한 불가지론 자로 묘사하려고 노력할 것입니다 (L (M) = L). .
문구 "언어에 대한 DFA"는 모든 언어로 word을 모두 수락하고 모든 언어로 word을 거부하는 DFA를 의미합니다. DFA를 가르친 방법은 암시 적 오류 상태에 대한 필요성을 제거하는 최종 상태/수락 상태와 일반 상태를 유지하는 것입니다. 입력이 끝날 때 상태가 accepting 인 경우 DFA가 단어를 수락하고 상태가 accepting이 아닌 경우 DFA가 단어를 거부 함을 의미합니다.
예 :
는 이제 1의 짝수를 포함하는 언어로 L을 정의 할 수 있습니다. 이들은 이진 문자열이므로 기호는 0과 1입니다. 00, 110,
, 111
1111 등은이 언어의 단어의 예입니다. 빈 문자열은이 언어로되어 있습니다.
DFA에는 두 가지 상태가 있습니다. 시작 상태 (even 1s이라고 함)도 0이 짝수이기 때문에 수락 상태입니다. 다른 주인은 odd 1s이며 동의하지 않습니다.
전환의 경우, even 1s이 1을 수신하면 odd 1s으로 전환됩니다. odd 1s이 1을 받으면 even 1s으로 전환됩니다. 이제 0의 수는 중요하지 않으므로 두 상태 중 하나에서 그 자체로 전환됩니다. 이중 화살표
죄송합니다,이 website은 훌륭하지만 even 1s 및 odd 1s
0
정확하게 질문을 작성하십시오. 여기서 DFA는 특정 언어에 대해서만 기계를 구성해야한다는 것을 의미합니다. 서브 세트 또는 수퍼 세트가 아닙니다.