두 개의 서로 다른 문법이 한 세트의 출력에 걸쳐 있음

Question

같은 단어 집합을 출력하는 두 개의 다른 문법을 줄 수 있습니까?

그림 :

문법 A는 문법 B 수뿐만 아니라, 단어 0101001를 생성 할 수있는 경우, 알파벳 {0,1}을 통해 문법 A와 B를 감안할 때. 문법 B가 0101111을 생성 할 수 있다면 문법 A도 가능합니다. 그리고 문법 A가 01001을 생성 할 수 없다면 B는 그렇게 할 수 없습니다.

하지만 여기서는 문법 A와 B가 완전히 다르다는 것, 즉 완전히 다른 알고리즘을 사용한다는 것입니다. 그런 다음 이들이 산출하는 일련의 결과는 다른 하나의 적절한 하위 집합이 아닙니다. 해당 출력 집합이 동일한 카디널리티를 가져야 함을 의미합니다. 아마도 그들은 서로 다른 복잡성 등급을 지니고 있지만 문제는 아닙니다. 만약 당신이 고전 Turing machine처럼 알파벳 {0,1} 이상의 문법을 주면 크게 감사하겠습니다.

Answer 1

확실하지 않습니다. A가 산출물 a를 생산할 수 있다면, B는 a를 직접 포함하거나 b와 a를 생성하는 a보다 짧은 b '를 포함한다. 같은 논증이 b (와 b ')에 적용된다 - 그것은 A에서 직접적으로 존재하거나 b를 생성하는 A에서 b보다 짧은'와 a ''가 존재한다. 이 인수를 반복하면 결과적으로 개별 요소가 길이 1 인 지점으로 이동하므로 더 이상 세분화 할 수 없으며 A와 B의 요소가 동일해야합니다.

Answer 2

이 트릭은 괜찮습니까?

A 
A -> 0A 
A -> B 
B -> 1B 
B -> {} 

오른쪽에서 왼쪽 : 왼쪽에서 오른쪽 형 0*n1*m (예컨대 000,000,111)의 문자열로 구성 될 수

B 
B -> B1 
B -> A 
A -> A0 
A -> {} 

중앙으로부터 :

AB 
A -> A0 
A -> {} 
B -> 1B 
B -> {}