구문 찾기 자유 문법 (CFG)

Question

문맥 자유 문법 제공 언어를 생성하는 H M = {a^m b^n | 2m> n> m}. ' 힌트 : m은 0 일 수 없습니다.이 경우 2m = m이기 때문입니다. m은 1 일 수 없습니다.이 경우 2> n> 1이기 때문에 자연스러운 숫자 은 존재하지 않습니다. 따라서 언어 M에서 가장 짧은 문자열은 aabb입니다. 긴 문자열의 경우,에 bs의 수 n과 as의 수 m이 2m> n> m을 만족하는지 확인해야합니다.

Answer 1

aabbb은 (는) 언어로되어 있으므로 S -> aabbb은 (는) 나쁜 시작이 아닐 수도 있습니다. 어떻게하면 더 긴 문자열을 얻을 수 있습니까? 음, 우리는 2m > n > m을 유지해야합니다. 이 언어의 가장 짧은 문자열 (a의 주어진 수)은 a을 가진 것보다 b이 하나 더 많으므로 S -> aSb은 나쁜 것으로 추측 할 수 있습니다. 확실히 우리 언어의 문자열, 즉 가장 짧은 문자열을 생성합니다 (주어진 수의 a). 마찬가지로 우리 언어의 가장 긴 문자열은 b보다 두 배 이상 많기 때문에 S -> aSbb은 (a의 주어진 수에 대해) 가장 긴 문자열을 생성한다는 점에서 안전합니다.

이

S -> aabbb 
S -> aSb 
S -> aSbb 

처음 이후 모든 생산이 단일 a 및 하나 개 또는 두 개의 b의 추가 : 우리의 문법은 지금까지입니다. 두 번째 제품은 단독으로 사용하면 가장 짧은 문자열 (주어진 수의 a)을 생성하고, 세 번째 제품은 단독으로 사용될 경우 가장 긴 제품을 생성합니다 (주어진 수의 a). 가장 짧은 것과 가장 긴 것 사이의 문자열은 어떻습니까? 이러한 제작물을 사용하여 그 모든 문자열을 얻을 수 있습니까?

수 있습니다. 유도로 증명할 수 있습니다. 언어의 길이가 n (1) 인 모든 문자열이 문법에 의해 생성되고 (2) 문법에 의해 생성 된 문자열이 언어로 표시되어야 함을 보여 주어야합니다.

기본 경우 : 언어의 최단 문자열은 aabbb이며 문법에 의해 생성됩니다.

유도 가설 : 문법은 길이가 k까지의 모든 문자열에 대해 언어의 모든 문자열 만 생성한다고 가정합니다.

유도 단계 : 문법이 길이가 k + 1 인 모든 문자열에 대해 언어의 모든 문자열 만 생성하도록 표시해야합니다. 우리는 이미 문법이 언어가 아닌 문자열을 생성 할 수 없다고 주장했다. 두 번째 작품 만 사용하면 n = m + 1이되고 세 번째 작품을 사용하면 n = 2m - 1이됩니다. 해당 언어의 모든 문자열을 생성하는지 확인하려면 해당 언어의 모든 문자열이 적어도 두 개부터 시작하여 a 두 개에서 시작하여 적어도 세 개 이상인 b으로 끝납니다. 그래서, 그것은 aaxbbb로 쓰여질 수 있습니다. 이 문자열이 언어로되어 있으면 axbb 및/또는 axb 중 하나 또는 둘 모두가 언어로되어 있어야 함을 나타낼 수 있습니다.

1. axbb는 L2(m - 1) > n - 1 > m - 1 않거나 2m - 1 > n > m
2. axb 인 경우이다 L2(m - 1) > n - 2 > m - 1 또는 2m > n > m + 1인치

모든 경우의 기본 케이스로 시작하기 때문에, 우리는 적어도 2m - 1 > n 중 하나 및/또는 n > m + 1, 그 중 하나가 L에 또한있다. 유도 가설에 의해 문법은 그것을 생성한다. 문법의 작품 중 하나는 원래 길이가 k + 1 인 문자열을 생성합니다. 따라서 문법은 모든 문자열을 L에 생성합니다.