서로 다른 상수 l, r이 주어졌다고 합시다.
집합 X를 X := {l, r}로 두고
유한열 (S_n)_(n＜ω)을 S_0 := {l r}, S_(n + 1) := { x y | x, y ∈ S_n } ∪ { l x r | x ∈ S_n }으로 두면
집합 S ⊆ X*에 대하여 다음 둘이 동치임을 어떻게 보일까요:
1) S = { z ∈ X* | (z = l r) ∨ (∃x, y ∈ S) (z = x y) ∨ (∃x ∈ S) (z = l x r) }.
2) S = { z ∈ X* | (∃n ＜ ω) (z ∈ S_n) }.
여기서 서수 ω는 자연수의 집합이고, 집합 X*는 X의 유한열의 집합입니다 (kleene-star).
해당 댓글은 삭제되었습니다.
답변 감사합니다 - dc App
집합 2가 1에 포함되는건 정의에 의해 쉽게 증명됨 1이 2에 포함되는건 귀류법 써서 2에 포함 안되는 가장 길이가 짧은 문자열 잡고 모순 보이면 됨
앗 그런 방법이! 감사합니다. - dc App