언어에서 문맥 자유 문법으로 이동

Question

주어진 언어 K = {e^h f^i | 2h> i> h} 문맥 자유 문법을 생성해야합니다.

내가 만든 몇 가지 제작 규칙은 다음과 같습니다. S -> eeTfff 및 T -> eTff | ε

n = m + 1 인 경우에만 작동하지만 2h> i> h의 모든 조합에 대해 규칙을 생성하는 방법을 알지 못합니다.

Answer 1

먼저 언어에서 가장 짧은 문자열을 식별하십시오. 우리는 i> h가 필요하므로 h = 0이라고 추측 할 수 있습니다. 그러나 그것은 2h> i를 만족할 수 없기 때문에 아무데도 이어지지 않습니다. 우리는 h - 1을 사용하여 같은 일을합니다. h = 2를 선택하면, i의 유일한 선택은 3입니다. 따라서 언어의 가장 짧은 문자열은 eefff입니다. 길이가 다른 문자열은 사용할 수 없습니다.

긴 문자열을 얻으려면 끝에 e를 추가하거나 끝에 f를 추가 할 수 있습니다. 분명히, 앞부분에 e를 추가한다면, 반드시 적어도 하나의 f를 마지막에 추가해야하고, f를 두 개 이상 추가해서는 안됩니다. e.eefff.f와 e.eefff.ff가 모두 우리의 언어로되어 있다는 것을 확인할 수 있습니다. 이것은 문법을 제안합니다 :

S -> eefff | eSf | eSff 

일단 후보자를 얻으면 수학적 유도를 사용하여 그것을 증명하려고 시도 할 수 있습니다. 우리의 경우 :

기본 경우 : 언어 eefff의 최단 문자열은 생산 S -> eefff에 의해 주어집니다.

유도 가설 : 문법이 언어의 모든 문자열을 생성하고 문법이 생성하는 모든 내용이 길이가 k를 넘지 않는 모든 문자열에 대해 언어로 있다고 가정합니다.

유도 단계 : (1) 문법에 의해 생성 된 길이가 k + 1 인 문자열이 언어에 있고 (2) 언어에서 길이가 k + 1 인 문자열이 문법에 의해 생성된다는 것을 보여줘야합니다.

1. 문법에 의해 생성 k+1 길이의 문자열 S -> eSfS -> eSff 또는 중 하나를 사용하여 생성 하였다. 첫 번째 경우 RHS에있는 S에서 파생 된 문자열의 길이는 k-1입니다. 두 번째에는 길이가 k-2입니다. 두 경우 모두 문자열은 유도 가설에 의해 언어로 표시됩니다. 즉, h < i < 2 시간입니다. 그런데 (h + 1) < (i + 1) < (i + 2) < 2 (h + 1)이므로 두 경우 모두 해당 문자열이 언어로 유지됩니다.

2. 길이가 k+1 인 모든 문자열을 고려하십시오. 우리는 h + i = k + 1이고 h는 <입니다. < 2 시간입니다. 그러한 문자열은 어떤 숫자의 e로 시작해야하고 몇 개의 f로 끝나야합니다. 길이가 k-1 및 k-2 인 부속 문자열을 고려하십시오. 첫 번째 전자와 마지막 한 개와 두 개의 f를 제외하여 구성됩니다. 전자가 언어의 문자열이거나 후자가 문자열입니다. 이것을 보지도 않았을 것입니다. 그러나 (h-1) < (i-1) < 2 (h-1)도 (h-1) < (i-2) < 2 (h-1)도 아니다. 즉 :

   ((i <= h) or (i >= 2h - 1)) 
   

   및 (또는 (> = 2 시간 전 (전 < = h를 + 1)))

우리가 시간 < 알고 있기 때문에 내가 < 2 시간 우리의 문자열이 L에 있기 때문에, 1 차 및 4 차 조건을 제거 할 수 있습니다. 남아있는 것은 결코 만족스럽지 않습니다.이것은 부분 문자열 중 적어도 하나가 언어에도 있음을 보여줍니다. 유도 가설에 의해, 그 문자열은 문법에 의해 생성된다. 해당 문자열에서 길이가 k+1 인 문자열을 얻으려면 해당 언어의 하위 문자열에 따라 S -> eSf 또는 S -> eSff을 적용하면됩니다.