언어가 재귀 적으로 또는 재귀 적으로 열거 가능 여부를 결정하는 방법은 무엇입니까?

Question

언어 (예 : L = {a^nb^mc^s | 0 < = n < = m < = s})는 일반, 문맥 자유, 재귀, 반복적으로 열거 가능 또는 전혀 없음을 결정해야합니다. .

언어가 정상적인지 (작동하는 DFA 또는 정규 표현식을 찾습니다) 또는 문맥이 없는지 (작동하는 PDA 또는 문맥 자유 문법 찾기) 어떻게 결정하는지 알고 있습니다. 재귀 적 언어에는 항상 멈추는 튜링 기계가 있으며 재귀 적으로 열거 가능한 언어에는 멈추지 않는 튜링 기계가 있다는 것을 알고 있습니다.

그래서 질문은 언어가 재귀 적이거나 재귀 적으로 열거 가능하거나 그렇지 않은지를 결정하는 빠른 기준이 있습니까? 예를 들어, 언어가 문맥에 구애받지 않는다는 것을 이해하기 위해 PDA를 만들 필요는 없습니다. 하나의 스택이 필요하다는 사실로 볼 수는 없습니다. 문제에 대한 비슷한 빠른 접근법이 있습니다 (튜링 기계를 만드는 데 어려움을주지 않아도됩니까)?

Answer 1

언어가 재귀 적으로 반복적으로 열거 가능한지 확인하는 구조적인 방법은 없습니다. 재귀 적 언어를 인식 할 수있는 모든 오토 마톤에 대해 R에없는 RE 언어가 하나 이상 있어도 오토 마톤도 받아 들일 수 있다고 말하는 정말 멋진 증거가 있습니다. 결정할 수없는 문제의 존재를 보여주기 위해 사용하는 대각 화 인수의 변형입니다.

언어를 증명하는 주된 방법은 RE가 아니라 RE가 언어에 있음을 증명하는 것입니다 (아마도 TM을 정의함으로써). 그런 다음 RE에서 알려진 문제는 줄이고 R에서는 그렇지 않은 것으로 알려진 문제를 줄이면됩니다. 문제. 예를 들어 중단 문제의 인스턴스가 문제의 인스턴스로 변환하여 해결 될 수 있음을 보여줄 수 있다면 재귀 솔루션을 가질 수 없다는 것을 알고 있으며이를 위해 언어는 RE에 있습니다. 함께, 당신은 RE에 있지만 R에 언어가 없습니다

Answer 2

문맥 자유 언어 하나의 빠른 방법은 단지 비교의 수를 볼 수 있습니다.
예에서 n<=m 및 m<=s을 참조하십시오. 따라서 두 가지 비교가 필요합니다. 따라서 컨텍스트가없는 것이 아니라는 것을 간단하게 알 수 있습니다. 비교가 하나만있는 경우 컨텍스트 프리 언어로 호출하십시오.

동일한 언어의 경우는입니다. 두 변수 사이에는 아무런 관련이 없어야합니다. 어떤 종류의 비교도 있어서는 안됩니다. 예를 들어, 언어 -0^m+n 1^n 0^m을 고려하십시오. 조심스럽게 단지 하나의 비교가 이루어 졌는지 확인하십시오. 이는 m+n = n+m (기호를 밀고 터지는 것)이므로 문맥이 없습니다.
이제 0^n+m 1^n+m 0^m은 처음 2와 다음 2의 비교를 명확하게 볼 수 있습니다.

나는 그것을 이해하는 데 시간이 좀 걸렸습니다. 그러나 결정을 내리는 데는 어느 정도 시간이 걸릴 것입니다. 저를 믿으십시오 정말 작동합니다. 다음은 정규 언어의 마지막 예입니다. a^n b^2m는 (n과 m 사이에 비교가없는 참조) 정규이며이 (일반되지 않음) 하나 개의 비교

희망이 확실히 내가 바라던 대답하지