L = {2^x * 2^y * 2^z = 2^(x + y + z)에 대한 문맥없는 문법. x, y, z> 0}

Question

제목에서 설명합니다. "방정식"의 왼쪽을 오른쪽으로 동기화하는 데 문제가 있습니다. 왼쪽에 2를 생성 할 때마다 오른쪽에 하나를 표시해야합니다. 이 언어가 컨텍스트 프리가 아니어도 될까요? 미리 감사드립니다.

L = {2^x ∗ 2^y ∗ 2^z = 2^(x+y+z) | x, y, z > 0}

편집 : 이것은 수학 방정식과는 아무 상관이 없습니다. "*"과 "="은 언어 알파벳의 기호 일 뿐이며 2는 "x"의 힘으로 2가 x 번 반복되는 것을 의미합니다. 곱셈 문자열 연결 및 지수 반복에 대한 기본적인 사실을 사용하여

Example of this language: 
222*2*22=222222 
2*2*2=222 
2*222222*22=222222222 

Answer 1

, 우리는 같은 언어를 다시 정의 할 수 있습니다 :이 언어 정의는 더 정교 할 수

L = { 2^x * 2^y * 2^z = 2^z 2^y 2^x | x, y, z > 0 } 

을 같은 :

Lz = { 2^z = 2^z | z > 0 } 
Ly = { 2^y * w 2^y | y > 0, w ∈ Lz } 
Lx = { 2^x * w 2^x | x > 0, w ∈ Ly } 
L = Lx 

그러면 Lz에 대한 문법을 ​​정의 할 수 있습니다 :

Z ::= 2 = 2 
Z ::= 2 Z 2 

그리고 리 하나 : LX 대한

{ include Lz's grammar } 
Y ::= 2 * Z 2 
Y ::= 2 Y 2 

그리고 하나

여기

Answer 2

는이다

가

{ include Ly's grammar } 
X ::= 2 * Y 2 
X ::= 2 X 2 

L = LX 때문에, 결합 문법의 시작 심볼 X 인 222*2*22=222222, 2*2*2=222 등과 같은 문자열이 문법적 인 문맥 자유 문법의 예입니다. 당신이 원하는 문자열이 유효한 모든 <expression>의있는이 작품으로

<literal>: 2 | <literal>2; 
<number>: <literal> | <number>*<number>; 
<expression>: <number>=<number>; 

. "틀린"문자열은 다음과 같이 문법적입니다.

22=2 

문제가 발생했는지 여부는 내게 명확하지 않습니다. 프로젝트의 첫 비즈니스 순서는 의미론에 대해 걱정하지 않고 문자열을 파싱 한 다음 문법적 문자열의 의미를 평가하는 것입니다.

편집 : 사실 내 답변에 문제가 있거나 방금 내 잔디에서 내려 놓은 것을 알고 싶다면 궁금합니다.

Answer 3

꼭 필요한 것보다 더 어렵게 만들지 마십시오.우변 그냥 2의 입니다 2의 중간

에서 *들

1. 중간
2. 좌변 시작에 =을 가지고 있으며, 2로 종료하고 있습니다 : 귀하의 언어는 다음과 같은 특징이 있습니다
3. LHS와 RHS에있는 2의 수는 동일합니다.
4. LHS에는 **이 포함되어 있지 않습니다.

이 규칙은 문법에 넣어 쉽게 :

(P1) S -> 2=2 
(P2) S -> 2S2 
(P3) S -> 2*S2 

첫 번째 규칙은 우리의 기본 케이스이며, = 항상 LHS 및 RHS을 분리해야한다는 설정합니다. 또한 LHS은 2으로 끝나야하고 RHS는 2으로 시작해야 함을 입증합니다.

두 번째 및 세 번째 규칙은 더 긴 문자열을 얻기 위해 2을 더 추가 할 수있게합니다. 두 번째 규칙은 "항상 LHS 앞에 2을 넣을 수 있으며, 그렇게한다면 RHS의 끝에 하나를 넣어야합니다"라고 말합니다. 세 번째 규칙은 우리만큼 우리가 RHS "에 적어도 하나 S를 넣어 같이 LHS에 *를 넣을 수 있습니다

귀하의 예입니다.

222*2*22=222222 
S 
2S2     P2 
22S22     P2 
222*S222    P3 
222*2*S2222   P3 
222*2*2S22222   P2 
222*2*22=222222  P1 

2*2*2=222 
S     
2*S2     P2 
2*2*S22    P2 
2*2*2=222    P3 

2*222222*22=222222222 
S 
2*S2     P3 
2*2S22     P2 
2*22S222    P2 
2*222S2222    P2 
2*2222S22222   P2 
2*22222S222222   P2 
2*222222*S2222222  P3 
2*222222*2S22222222 P2 
2*222222*22=222222222 P1 

보여주는 포함 할이 문법에 대한 공식적인 정확성을 증명 . 유도에 의해 자료의 경우 :

증명한다 : (a) 언어의 모든 문자열이 생성되고, (2) 생성 된 모든 문자열이 언어입니다 우리는 모두 사용하여 유도 할 수 있습니다. 언어의 짧은 문자열 2=2입니다 , P1에 의해 생성되며 더 짧은 문자열이 생성되지 않습니다. 유도 가설 : 길이가 k보다 작은 모든 문자열이 생성되고 언어가 같다고 가정합니다 (길이가 k까지 동일 함). 유도 단계 : k보다 큰 길이의 문자열도 일치해야합니다. 문법에 의해 생성 된 언어로 길이가 k 이상인 문자열은 22x22 또는 2*x2 형식이어야하며 여기서 x은 다른 문자열 (또는 문법에 의해 생성됨)입니다. x 길이가 k보다 작거나이 인수는 x 자체에 재귀 적으로 적용됩니다. x은 길이가 k보다 작으므로 유도 가설은 문법에 의해 생성 될 수 있음을 나타냅니다 (또는 언어에 있음). 결과적으로 P2와 P3의 두 응용 프로그램 (대안 적으로 언어 자체의 정의에 의해)에서 두 가지 양식을 생성 할 수 있습니다 (대안 적으로 언어에 있음).

UPDATE :

주석이 *의 수를 2로 고정되어있을 가능성이 내 관심을 가져왔다.문법 정의의 변경이 필요합니다.

S -> 2S2 | 2*R2 
R -> 2R2 | 2*T2 
T -> 2T2 | 2=2 

이렇게하면 위의 인수가 비교적 사소하고 예측 가능한 방식으로 변경됩니다. 기본적으로, 우리는 P3의 애플리케이션 수를 추적하고 두 번째 이후의 애플리케이션을 더 이상 허용하지 않으며, 동시에 적어도 두 개의 애플리케이션을 본 후에 모든 비 터미널의 제거만을 허용합니다.