정확합니다. 문법이 동일하다는 것을 보여주기 위해 (동일한 언어를 생성 함), 다른 문법을 복제 할 수 있다는 것을 보여 주어 동일한 문자열을 생성 할 수 있습니다. 다음과 같이
예를 들어, 제안 된 문법 E을 (S)S 생성 할 수 있습니다
`S => SS => (S)S` and `S => E`.
다음과 같이 다른 문법을 복제 할 수 있습니다 귀하의 문법 :
S => SS를 들어
`S => (S)S => (S)`
`S => E`
, 당신이 실제로 할 수 없습니다 그것을 복제하거나, 강의의 문법이 할 수있는 다른 어떤 S^n. 터미널의 줄이 덮혀있는 한이 모든 것을 커버 할 필요가 없기 때문에 괜찮습니다. 이 일을 위해, S^n 결국 다음의 (S)으로 변경 S (다른 규칙)과 모두 왼쪽에서 작업이 있어야합니다 :
`S => (S)S => (S)(S)S => ... => (S)^n S => (S)^n`
지금 당신이 수행됩니다.
또한 (a) 문법에 의해 생성 된 모든 문자열이 L에 있음을 증명할 수 있습니다. (b) 문자열이 L이면 문법에 따라 문자열이 생성됩니다. 괄호 쌍 수와 같은 유도에 의해이를 수행 할 수 있습니다.
n = 0의 경우 문자열은 E이고이 값은 L입니다. n = 0의 유일한 문자열은 E이며 Google 문법에 의해 생성됩니다.
유도 가설 : L에와 우리의 문법에 의해 생성 된 괄호 k쌍 등까지 모든 문자열 및 최대 우리의 문법에 의해 생성되는 괄호 k쌍 등으로 L의 모든 문자열.
유도 단계 : 우리는 L에있는 우리의 문법에 의해 생성 된 괄호의 k+1 쌍 모든 문자열을 표시하고 괄호 Lk+1와 쌍으로 모든 문자열이 우리의 문법에 의해 생성됩니다. 괄호 k+1 쌍 규칙 S => (S)S를 사용하여 우리의 문법에 의해 생성 된와
한다고 가정 문자열 w. 이어서 w = (x)는 X, Y whereand Y are words in L with fewer than K + 1 pairs of parentheses. But then they are balanced by the induction hypothesis.w is therefore balanced sinceis balanced, thus X (X) is balanced and (X) Y = 너무 w`.
k+1 쌍의 문자열이 L 인 것으로 가정합니다. 그런 다음 L의 정의에 따라 w의 균형이 조정됩니다. 균형 잡힌 괄호 문자열은 왼쪽 및 오른쪽 괄호의 수와 같아야하며 모든 접두사에서 오른쪽 괄호만큼 많은 왼쪽 괄호를 사용해야합니다 (따라서 접미사에는 왼쪽 괄호만큼 많은 오른쪽 괄호가 있어야합니다). 첫 번째 왼쪽 괄호와 첫 번째 오른쪽 괄호를 선택하면 접두사의 왼쪽과 오른쪽 괄호 수가 같습니다. 이 하위 문자열 (x)은 w입니다. 그 후에 오는 부분 문자열은 오른쪽 괄호와 동일한 수의 왼쪽 괄호를 가져야하며 모든 접두사에서 최소한 왼쪽 괄호가 있어야합니다 (이것은 w이 균형을 이루는 조건을 충족시키기위한 것입니다). 따라서, 이후에 오는 것은 - y이라고 부르겠습니다 - 균형 잡힌 괄호 문자열이어야합니다. (적절한) 하위 문자열로, x과 y은 모두 w (더 적은 괄호 쌍을 포함)보다 짧아야하며 둘 다 균형을 유지해야하므로 둘 다 L입니다. 그러나 그것들은 모두 문법에 의해 생성되며 문법은 S => (S)S을 포함하기 때문에 (x)y을 생성합니다.
답변에 대한
좋아요 감사 QED. – yogeshagr