שפה אונארית

מתוך המכלול, האנציקלופדיה היהודית
קפיצה לניווט קפיצה לחיפוש

שפה אונארית היא שפה שמכילה רק מילים מהצורה , כלומר שפה L תיקרא אונארית אם , כאשר 1 יכול להיות כל תו בא"ב סופי. (למרות שמקובל לדבר על א"ב של 0 ו-1 בלבד). לדוגמה: השפה של כל המחרוזות שמייצגות את המספרים הראשוניים מעל א"ב של {0,1} היא שפה אונארית. לכל שפה ניתן להגדיר שפה אונארית מקבילה, כאשר פשוט "מותחים" כל מילה לייצוג אונארי. דוגמה: המילה 1001 (9 בבינארית) תימתח למילה 111111111 (9 פעמים 1).
שפה שניתנת להכרעה בזמן אקספוננציאלי, המקבילה האונרית שלה ניתן להכרעה בזמן לינארי, אך שפה שאינה כריעה בגרסה הרגילה שלה, אינה כריעה גם בגרסה האונארית. כל שפה אונארית נמצאת ב-P/Poly, כולל שפות אונאריות לא כריעות.

P Computer-science.svg ערך זה הוא קצרמר בנושא מדעי המחשב. אתם מוזמנים לתרום למכלול ולהרחיב אותו.