예 일반 아닙니다

Question

A "반 일반"문법은 허용 하나 인 형태의 규칙 :

X → y 
X → y Y 
X → Y y 

X와 Y는 단일 비 터미널에서

하고, x와 y는 단일 터미널입니다.

는 예를 들어,이 언어는 A에 대한 반 정규 문법이다 + B +

S → a S 
S → a A 
A → A b 
A → b 

언어 일반 언어가 아닌 반 정규 문법의 예를 준다. 언어가 무엇이고 왜 그것이 규칙적이지 않은지 말하십시오.

Answer 1

무엇 -는 빈 문자열을 표현하는 것으로

S := aT | - 
T := Sb 

에 대한; 당신은 규칙 성을 바꾸지 않고 원하는 경우 이것을 단일 터미널 기호로 대체 할 수 있습니다. 이것은 규범적인 비정규 언어 인 a^n b^n을 생성합니다. 정규 언어 또는 Myhill-Nerode 정리에 대해 펌핑 보조 정리를 사용하여 쉽게 증명할 수 있습니다.