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

다음과 같이 말하십시오 :

L = { w s : | 승 | = | s |w , s ∈ { 0 , 1}※, w ≠ s }

엘#= { w # s : | 승 | = | s |w , s ∈ { 0 , 1}※, w ≠ s }

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

씨에프엘

그리고 아래에서 대한 증명을 추가합니다 .엘#∉ C에프엘

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

증명이 :엘#∉ C에프엘 L#∉CFL

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

p > 0

L

s=0m1p#0p1m

m=p!+p

s∈L

|s|>p

s=uvxyz

|vy|>0

|vxy|≤p

uvjxyjz∈L

j≥0

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

• 또는 포함 된 경우 : 이면 포함되지 않으므로 이 모순됩니다.v
  v
  y y
  # #
  i=0 i=0
  uxz uxz
  # #
  uxz∉L uxz∉L

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

  v

  y

  y

  #

  #

  i=0

  i=0

  uxz

  uxz

  w#x

  w#x

  |w|<|x|

  |w|<|x|

  uxz∉L

  uxz∉L

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

  v

  y

  y

  #

  #

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

  v

  #

  #

  y

  y

  |v|<|y|

  |v|<|y|

  i=0

  i=0

  uxz

  uxz

  w#x

  w#x

  |w|>|x|

  |w|>|x|

  uxz∉L

  uxz∉L

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

  v

  #

  #

  y

  y

  |v|>|y|

  |v|>|y|

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

  v

  #

  #

  y

  y

  |v|=|y|

  |v|=|y|

  |vxy|≤p

  |vxy|≤p

  v

  v

  1p

  1p

  s

  s

  y

  y

  0p

  0p

  v=1k

  v=1k

  y=0k

  y=0k

  1≤k≤p

  1≤k≤p

  k<p/2

  k<p/2

  j≥0

  j≥0

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

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

  m=p+j⋅k

  m=p+j·k

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

  uvj+1xyj+1z∉L

  j=(m−p)/k

  j=(m−p)/k

  m−p

  m−p

  k

  k

  m=p+p!

  m=p+p!

  m−p=p!

  m−p=p!

  p!

  p!

  1≤k≤p

  1≤k≤p

답변