경우 문맥 자유이고, 일반이며, 다음 문맥 자유입니까? PDA 와 을 허용하는 DFA 가

다음 연습 문제를 해결해야합니다.

만약 에 문맥이없고 이 규칙적이라면 (즉, 오른쪽 몫 )은 문맥이 없습니다. $L$

$R$

$L / R = {w ∣ \exists x \in R s.t w x \in L}$

L/R={w∣∃x∈Rs.twx∈L}

을 허용하는 PDA 와 을 허용하는 DFA 가 있어야 함을 알고 있습니다. 나는 이제 이러한 오토마타를 올바른 몫을 받아들이는 PDA에 결합하려고합니다. 내가 그것을 구축 할 수 있다면 에 컨텍스트가 없음을 증명했습니다 . 그러나 나는이 PDA를 구축하고 있습니다. $L$

$R$

$L / R$

L/R

이것이 내가 한 거리입니다.

결합 된 PDA에서 상태는 분리 된 오토마타 상태의 직교 곱이다. 그리고 가장자리는 DFA의 가장자리이지만 앞으로 L의 원래 PDA의 최종 상태에 도달 할 수있는 것만 DFA의 가장자리입니다. 그러나 공식적으로 작성하는 방법을 모릅니다.

답변

힌트는 다음과 같습니다.

처음에는 의 단어 일부를 받아들이고 테이프를 소비하면서 기계가 필요합니다 . 그런 다음 아무 것도 소비하지 않으면 에서 기계를 최종 상태로 밀어 넣을 단어를 찾아야 합니다. 에서 선택한 단어 는 계산의 후반부에 입력 단어의 역할을합니다. $L$

$R$

분명히, 비결정론은 두 기계 사이의 제품과 마찬가지로 역할을 수행 할 것입니다. 이를 공식화하는 비결은 입력이 입력이 아니라 에서 발생한다는 사실을 처리하도록 제품을 조정하는 것 입니다. $R$

답변

Cartesian 제품으로 무엇을 얻고 있는지 잘 모르겠습니다. 이것은 두 오토마타를 동시에 시뮬레이트하여 교차점을 제공합니다. 그러나 당신은 모든 단어를 식별 할 에서 접미사가 ! 즉, 직관적 인 수준입니다. $L$

$R$

입력이 가정하십시오 . 분명히, 우리는 가능한 모든 연속을 확인할 수는 없지만 ( 멤버십의 경우) 유한 한 수만 확인할 수 있습니다. Artem의 의견 이 여기에 가장 도움이됩니다. 우리 는 접미사 가 무엇인지 추측 하고 두 automata를 실행합니다. $w \in Σ^{*}$

w∈Σ∗

$R$

$x$

하자 및 위해 PDA를 및 NFA 각각. 다음과 같이 오토 마톤 를 구성하십시오. 입력 에서 시뮬레이션 . 가 소비 된 후 상태를 에서 유지하면서 과 의 수정 된 교차로 로 . 이제 모든 전환에 대해 가상 입력에서 다음에 어떤 심볼이 있는지 결정적으로 결정하십시오. 수락 IF 및 두 구성 요소에만 경우에 동시에 최종 상태에 도달 $A_{L}$
AL
$A_{R}$
AR
$L$
L
$R$
R
$A$
A
$w \in Σ^{*}$
w∈Σ∗
$A_{L}$
AL
$w$
w
$A_{L, R}$
AL,R
$A_{L}$
AL
$A_{R}$
AR
$A_{L}$
AL
$w$
w
$A_{L, R}$
AL,R
$w$
w
연속 있으므로 및 입니다. $x$
x
$w x \in L$
wx∈L
$x \in R$
x∈R

공식적인 문법을 사용할 수도 있습니다. 두 개의 문법으로 동시에 파생 할 수있는 방법을 알고 있습니까? 일반적으로 어떻게 적응시키는 지 명확하지 않으므로 접미사를 처리 할 수 있습니다. 사용 촘스키 정규형하는 데 도움이됩니다. $G_{L}$

과 이 모두 Chomsky 일반 형식으로 제공 되었다고 가정합니다 . 가장 오른쪽에있는 비 터미널이 구별되도록 수정 하고 시작 기호를 새 시작 기호로 만드십시오. 과 에서 병렬로 파생되는 문법으로 이어지는 비 터미널의 새 버전의 구별 된 버전을 소개합니다 (비 터미널은 비 터미널의 쌍입니다). 두 문법이 모두 터미널 기호에 동의하면 복합 비 터미널을 삭제하십시오. 이러한 방식에서, 접미사 그것이 유도 될 수있는 경우와있는 경우에만 삭제 이상에서 그것은 남아 . $G_{L}$
GL
$G_{R}$
GR
$G_{L}$
GL
$G_{L}$
GL
$G_{R}$
GR
$G_{L}$
GL
$G_{L}$
GL
$G_{R}$
GR
$w \in L / R$
w∈L/R

답변

Raphael의 대답을 사용하는 것이 훨씬 쉽지만 여기에는 automata 대신 클로저 속성을 사용하는 대안이 있습니다.

하자 언어합니다. 우리는 단어를 읽고 싶지만 가 언어로되어 있는지 에게 묻습니다 . 그래서 우리 는 “삭제” 된 에서 새로운 언어를 만들고 싶습니다 . 우리는 동질성을 사용하여 그것을 할 수 있지만 에서 문자를 제거 할 수 있습니다. 해결 방법 : 알파벳을 2로 나누고 와 다른 문자를 사용하십시오 . $L \subseteq A^{*}$
L⊆A∗
$w$
w
$L$
L
$w x$
wx
$L$
L
$x$
x
$w$
w
$w$
w
$x$
x

더 공식적으로 :

1) 만들기 에서 단어의 각 문자로는 0 또는 1 태그

2) 일반 언어와 교차 그것 입니다. 이렇게하면 모든 0이 1보다 먼저 나오고 두 번째 부분은 에서 나옵니다 . 의 정확한 의미 는 독자에게 남아 있습니다.

3) 와 .

사용 된 폐쇄 특성 : 동형 이미지, 사전 이미지, 일반 언어와의 교차. 장점 :이 증명은 다른 가족에 적용됩니다 (예 : 문맥이없는 것을 일반으로 대체). $L^{'} \subseteq (A \times {0, 1})^{*}$
L′⊆(A×{0,1})∗
$L$
L

$(A \times 0)^{*} (R \times 1)$
(A×0)∗(R×1)
$R$
R
$\times$
×

$(a, 0) \to a$
(a,0)→a
$(a, 1) \to ε$
(a,1)→ε

답변

Exit mobile version

How IT

언제든지 물어보세요.

경우 문맥 자유이고, 일반이며, 다음 문맥 자유입니까? PDA 와 을 허용하는 DFA 가

답변

답변

답변

답변