نظریه پاریک

**قضیهٔ پاریک**  یکی از قضایای علوم کامپیوتر نظری است که در سال ۱۹۶۱ توسط روهیت پاریک(Rohit Parikh) اثبات شده‌است و در سال ۱۹۶۶ اثبات ساده تری برای آن ارائه شده‌است.[3] اثبات می‌کند که یک زبان مستقل از متن روی یک الفبای تک حرفی باید منظم باشد. از قضیهٔ پاریک می‌توان در اثبات مستقل از متن بودن یا نبودن یک زبان استفاده کرد. علاوه بر این از این قضیه برای اثبات این که یک زبان حاوی رشته‌ای با تعداد برابری از دو پایانه داده شده هست یا خیر.[1] این قضیه بیان می‌کند که اگر توالی نشانه‌ها در نظر گرفته نشود آنگاه زبان‌های مستقل از متن از نظر مجموعه‌های منظم و نشان دادن وجود یک زبان مستقل از متن ذاتاً مبهم غیر متمایزاند.

## تعاریف مهم
اگر \Sigma = \{a_1,a_2,...\} مجموعهٔ یک الفبا باشد، بردار پاریک یک کلمه به صورت یک تابع در قالب p:\Sigma^* \longrightarrow \mathbb{N}^k خواهد بود به‌طوری‌که p(w) = (|w_{a_1}|,|w_{a_2}|,...,|w_{a_k}|) و |w_{a_i}| نشان دهندهٔ تعداد حرف a_i در کلمهٔ w است.
می‌گوییم زیرمجموعه‌ای از \mathbb{N}^k خطی است اگر به ازای بردارهای u_0,...,u_m این زیر مجموعه به صورت u_0 + \left \langle u_1,...,u_m \right \rangle = \{ u_0 + t_1 u_1 +...+ t_m u_m | t_1,...,t_m \in \mathbb{N}\} باشد.
می‌گوییم یک زیرمجموعه از \mathbb{N}^k شبه‌خطی است اگر اجتماعی از چند زیرمجموعهٔ خطی باشد.
فرض کنید L یک زبان مستقل از متن و P(L)مجموعهٔ بردارهای پاریک کلمات در Lباشد که P(L) = \{p(w)|w\in L\}. آنگاه P(L) یک مجموعهٔ شبه خطی است.
می‌گوییم دو زبان جابه‌جایی‌پذیرند اگر دارای مجموعهٔ بردارهای پاریک برابر باشند. اگر S یک مجموعه ی شبه‌خطی باشد، زبان شامل کلماتی که بردارهای پاریک آن‌ها در S است با بعضی از زبان‌های منطم جابه‌جایی‌پذیرند. در نتیجه هر زبان مستقل از متنی با بعضی از زبان‌های منظم جابه‌جایی‌پذیرند.
## اهمیت آن
در قضیهٔ پاریک اثبات می‌شود که بعضی از زبان‌های مستقل از متن فقط میتوانند گرامرهای مبهم داشته باشند که به این زبان ها، زبان‌های ذاتاً مبهم گفته می‌شود. به عبارتی دیگر بعضی از گرامرهای مستقل از متن را نمی‌توان به گرامر مستقل از متن غیر مبهمی تبدیل کرد.
## نگاشت پاریک
فرض کنید \Sigma = \{a_1,a_2,...\} الفبای یک زبان باشد که n \in \mathbb{N}^+ و ترتیب a_1,a_2,... دلخواه ولی ثابت است. برای w \in \Sigma^* تصویر پاریک معادل است با:
:\begin{align}
\Psi(w) = (m_1,...,m_n)
\end{align}
که هر m_i تعداد a_i‌ها در w hsj.
نگاشت پاریک روی یک زبان به صورت مقابل تعریف می‌شود:
برای یک زبان دلخواه مانند L که L \in \Sigma^* قرار دهید \Psi (L) = \{ \Psi(w)| w \in L\}
مثال: (نگاشت پاریک کلمات یک گرامر مستقل از متن)
گرامر مستقل از متن G = (N,\Sigma , R,S) را با قواعد زیر در نظر بگیرید:
:\begin{align}
S \longrightarrow ASB | BSA | ab
\end{align}
:\begin{align}  
A \longrightarrow a
\end{align}
:\begin{align} 
B \longrightarrow b
\end{align}
این بدین معناست که زبان تولید شده توسط G دارای رشته‌هایی است که a و b‌ها میتوانند در آن به صورت درهم آمیخته ظاهر شوند. اما از آنجایی که از تعریف زبان پیداست تعداد آن‌ها در رشته برابر خواهد بود. علاوه بر این همیشه از هر حرف حداقل یکی وجود دارد.
حال اگر a_1 و a_2 را با توجه به تعریف بالا به ترتیب a و b بگیریم و رشته‌های w_1 = aaaabbbb \in L(G) و w_2 = babababa \in L(G) فرض کنیم. هر دو این رشته‌ها دارای نگاشت پاریک یکسان هستند؛ \Psi(w_i) = (4,4) که داریم 1\leq i \leq 2
## اثبات
این قضیه با استقرا روی یک مجموعه از درخت‌های اشتقاق و با استفاده از نگاشت‌های پاریک به دست آمده از مجموعه ی درخت‌های اشتقاق پایانه‌ها و امکان بزرگ کردن آن‌ها در طول اشتقاق اثبات می‌شود.
## منابع

* Kozen, Dexter (1997), *Automata and Computability*, New York: Springer-Verlag. .
* Parikh, Rohit (1966), *"On Context-Free Languages"*, Umeå Universitet
* Håkan Lindqvist. *Parikh's Theorem*, New York: Springer-Verlag. 
* Language Generating Devices, *Language Generating Devices*, Quartly Progress Report, Research Laboratory of Electronics, MIT.

رده:اتوماتا (رایانش)
رده:زبان‌های صوری
رده:منطق در علوم کامپیوتر