카테고리 보관물: cs

cs

| w |로 ws를 사용하는 방법 = | s | 그리고 w ≠는 컨텍스트가없는 반면 w # s는 그렇지 않습니까? :엘#∉ C에프엘L#∉CFLL_{\#} \notin CFL 그

seperator 가 두 언어를 다르게 만드는 이유는 무엇 입니까?

#

다음과 같이 말하십시오 :

L={ws:|w|=|s|w,s{0,1},ws}

L#={w#s:|w|=|s|w,s{0,1},ws}

다음 은 을 로 나타내는 증명 및 그래머입니다.

L

CFL

그리고 아래에서 대한 증명을 추가합니다 .

L#CFL

부호가 실제로 차이를 만들어 줍니까 ? 그렇다면 왜 그렇습니까? 그렇지 않다면, 어떤 증거 중 어느 것이 틀렸고 어디에 있습니까?

#

증명이 :

L#CFL

그 모순로서 가정 .
문맥이없는 언어에 대해서는 펌핑 보조로 보장되는 을 의 펌핑 상수라고 하자 우리는 이라는 단어를 고려합니다.
여기서 이므로 입니다. 부터 , 펌핑 렘마에 따르면, 와 같이
, 및 각 에 대해 입니다 .

LCFL

p>0

L

s=0m1p#0p1m

m=p!+p

sL

|s|>p

s=uvxyz

|vy|>0

|vxy|p

uvjxyjzL

j0

우리는 사례별로 모순을 얻습니다.

  • 또는 포함 된 경우 : 이면 포함되지 않으므로 이 모순됩니다.
    v

    y

    #

    i=0

    uxz

    #

    uxzL

  • 두 경우 와 에 남아있는 : 대한 그런 , 우리가 얻을
    형식이다 , 어디따라서 입니다.

    v

    y

    #

    i=0

    uxz

    w#x

    |w|<|x|

    uxzL

  • 와 가 모두 맞다면 : 마지막 경우와 비슷합니다.

    v

    y

    #

  • 가 남아 있으면 , 가 오른쪽에 있고: 이면 는 형식입니다 . 여기서따라서 입니다.

    v

    #

    y

    |v|<|y|

    i=0

    uxz

    w#x

    |w|>|x|

    uxzL

  • 가 남아 있으면 , 가 오른쪽에 있고: 마지막 경우와 비슷합니다.

    v

    #

    y

    |v|>|y|

  • 가 남아 있으면 , 가 오른쪽에 있고: 가장 흥미로운 경우입니다. 부터 , 는 의 부분에 , 는 부분에 포함되어야합니다. 따라서 동일한 (실제로 이어야 함)에 대해 및 를 유지합니다 . 각 에 대해
    이므로

    v

    #

    y

    |v|=|y|

    |vxy|p

    v

    1p

    s

    y

    0p

    v=1k

    y=0k

    1kp

    k<p/2

    j0

    uvj+1xyj+1z=0m1p+j·k#0p+j·k1m

    m=p+j·k

    다음이를 주장한다 모순하여. 이를 달성하기 위해서는 취해야합니다 . 이는 를 로 나눌 수있는 경우에만 유효합니다 . 우리는 선택했음을 기억하십시오따라서, 그리고원하는대로 로 나눌 수 있습니다.

    uvj+1xyj+1zL

    j=(mp)/k

    mp

    k

    m=p+p!

    mp=p!

    p!

    1kp



답변

당신의 증거는 정확하고 틀 렸습니다. 혼란이 있던 곳을 정리하는 데 시간이 걸렸습니다. 그러나 Yuval의 도움으로 이해했다고 생각합니다.

세 가지 언어를 고려해 봅시다

L=={xy|x|=|y|,xy},L#={x#yxy}, andL=#={x#y|x|=|y|,xy}.

우리가 보았 듯이 여기 , 상황 무료입니다. 트릭은 문법에서 "오른쪽에"기호를 생성하지만 나중에 "왼쪽에"(또는 다른 방법으로) 계산하여 일치하지 않는 기호가 일치하는 위치에 나타나는지 확인하는 것입니다. 길이 조건은 균일 한 길이로 줄어들 기 때문에 사소합니다.
스택을 사용하여 위치를 일치시키는 유사한 아이디어로 NPDA를 구성 할 수 있습니다.

L=

L#

에도 컨텍스트가 없습니다 . 일치하지 않는 기호는 처음부터 멀리 떨어져있는 동일한 거리에 나타납니다. 분리기. 동일하지 않은 길이는 별도로 점검 할 수 있습니다. 비결정론은 두 옵션 사이에서 "선택한다".

이제 에는 컨텍스트 가 없습니다 . 다른 두 언어의 증거가 깨지는 이유는 다음과 같습니다.

L=#

  1. 의 문법 에서 중간에 구분 기호를 생성해야하는 경우 "왼쪽"에서 "오른쪽"으로 기호를 "재 할당"할 수 없습니다.
    L=

  2. 대신에 "동의 길이가 동일하지 않은 경우 또는 불일치"우리는 "길이가 같아 수락 경우에 가지고 불일치". 비 결정론은 우리를 도울 수 !

직관적으로 요약하면, " "및 " " 형식의 조건은 스택으로 확인할 수 있다는 의미에서 "문맥이없는"상태입니다. 유한 제어를 사용하지 않습니다. 따라서 PDA는 둘 중 하나만 수행 할 수 있습니다.

xy

|x|=|y|

대한 PDA는 실제로 와 대한 이러한 조건을 확인 하지 않기 때문에 "속임수" ; 단어를 다른 방식으로 나눕니다. 구분 기호가 있으면 더 이상 사용할 수 없습니다.

L=

x

y


부록 : 나는 CFL이 역 동 형성에 대항하여 닫혀 있기 때문에 과감하게 주장 했습니다 . 그것이 사실이지만 그 와 그것을 제외하고 신원이 삭제 관련이없는입니다. ; 에 대해서는 아무 것도 말할 수 없습니다 .

L=CFLL=#CFL

f(L=#)=L=

f

#

f1(L=)=L#

L=#


부록 II : 참고 에는 컨텍스트가 거의 없습니다. 따라서 을 사용하면 교차점에 대해 CFL이 닫히지 않는 좋은 예가 있습니다.

L={x#y|x|=|y|}

LL#=L=#


답변