2
L1={anb2m|n,m≥1}
L2={anb3n|n≥0}
L = L1 ∩ L2
내가 L1 일반 언어이고 L2은 PDA에 의해 표현 될 수 있다는 것을 알고 주어진.
그러나 나는 L이 {a2nb6n|n≥1}이라는 대답을 이해하지 못합니다. 이 솔루션은 어떻게 계산 되었습니까?
A
답변
3
언어는 유효한 문자열로만 구성되어 있으므로 여기에있는 것은 정수 연산에서의 간단한 문제입니다. 문제의 본질에 도달하기 위해서는 공식 언어의 우아한 의상을 제거하는 것만으로 충분합니다.
두 세트 L1 및 L2은 {acount(a)bcount(b)|j,k≥0}의 부분 집합입니다. 즉, 어떤 숫자가 이고 그 뒤에 숫자 s가옵니다. 의 조건은 m≥1 일 경우 2m이어야하므로 count(b)이 양수가되도록 제한합니다. L2의 조건은 count(b)이 정확히 3×count(a)으로 제한됩니다.
이제 술어로 정의 된 두 세트의 교차는 두 술어가 모두 참인 것과 같은 요소 세트입니다. 따라서 count(b)은 2와 3으로 나눌 수 있어야합니다. 즉, 6으로 나눌 수 있어야합니다. 즉, 양수가 n 인 경우 6n이어야합니다. 그리고 count(a)은 b의 세 배만큼 정확히 2n이어야합니다. 그것은 당신에게 제공된 답을 제공합니다.
L2과 마찬가지로 L은 규칙적이 아니지만 매우 유사한 PDA로 구현할 수 있습니다.
[다른 알파벳이있는 두 언어의 교차점은 무엇입니까?] 가능한 복제본 (http://stackoverflow.com/questions/15213955/what-is-the-intersection-of-two-languages-with-different- 영문) – veganaiZe
@rici 그게 뭔지는 모르겠지만,'L'은 기본적으로 해결책이 제공됩니다. – totoro
@totoro : 좋아, 혼란 스러움이 무엇인지 명확하게하기 위해 질문을 편집하려고했습니다. 이런 질문은 http://cs.stackexchange.com/에서 정말 프로그래밍과 관련이 없기 때문에 물어야합니다. 그러나 당신이 당신의 일을 보여 주려하지 않는 한 당신의 질문은 그곳에서 잘 받아 들여지지 않을 것이라는 점에 유의하십시오. – rici