문맥 자유 문법 문법

Question

CFG 문항에 약간의 혼동이 있습니다. 이 문법

S -> aS | bA 
A -> c | cA 


A: a*bc* 
B: a*b*c* 
C: a*b*c 
D: a*bc+ 

내 혼란 허용되는 다음의

내가 0 번 이상을 의미하는 것으로 이해 * 내 자리 잡고 있습니다.

A의 경우 여러 개의 a (반복됨), b (bA), c가 차례로 포함될 수 있으므로이 기능이 작동하지 않는 것으로 나타났습니다. 그러나 c는 *를 가질 수 없습니다. b (bA)를 호출하는 것처럼 A는 항상 c를줍니다. *는 당신이 0이 될 수 있다고 말합니다.

B의 경우 c에 *가 있으므로 동일한 규칙이 적용되지 않습니다.

C는 다중 a (aS 반복), 가능한 b 다음에 c가 올 수 있으므로이 MAYBE가 작동하는 것을 봅니다. 나는 b * 때문에 여기에서 혼란 스럽다. 이것은 잠재적으로 여러 개의 b를 가질 수 있음을 의미합니까? 그렇다면 'b'는 위에 정의 된 문법 컨텍스트로 한 번만 발생할 수 있기 때문에 이것은 사실이 아닙니다.

D의 경우이 작업은 여러 번 발생할 수 있으므로 (반복), b는 한 번 발생하고 c는 한 번 이상 발생합니다.

그래서 A no, B no, c maybe ?, d 예.

이 생각이 옳았는지 잘못 되었습니까? *가 나를 버리고있다.

Answer 1

옵션 D는 정확하게 문법을 나타내며, 다른 옵션은 항상 어느 시점에서 실패하므로 제대로 맞 춥니 다. 'c'는 문법에 의해 0이 허용되지 않기 때문에 옵션 A가 실패합니다. 옵션 B와 C는 하나의 'b'가 허용되기 때문에 실패합니다.