집합 이론에서의 concat 표기법

Question

나는 automata 이론 수업을 위해 숙제를하고있다. 지금까지 정규 표현식을 포함하고있는 그 증명은 너무 미쳤습니다. 어쨌든, 내 질문은 연결에 대한 적절한 설정 표기법은 무엇입니까? 예를 들어, R + S가 R 유니온 S와 같을 것이라는 것을 알고 있지만, 나에게있어서 연결에 해당하는 집합 이론이 무엇인지 기억하지 못합니다.

내가 그 (것)들에 잘 일할 것이라는 점을 나는 생각한다대로 아무 문제도 배치하지 않을 것이다, 누군가는 저에게 바른 방향으로 조금 찔레를 줄 수 있 었는가?

Answer 1

나는 당신이 정규 세트의 연결을 말하는 것이라고 믿습니다. 일반적으로 연결 또는 점 연산자는 일반 세트의 연결을 나타냅니다. 정규 표현식에도 동일한 표기법이 적용됩니다. 예컨대

• AB = A * B = {XY : X ∈ &의 Y ∈의 B}

정식 정규 세트가 Kleene 등급으로 semiring 멱등 인 Kleene 대수를 형성 공리의 집합을 만족시키는 연산자. 멱등 원과 같은 대수 (algebras)에서 곱셈은 대개 을 통해 연결 또는 도트 연산자로 표현됩니다. 이것이 정규 세트의 연결 (Kleene 대수학에서의 곱셈 연산)이 연결 또는 도트 연산자로 표시되는 이유입니다. 정규식에 대해서도 마찬가지입니다.

Answer 2

문자열이 집합이 아니기 때문에 R + S는 R 유니온 S와 같지 않습니다. 문자열은 알파벳이며 세트입니다. (기술적으로는 문자열을 순서쌍 (char, index)의 집합으로 나타낼 수 있지만).

연결하려는 경우 R + S를 말해야합니다. 일반 세트를 연결할 수 없습니다.

그러나 문자열의 세트를 연결할 수 있습니다. 문자열 U와 V의 집합에 대해 연결, UV는 uv 형식의 모든 문자열로 구성됩니다. 여기서 u는 U의 문자열이고 v는 V의 문자열입니다. 교차 제품과 비슷합니다.