CFL 평등의 결정 가능성 있습니다. 문맥이없는 문법을 감안할 때

다음과 같은 문제를 결정할 수 있습니다.

문맥이없는 문법을 감안할 때

이며,

()=

?

다음과 같은 문제는 결정할 수 없습니다.

문맥이없는 문법 주어 졌을 때

,

()=

?

결정 가능한 동등성 L ( G ) = M을 갖는 문맥없는 언어 의 특성이 있습니까?

미디엄

()=미디엄



답변

동등성에 대한 일반적인 특성이 확실하지 않지만 Hopcroft와 Hunt and Rosenkrantz resp의 다음 논문이 있습니다. 좋은 시작이 될 수 있습니다.

  • John E. Hopcroft, 문맥이없는 언어에 대한 동등성과 격리 문제에 대하여, 컴퓨팅 시스템 이론 3 (2) : 119-124, doi : 10.1007 / BF01746517 ;
  • Harry B. Hunt, III 및 Daniel J. Rosenkrantz, 공식 언어의 동등성과 격리 문제 , ACM 저널 24 (3) : 387–396, 1977, doi : 10.1145 / 322017.322020 .

만약, 특정의 Hopcroft 쇼 규칙적 후 L ( G는 ) = M은 IFF decidable이고 M은 즉, 존재, 묶여 N 워드 w는 1 , w는 2 , , w N 세인트 M w * 1 w * 2w n .

미디엄

()=미디엄

미디엄

1,2,,

미디엄12


답변

오래된 실을 가져 와서 죄송합니다. 그러나 여기에 관련이있는 것이 있습니다.

하자 pCFL은 순열 폐쇄의 CFLs의 클래스합니다. pCFL 의 평등 문제 는 결정 가능합니다.

감안 Σ = { σ (1) , , σ N } ,하자 W L = { # 1 ( w ) , , # N ( w ) | w L을 } . Parikh의 정리함으로써, W L은 때마다 semilinear이다 L은 상황 무료입니다.

Σ={σ1,,σ}

={#1(),,#()}

만약 지금, pCFL , 우리가 그 w L IFF # 1 ( w ) , , # N을 ( w ) W L . 따라서, pCFL 에서 L 1 , L 2대해 , L 1 = L 2 iff W L 1 = W L 2 . 그러나 반 선형 세트의 동등성은 결정 가능합니다. 보다:

#1(),,#()

L1,L2

L1=L2

WL1=WL2

이것은 대답을 알고 싶은 질문을 제기합니다. 주어진 문맥이없는 언어가 순열 닫혀 있는지 여부를 결정할 수 있습니까?


답변