거기에 필요 에 대한
L⊆Σ∗가 될 무한 결정 불가능한 것으로는?
우리가 언어를 선택하면 내가 무엇을 의미
L′수 의 경계 유한 버전
L⊆Σ∗입니다
|L′|≤N, (
N∈N,)와
L′⊂L. 그것은 가능합니다
L′결정 불가능한 언어로?
“무한한”Kleene 스타 연산의 일종 인 의 첫 번째 요소 가 될 규칙을 설정해야하는 ∈ 의
N단어 를 선택하는 방법”이라는 문제 가 있습니다. . 목표는 무한한 세트가 필요없는 결정 불가능한 언어를 찾는 것이지만 볼 수는 없습니다.
∈N L ‘
L′“N
L′
참고 편집 :
답변을 선택했지만 많은 답변 과 모든 의견 이 중요합니다.
답변
그렇습니다. 을 결정할 수 없게하려면 무한 해야합니다 .
L라파엘과 샘의 답을 더하기 위해, “결정 가능”을 컴퓨터 프로그램이 해결할 수있는 것으로 생각해야합니다. 필요한 프로그램은 매우 간단합니다. 요소에 대해 “Yes”만 출력하면 됩니다.
L따라서 “복잡한” 이 많을수록 프로그램 작성 시간이 길어집니다. 다른 말로하면, 당신이 실행하는 프로그램이 길수록 더 많은 것들을 확인할 수 있습니다. 그래서 누군가가 되는 언어 을 주면 과 같이 쓸 수 있습니다. 다음 프로그램 :L L = { a 1 , a 2 , … , a n }
LL
L={a1,a2,…,an}
if INPUT = $a_1$ output Yes;
if INPUT = $a_2$ output Yes;
...
if INPUT = $a_n$ output Yes;
output No;
이제 어떤 것이 당신에게 더 큰 (아직 유한)을 주면 더 긴 프로그램을 작성하게됩니다. 이것은 항상 사실이며 유한 은 자체 프로그램을 갖습니다. 유일한 “흥미로운”사례는 이 무한 할 때 발생하는 것입니다. 프로그램은 무한 할 수 없습니다 .L L
LL
L
“결정 불가능 성”문제는 훨씬 더 흥미 롭습니다. (무한대) 은 제대로 작동하는 프로그램이 없습니다. 우리 는 유한 한 (그러나 무한한) 길이의 프로그램의 수보다 더 많은 (무한한) 언어 이 있기 때문에 그러한 언어가 존재해야한다는 것을 알고 있습니다 .L
LL
답변
나는 그 질문을 올바르게 이해하고 있는지 확실하지 않지만 모든 유한 한 언어는 규칙적입니다. 결정 불가능한 정규 언어는 없으므로 결정 불가능한 유한 언어는 없습니다. 이 모든 진술은 잘 알려져 있으며 Hopcroft와 Ullman 에서 증거를 찾을 수 있습니다 .
답변
언어의 경우 유한, 당신이 수행 할 수있는 테이블 조회 에있는 모든 단어를 포함하는 하드 테이블에 . 이것은 Turing machine으로 작성하기에는 어색하지만, 다른 모델에서는 상당히 분명합니다.L ‘
L′ L′사실, 유한 오토마타이면 충분합니다. 다음과 같이 대한 오토 마톤을 구성하십시오 .
L′- 모든 들어 , 수용 상태의 직쇄 생성 . w
w∈L′ w - 새로운 초기 상태 작성하십시오 .
q0 - 연결 으로 1 년에 건설 모든 오토마타의 초기 상태에 -transitions. ε
q0 ε
이렇게 구성된 오토 마톤은 분명히 받아들 입니다. 따라서 은 규칙적이고 계산 가능합니다 ( ).L ‘ R E G ⊊ R E
L′L′
REG⊊RE
공동 유한 대해 일부 추론이 적용됩니다 . 즉 ; 당신은 단지 요소를 하드 코딩 하지 에 .| ¯ L ‘ | < ∞ L ‘
L′|L′¯|<∞
L′
답변
(계산성에 대해 생각할 목적으로) 모든 흥미를 갖기 위해서는 결정 문제가 무한히 많은 "예"답변과 무한히 많은 "아니오"답변을 가져야합니다. 이러한 결정 문제는 알파벳보다 많은 문자열을 포함하는 언어에 해당하며 알파벳보다 많은 문자열을 제외합니다.
다른 것들은 유한 한 양의 정보로만 인코딩 될 수 있으므로 (언제나 언어가 아닌 많은 문자열 목록) 간단한 DFA / 정규 표현식으로 계산할 수 있습니다. 유한 한 문자열 목록에 대해 단순히 모든 문자열을 OR하는 정규식을 즉시 작성할 수 있음을 분명히해야합니다.
나의 계산 이론 강사의 witticism은 "하나님이 존재 하는가"라는 문제였습니다. 계산 가능-즉시 수락하는 기계 또는 즉시 거부하는 기계에 의해 계산됩니다. 우리는 단지 어느 것을 모른다!