نظریه پاریک

قضیهٔ پاریک (به انگلیسی: Parikh's Theorem) یکی از قضایای علوم کامپیوتر نظری است که در سال ۱۹۶۱ توسط روهیت پاریک(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{aligned}\Psi (w)=(m_{1},...,m_{n})\end{aligned}}$

که هر $m_{i}$ تعداد $a_{i}$‌ها در $w$ hsj. نگاشت پاریک روی یک زبان به صورت مقابل تعریف می‌شود: برای یک زبان دلخواه مانند $L$ که $L\in \Sigma ^{*}$ قرار دهید $\Psi (L)=\{\Psi (w)|w\in L\}$ مثال: (نگاشت پاریک کلمات یک گرامر مستقل از متن) گرامر مستقل از متن $G=(N,\Sigma ,R,S)$ را با قواعد زیر در نظر بگیرید:

${\begin{aligned}S\longrightarrow ASB|BSA|ab\end{aligned}}$

${\begin{aligned}A\longrightarrow a\end{aligned}}$

${\begin{aligned}B\longrightarrow b\end{aligned}}$

این بدین معناست که زبان تولید شده توسط $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. ISBN 3-540-78105-6.
• Parikh, Rohit (1966), "On Context-Free Languages", Umeå Universitet
• Håkan Lindqvist. Parikh's Theorem, New York: Springer-Verlag. ISBN 3-540-78105-6
• Language Generating Devices, Language Generating Devices, Quartly Progress Report, Research Laboratory of Electronics, MIT.