https://gall.dcinside.com/mgallery/board/view/?id=math&no=22410&_rk=Zxh&page=1


https://math.stackexchange.com/questions/96880/need-help-in-formal-grammar-for-the-l-wcw-w-in-a-b-ast/3916848#3916848




사실 원래 요청은 자기가 한 답변을 보고 검증해달라는 거였는데

설명을 추가해도 너무 복잡하고 도저히 이해가 가지 않아서 포기함


뭔가 저게 되는 아이디어가 있을텐데 이런식의 CS문제 솔루션 특징이

글로 설명해서는 죽어도 이해가 안간다는거임 아마 실제로 대면해서 상호작용하면서 문제풀이를 들으면

충분히 이해할 수 있는 뭔가가 있으리라 생각함


그리고 저게 저렇게 답이 복잡해야만 하나? 하는 생각이 들어서 내 풀이를 써봄







(그룹1)

S -> ASA'

S -> BSB'

S -> C


(그룹2)

CA' -> CA

CB' -> CB


(그룹3)

AA' -> A'A

AB' -> B'A

BA' -> A'B

BB' -> B'B


규칙 그룹3을 통해 AAAAA' =>* A'AAAA 형태의 변환이 가능


(그룹4)

A -> a

B -> b

C -> c





규칙 그룹 1을 써서

S =>* AABCB'A'A'


규칙 그룹 2~3 반복적용해서 C이후의 문자열 BAA를 뒤집음

AABCB'A'A' =>* AABCAAB


규칙 그룹 4를 써서

AABCAAB =>* aabcaab