문맥 자유 문법으로 문자 수를 가진 언어를 기술 할 수 있습니까?

Question

독일 HBCI/FinTS 프로토콜을보고 있습니다. 이 프로토콜의 한 가지 특점은 이진 Blob을 포함 할 수 있으며 접두사는 @NUM_OF_BINARY_CHARS@입니다. 다음과 같이 그렇지 않으면 프로토콜은 문법은 (조금 단순화, 단말기에 의해 인용되는 ") 아주 간단 설명 할 수있다 :

는

message = segment+ 
segment = elements "'" 
elements = element "+" elements | element 
element = items 
items = item ":" items | item 
item  = [a-zA-Z0-9,._-]* | escaped item 
escaped = ?[-@?_-a-zA-Z0-9,.] 

The @ is missing here! 

샘플 메시지는이

FirstSegment+Elem1+Item1:Item2+@4@:'+@+The_last_four_chars_are_binary+Elem4'SecondSegment+Elem5' 

수있는이 같은 것을 볼 수 있었다 (바이너리 문자열의 이스케이프와) 언어는 문맥 자유 문법에 의해 설명 될 수?

Answer 1

아니오,이 언어는 문맥 자유가 아닙니다. 당신이 설명하는 형식이 언어

본질적으로 동일하다

{@ n @ w | n은 자연수이고 | w | = n}

문맥없는 펌핑 보조 정리를 사용하여 컨텍스트 프리가 아닌 것으로 나타낼 수 있습니다. 펌핑 길이를 p로하고 문자열 @ 1 ^p @x ^{1111 ... 1 (p 회)}을 고려하십시오. 이것은 길이가 111 ... 1 (p times) 인 이진 데이터 조각의 문자열 인코딩입니다. 이제 문자열을 u, v, x, y, z로 나눕니다. 여기서 | vy | > 1 및 | vxy | ≤ p. v 또는 y가 @ 기호 인 경우 uv xy z는 @ 기호가 충분하지 않기 때문에 언어에 없습니다. v와 y가 완전히 1 ^p에 포함 된 경우 이진 데이터 문자열의 크기가 올바르지 않기 때문에 문자열을 펌핑하면 언어가 아닌 문자열이 생성됩니다. 마찬가지로, v와 y가 순전히 x ^{111 ... 1 (p 배)}에 포함되어 있다면 펌프를 올리거나 내리면 페이로드가 잘못된 크기가됩니다. 마지막으로 v가 길이 필드에 있고 x가 페이로드에 있으면 v가 십진수로 쓰여지기 때문에 v와 x를 동시에 펌핑하면 페이로드의 길이가 잘못됩니다 (따라서 여분의 문자가 페이로드 크기를 10 배 증가시킵니다) x의 길이는 그렇지 않습니다.

희망이 도움이됩니다.