[일반] 형식언어 질문

[기괴공학도(mecheng98)]

이거 증명 어떻게 해요??

- dc official App

[coco(175.196)]

Production 좌변이 하나의 (nonterminal) symbol로 되어있기 때문인거 같음. X -> string aaa를 ...X...에 적용했을 때 ...X (...) 가 ...aaa(...)로 변형되더라도 오른쪽 (...)에 영향을 안 주므로 (...)에 production을 먼저 적용하나 나중에 적용하나 상관이 없게되는 것 같음.

[기괴공학도(mecheng98)]

네 저도 문맥자유문법이어서 가능한 것 같다고 생각하는데, 수학적으로 말하지 못하겠어요. - dc App

[coco(175.196)]

문맥자유문법이기 때문에 스트링 ....A....B... 에 대한 변형이 있을 때, 이를 ...A 와 ...B...의 두 스트링으로 분할 을 하고 ...A과 ....B...에 대한 각각의 변형이 적용된 결과를 다시 왼쪽 오른쪽 스트링을 붙인 것으로 볼 수 있을 것 같아요. 이렇게 생각하면 오른쪽 스트링 ....B...이 먼저 변형되고 후에 왼쪽 스트링 ...A가 변형된 걸로 볼 수 있으니까, 그리고 nonterminal symbol은 반드시 변형되어야 하므로 항상 맨 오른쪽 nonterminal symbol은 반드시 변형 되어야 하므로 제 생각에도 그런 식으로 하다보면 가능 할 것 같아요.

[기괴공학도(mecheng98)]

오 감사합니다 - dc App