1
언어 A = a*b*은 (는) 정기적 인 언어입니다. 그러나 그것의 상위 집합이 비정규 언어인지 궁금합니다. 그리고 수퍼 집합은 같은 알파벳을 사용해야합니다. {a, b}일반 언어 a * b *의 경우, 비정상적인 수퍼 집합이 있습니까?
A
답변
2
예, 있습니다. B = b n ab n (여기서 n> 0) 즉, b으로 시작하고 가운데에 a을 포함하는 문장을 사용합니다. 이 언어는 pumping lemma이 적용되지 않기 때문에 비정규입니다. B의 모든 단어에는 의 단어가 들어 있지 않으므로 ba 하위 문자열이 포함되어 있기 때문에 A과 완전히 별개입니다.
A과 B의 합집합은 A의 비정규 수퍼 셋입니다.
또한 모든 정규 언어가이 방법으로 확장 될 수있는 것은 증명하기 쉽습니다. 예를 들어 주어진 알파벳에 대해 가능한 모든 단어의 언어가 정의 상으로는 틀리기 때문입니다. 동일한 알파벳에 대해이 언어의 중요하지 않은 수퍼 집합을 공식화 할 수있는 방법이 없기 때문에 주어진 알파벳에 대한 "클레이 네 스타"언어의 모든 수퍼 집합도 규칙적입니다. 보다 일반적
보체 언어 모든 언어 A (C = Σ * \ A)는 비 정기적 상위가되지 유한 C 때문에 및 모든 부분 집합 정의상 일반 (유한 언어는 항상 일반)이므로 A와의 임의의 조합도 일반 입니다 (정규 언어 2 개 조합은 규칙적입니다).
왜 없어야하나요? 정규 언어'A'와 비 정규 언어'B'의 결합은 모두'A'와 비정규의 수퍼 세트입니다. – biziclop
... 적어도 분리 문자가있는 경우. – biziclop