언어 사양을 프로덕션 규칙으로 변환 (CFG인지 CSG인지 확실하지 않음)

Question

입력 문자열이 지정된 언어 사양에 맞는지 확인하는 함수를 작성해야합니다. 나는 이것이 표준 CFG -> Chomsky Normal Form, CYK 파싱이라고 생각했지만 언어의 규칙들 중 하나는 이런 일이 일어나지 못하도록 막고있다. 우리는 터미널 {a,b,c,d,e,f,P,Q,R,S}를 정의하는 경우

규칙의 일부

후 유효한 문자열은, 간단

1) 분리의 소문자 단말기의 모든
2) 'x'를 다음 유효한 문자열 인 경우 그래서 내지 Sx

이다하지만 X와 Y가 유효한 입력 문자열 인 경우 제 규칙은 그렇게이다)

3 PXY, QXY, RXY

여기서 대문자 {P,Q,R} 나머지 단자 X와 Y는 비끝있다이다.

이 모양의 제작 규칙은 어떻게됩니까?

XY -> PXY (and QXY, RXY) 

과 같은 것으로 생각했지만 두 가지 문제가 있습니다. 첫 번째는 이것이 CFG 규칙이 아니라는 것입니다 -이 언어가 CSG를 ​​대신 정의한다는 의미입니까?

그리고 두 번째

이 작동하지 않는다는 것입니다 때문에

XY -> PXY - 모든 경우에> PPXY

되지 않을 것 유효한 메시지.

Answer 1

나는이 문법이 당신이 말하는 것을 오해하지 않는 한 문맥이 없다고 생각합니다.

첫째, 우리는 이제

A -> a | b | c | d | e | f 

을 얻을 A는 처음 두 규칙을 사용하여 방금 만든 몇 가지 유효한 문자열에게 확장 비 터미널하자하자, 두 번째 규칙은 말한다 당신은 문자열을 구축 할 수있는 경우 ω S ω을 만들 수 있습니다. 우리는 마지막으로

A -> SA 

로, 당신은 당신이 두 개의 문자열 X와 Y가있는 경우, 다음이 될 것이라고 생각

PXY 
QXY 
RXY 

한 가지 방법으로 그들을 함께 결합 할 수 있다고 말한 것으로 인코딩 할 수있다 두 개의 유효한 문자열 (Q 또는 R과 동일)이 뒤에 오는 문자열 P를 생성합니다. 따라서 당신이 최종 문법이 도움이

A -> a | b | c | d | e | f 
A -> SA 
A -> PAA | QAA | RAA 

희망을주는 규칙

A -> PAA | QAA | RAA 

를 추가 할 수 있습니다!