یک گرامر مستقل از متن، یک چهارتایی $(V, \Sigma,R,S)$ است که:

$V\quad (a)$ یک مجموعه‌ی متناهی از متغیرها است.

$\Sigma \quad (b)$ یک مجموعه‌ی متناهی و مجزای از $V$ از پایانه‌ها است.

$R \quad (c)$ یک مجموعه از قواعد است که هر قاعده شامل یک متغیر و یک رشته از متغیرها و پایانه‌ها است.

S \in V\quad (d)$ یک متغیر شروع است.

مثال: $G=(\{S\},\{a,b\},R,S)$ که مجموعه‌ی $R$ عبارت است از:

اگر $u$، $v$ و $w$ رشته‌هایی از متغیرها و پایانه‌ها باشند و $A \rightarrow w$، یک قاعده از گرامر باشد، می‌گوییم که $uAv$ به $uwv$ می‌رسد و می‌نویسیم $uAv \Rightarrow uwv$. اگر $u=v$ و یا اگر دنباله‌ی $u_1,u_2,…u_k$ وجود داشته باشد که $k\geq 0$ و

$$u=u_1 \Rightarrow u_2 \Rightarrow … \Rightarrow u_k=v$$

آن‌گاه می‌نویسیم $u \Rightarrow v$.

زبان گرامر عبارت است از تمام رشته‌های $w$ از عناصر $\Sigma$ به قسمی که $S \Rightarrow w$.

به عنوان نمونه در مثال فوق داریم: $S \Rightarrow abab$ و $S\Rightarrow aaabbb$ و … و به این ترتیب زبان گرامر فوق عبارت‌است‌از: $\{abab,aaabbb,aababb,…\}$

اگر $A$ زبان یک گرامر مستقل از متن باشد، نشان دهید عدد $p$ وجود دارد که اگر $s$ یک رشته متعلق به $A$ با طول بیش‌تر از $p$‌باشد، آن‌گاه می‌توان $s$ را به ۵ قسمت افراز کرد یعنی $s=uvxyz$ بع قسمی که سه شرط زیر برقرار شوند (منظور از $|w|$ طول رشته‌ی $w$ و منظور از $xy$ رشته‌ی حاصل از پشت سر هم قرار دادن رشته‌های $x$ و $y$‌است):

$\quad (a)$ برای هر $i\geq 0$، $uv^ixy^iz \in A$

$|vy|> 0 \quad (b)$

$|vxy|\leq p \quad (c)$

• سوال بعد
• سوال قبل