موضوع مقاله: گرامر مستقل از متن تصادفی | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # گرامر مستقل از متن تصادفی | مقدمه: گرامر مستقل از متن تصادفی یک گرامر مستقل از متن است که هر کدام از قواعد تولید آن با یک احتمال همراه شده‌است. | ## بخش 1: گرامر مستقل از متن تصادفی | در این نوع گرامر هر درخت اشتقاق دارای یک احتمال است که این احتمال برابر است با حاصلضرب احتمال قواعد به کار رفته در فرایند اشتقاق آن؛ بنابراین در گرامر مستقل از متن تصادفی، برخی از اشتقاق‌ها پایدارتر از دیگری هستند. به همان طریقی که مدل‌های پنهان مارکوف، تعمیم یافتهٔ گرامرهای منظم هستند، گرامرهای مستقل از متن تصادفی نیز تعمیم یافتهٔ گرامرهای مستقل از متن‌اند. گرامرهای مستقل از متن تصادفی در زمینه‌های گسترده‌ای، از پردازش زبان‌های طبیعی گرفته تا بیوانفورماتیک، کاربرد دارند. الگوریتم‌ها یک گرامر مستقل از متن تصادفی، یک رشته از زبان را می‌تواند از مسیرهای مختلفی تولید کند که به هر کدام از آن‌ها یک اشتقاق گفته می‌شود. از آنجا که هر کدام از قواعد گرامر مستقل از متن تصادفی دارای یک احتمال می‌باشند، هر اشتقاق نیز دارای یک احتمال می‌گردد که برابر است با حاصلضرب احتمال‌های قواعد به کار رفته در آن اشتقاق. از میان اشتقاق‌های ممکن برای یک رشته، آن اشتقاقی که دارای بیشترین احتمال است به عنوان محتمل‌ترین اشتقاق انتخاب می‌گردد که به آن اشتقاق Viterbi گفته می‌شود. گونهٔ تغییر یافته‌ای از الگوریتم CYK با گرفتن یک رشته از زبان و یک گرامر مستقل از متن تصادفی به عنوان ورودی، اشتقاق Viterbi آن را پیدا می‌کند. | ## بخش 2: گرامر مستقل از متن تصادفی | مجموع احتمالات تولید یک رشته توسط یک گرامر مستقل از متن تصادفی برابر است با حاصل جمع احتمال‌های همهٔ اشتقاق‌های ممکن برای یک رشته توسط آن گرامر. در برخی مواقع می‌خواهیم با داشتن مجموعه‌ای از رشته‌ها و اشتقاق‌های آن‌ها، احتمال‌های قواعد یک گرامر مستقل از متن تصادفی را به دست آوریم به طوری که گرامر، رشته‌های داده شده را با اشتقاق‌های داده شده تولید کند. کاربردها پردازش زبان‌های طبیعی گرامرهای مستقل از متن در آغاز در طی تلاش برای مدل کردن زبان‌های طبیعی به وجود آمدند. این گرامرها به صورت قواعدی قطعی تعریف شدند که البته هنوز برای کاربردهای گوناگونی من‌جمله طراحی زبان‌های برنامه‌سازی کاربرد دارند. گرامرهای مستقل از متن تصادفی در طی تلاش برای گسترش دادن گرامرهای مستقل از متن برای مقابله با پیچیدگی‌های زبان‌های طبیعی (به عنوان مثال: ابهام) به وجود آمدند. ابهام بدین معنی است که ممکن است برای یک دنباله از کلمات بیش از یک اشتقاق وجود داشته باشد که به دلایل مختلفی اتفاق می‌افتد، مانند کلماتی که املای یکسان و معانی مختلفی دارند. هر دو این روش‌ها دارای مشکلاتی همچون زیاد شدن بیش از حد تعداد قواعد یا تولید رشته‌های ناخواسته می‌باشند. | ## بخش 3: گرامر مستقل از متن تصادفی | گرامرهای تصادفی این مشکلات را با استفاده از تنظیم قواعد بر اساس فرکانس تعداد زیادی اشتقاق حل می‌کنند. بیوانفورماتیک گرامرهای مستقل از متن در مدل کردن ساختار دوم آران‌ای بسیار خوب عمل می‌کنند. ساختار دوم آران‌ای شامل نوکلئوتیدهایی است درون یک مولکول تک رشته‌ای آران‌ای که مکمل یکدیگرند و جفت باز تشکیل می‌دهند. این جفت شدن بازها از لحاظ زیست‌شناسی دارای اهمیت هستند، زیرا با عملکرد آران‌ای در ارتباط‌اند. اکثر این جفت بازها می‌توانند در یک گرامر مستقل از متن نشان داده شوند(یک استثنا مهم، شبه گره‌ها هستند). به عنوان مثال، گرامر زیر را در نظر بگیرید که در آن a، c، g و u نشان دهندهٔ نوکلئوتیدها هستند و S سمبل شروع و تنها ناپایانهٔ گرامر است: S → aSu | cSg | gSc | uSa این گرامر مستقل از متن ساده مولکول آران‌ایی را نشان می‌دهد که کلاً از دو نوع ناحیه مکمل ساخته شده‌است و تنها جفت بازهای A-U و C-G در آن وجود دارند. | ## جمع‌بندی | با اضافه کردن احتمال به گرامرهای مستقل از متن پیچیده‌تر، می‌توان جفت بازهای بیشتر و الگوهای پیچیده‌تر یک مولکول آران‌ای را مدل کرد.