| [ QuizWit ] in KIDS 글 쓴 이(By): dkkang (질투는내힘) 날 짜 (Date): 2002년 7월 10일 수요일 오후 01시 17분 16초 제 목(Title): Decidable language의 concatenation 지난 학기에 theory of computation 수업을 들었는데요. 어나니에서 theory of computation은 어려운 거다고 했더니, 키즈 고수 정도면 그리 어렵지 않다고 누가 그러네요? 아마 아는 분이 있을 듯... 지난 학기에 텍스트로 썼던 Homer and Selman의 Computability and Complexity Theory의 70 쪽에 나오는 연습문제 3.17 이거든요. Show that if A is a decidable language, then so is the concatenation AA. Provide an example to demonstrate that the converse is false. 결국 두 문제인데, 앞의 증명은 평이하니까 필요없고, 뒤의 반례가 뭐가 있는지 들어주셨으면 합니다. |